2019年8月10日土曜日

待ち行列:Jacksonネットワークの計算

待ち行列理論の中でJacksonネットワークの計算をしてみます。
(1)推移確率行列
ノードがN個あるネットワークを考える。推移確率行列は次の式になります。通常、行和が1になりますが、1にならない場合がそのノードから外部への退去と考えます。例えばi行の行和が0.7の場合、ノードiから外部への退去は0.3となります。
推移確率行列が上の場合、ノード2は行和が0.6のため、ノード2から外部への退去は0.4となります。

(2) トラフィック方程式
次にノードiへの到着率αを求めます。トラフィック方程式は次のようになります。
ベクトル表記
要素で表記
行列表記
これを式変形して計算しやすい形にします。
ベクトル表記
この線形方程式を解くことでαが得られます。ρは次の式で求められます。μはサービス率です。
 (3) 定常分布の算出
ノード i の人数を ni とすると、全ノードのそれぞれの人数のベクトル表現を n = (n1, n2, · · · , nN ) とする。 この時、定常分布は下記になる。ただし全てのノードで ρi < 1 となることが必要である。周辺分布は、それぞれのノードの定常分布となる

 (4) 平均系内人数
各ノードの平均系内人数は M/M/1 待ち行列モデルに従うので、それぞれの平均系内人数 Li は下記になる
(5) 数値計算
簡単な例で数値計算をしてみます。加藤、小沢、ORの基礎、実教出版、P153の例を使ってみます。
この場合の推移確率行列は、下記です。
外部からの到着率は
サービス率は
これからトラフィック方程式を解くと、αは
これからρは
平均系内人数は
ρが1に近くなると系内人数は発散します。
定常分布を求めます。今回はn = [6, 1, 2]と人数分布になる場合のそれぞれのノードの定常分布は、下記になります。
 n = [6, 1, 2]となる場合の結合分布は
となります。各ノードの定常分布のグラフは下記になります。
[ソースコード:Matlab]

0 件のコメント:

コメントを投稿