待ち行列２．待ち行列の基本方程式

確率 待ち行列 基本情報処理試験

来た人がサービスを受ける場所を窓口とよぶ。1つの窓口でのサービス時間の長さの分布がパラメーター\mu\gt 0の指数分布であると仮定して話を進める。サービス時間の分布の密度関数はg(t)=\mu e^{-\mu t} ,t \gt 0である。すると、出口への到着時間間隔も同じ指数分布になり、このとき出口へ到着した人数の分布はポアソン分布になる。t時間内にn人サービスを終える確率を\Psi_n (t)とすれば、\displaystyle{\Psi_n (t)=\frac{(\mu t)^n}{n!} e^{-\mu t}},t \gt 0となる。\muは単位時間当たりのサービス終了人数（平均サービス率）を与える。これは、

\displaystyle{\frac{d q_n(t)}{dt}=-\mu q_n (t) + \mu q_{n-1} (t),n \geqq 1}

\displaystyle{\frac{d q_0(t)}{dt}=-\mu q_0 (t)}

なる連立微分方程式の解である。これらの関係から、t時点でサービスステーションの中にいる人数をn人とするときの確率をP_n(t)とおくと、

\displaystyle{\frac{d P_0(t)}{dt}=-\lambda P_0(t) + \mu P_1(t)=0}

\displaystyle{\frac{d P_n(t)}{dt}=-(\lambda+\mu)P_n(t) +\lambda P_{n-1}(t) + \mu P_{n+1}(t) ,n\geqq 1}

となる（後述）。解P_n(t)はt\to \inftyのとき極限をもつ。その極限をP_nとする。P_nはtに依存しない定数であるから

-\lambda P_0 + \mu P_1 =0

-(\lambda+\mu)P_n + \lambda P_{n-1} + \mu P_{n+1} =0,n \geqq 1

最初の式は\mu P_1 - \lambda P_0 =0であり、2番目の式は\mu P_{n+1} -\lambda P_n = \mu P_n - \lambda P_{n-1}と変形できる。すべてのn\geqq 1でこの関係式が成り立つから

\mu P_n - \lambda P_{n-1}=\mu P_{n-1} - \lambda P_{n-2}=\cdots =\mu P_1 - \lambda P_0=0

したがって\displaystyle{P_n = \frac{\lambda}{\mu} P_{n-1}=\left( \frac{\lambda}{\mu} \right)^n P_0}が成り立つ。このP_nの関係式を待ち行列論の基本方程式とよぶ。