M/M/1 待ち行列とリトルの公式

利用率 $ρ = λ / μ < 1$ の M/M/1 について、次の量を求められる: 平均系内人数 $L = \frac{ρ}{1 - ρ}$ 、平均待ち行列長 $L_{q}$ 、平均系内滞在時間 $W = \frac{1}{μ - λ}$ 、平均待ち時間 $W_{q}$ 。また、リトルの公式 $L = λW$ でこれらを互いに換算できる

前提

出生死滅過程の定常分布（大学数学オペレーションズ・リサーチ）
幾何分布・ポアソン分布（大学数学確率・統計）

この技能までの道筋（84 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
平均と合計（算数いろいろな文章題）
平均値・中央値・最頻値（中学数学データの活用）
代表値（平均値・中央値・最頻値）（数学I データの分析）
分散と標準偏差（数学I データの分析）
変量の変換と平均・分散（数学I データの分析）
確率変数の期待値・分散と $a X + b$ （数学B 統計的な推測）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
定積分の計算（数学II 微分法と積分法）
連続型確率変数と確率密度関数（数学B 統計的な推測）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
広義積分（大学数学微分積分）
一様分布・指数分布（大学数学確率・統計）
条件付き確率と乗法定理（数学A 場合の数と確率）
マルコフ連鎖と推移確率（大学数学確率・統計）
定常分布（大学数学確率・統計）
無限等比級数と無限級数（数学III 極限）
出生死滅過程の定常分布（大学数学オペレーションズ・リサーチ）
確率変数の和と積（独立な場合）（数学B 統計的な推測）
独立な試行と反復試行（数学A 場合の数と確率）
二項分布（数学B 統計的な推測）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
増減・凹凸・漸近線とグラフ（数学III 微分法）
テイラー展開（大学数学微分積分）
べき級数と収束半径（大学数学微分積分）
幾何分布・ポアソン分布（大学数学確率・統計）

説明

窓口が 1 つで、客がランダムに到着し、サービス時間もランダムな待ち行列（M/M/1 待ち行列）について、「平均で何人いるか」「平均でどれだけ待つか」を求める技能です。到着率 $λ$ （単位時間あたりの平均到着人数）とサービス率 $μ$ （単位時間あたりに処理できる平均人数）の 2 つの数だけで、平均系内人数 $L$ 、平均待ち行列長 $L_{q}$ 、平均系内滞在時間 $W$ 、平均待ち時間 $W_{q}$ がすべて決まります。人数と時間はリトルの公式 $L = λW$ で互いに換算できます。窓口・サーバ・レジなどの混雑の見積もりに使います。

なぜそうしてよいのか

M/M/1 とは、客がポアソン到着し（到着間隔が平均 $1/ λ$ の指数分布に従い）、サービス時間が平均 $1/ μ$ の指数分布に従い、窓口が 1 つの待ち行列のことです。系内人数（並んでいる人とサービス中の人の合計）を $n$ とすると、これは出生率 $λ_{n} = λ$ $(n \geq 0)$ 、死亡率 $μ_{n} = μ$ $(n \geq 1)$ の出生死滅過程です。平衡方程式 $λ p_{n} = μ p_{n + 1}$ より $p_{n} = ρ^{n} p_{0}$ （ $ρ = λ / μ$ ）となり、 $\sum_{n = 0}^{\infty} p_{n} = p_{0} \cdot \frac{1}{1 - ρ} = 1$ が成り立つためには $ρ < 1$ が必要で、そのとき $p_{0} = 1 - ρ$ 、 $p_{n} = (1 - ρ) ρ^{n}$ です。 $ρ \geq 1$ だと級数が発散して定常分布が存在せず、行列は長期的に際限なく伸びていきます。窓口が使用中である確率は $1 - p_{0} = ρ$ なので、 $ρ$ を利用率と呼びます。

系内人数は 0 から始まる幾何分布 $P (N = n) = (1 - ρ) ρ^{n}$ に従うので、期待値は $L = \sum_{n = 0}^{\infty} n (1 - ρ) ρ^{n} = \frac{ρ}{1 - ρ}$ です。待ち行列に並んでいる人数は、 $n \geq 1$ のとき $n - 1$ （1 人はサービス中）、 $n = 0$ のとき 0 なので、 $L_{q} = \sum_{n = 1}^{\infty} (n - 1) p_{n} = L - \sum_{n = 1}^{\infty} p_{n} = L - ρ = \frac{ρ ^{2}}{1 - ρ}$ となります。

人数と時間を結ぶのがリトルの公式 $L = λW$ です。長い時間 $T$ の間、各時刻の系内人数をグラフにしてその面積 $A$ を考えます。面積 $A$ は「全員の滞在時間の合計」とも見られます。この間の到着人数は約 $λ T$ 人なので、1 人あたりの平均滞在時間は $W \approx A / (λ T)$ 、時間平均の人数は $L \approx A / T$ です。よって $L \approx λW$ で、 $T \to \infty$ の定常状態で等号になります。同じ議論を「待ち行列だけ」に当てはめると $L_{q} = λ W_{q}$ です。これから $W = \frac{L}{λ} = \frac{1}{μ - λ}$ 、 $W_{q} = \frac{L _{q}}{λ} = \frac{λ}{μ ( μ - λ )}$ が得られ、 $W = W_{q} + \frac{1}{μ}$ （待ち時間＋平均サービス時間）とも一致します。

手順

$λ$ と $μ$ の時間の単位をそろえ、利用率 $ρ = λ / μ$ を計算して $ρ < 1$ を確認する（ $ρ \geq 1$ なら定常状態はない）
平均系内人数を求める: $L = \frac{ρ}{1 - ρ}$
平均待ち行列長を求める: $L_{q} = L - ρ = \frac{ρ ^{2}}{1 - ρ}$
リトルの公式で時間に換算する: $W = \frac{L}{λ}$ 、 $W_{q} = \frac{L _{q}}{λ}$
検算として $W = W_{q} + \frac{1}{μ}$ が成り立つか確かめる

例題

窓口が 1 つの受付に、客が 1 時間あたり平均 12 人の割合でポアソン到着し、サービス時間は平均 4 分の指数分布に従う（M/M/1 待ち行列）。定常状態における平均待ち時間 $W_{q}$ を分単位で求めよ。

例題の解答

手順 1: 単位を「分」にそろえる。到着率 $λ = 12/60 = \frac{1}{5}$ （人/分）、サービス率 $μ = \frac{1}{4}$ （人/分）。利用率 $ρ = \frac{1/5}{1/4} = \frac{4}{5} < 1$ なので定常状態がある。
手順 2: $L = \frac{ρ}{1 - ρ} = \frac{4/5}{1/5} = 4$ （人）。
手順 3: $L_{q} = L - ρ = 4 - \frac{4}{5} = \frac{16}{5}$ （人）。
手順 4: リトルの公式 $L_{q} = λ W_{q}$ より $W_{q} = \frac{L _{q}}{λ} = \frac{16/5}{1/5} = 16$ （分）。また $W = \frac{L}{λ} = \frac{4}{1/5} = 20$ （分）。
手順 5: 検算。 $W_{q} + \frac{1}{μ} = 16 + 4 = 20 = W$ で一致する。公式 $W = \frac{1}{μ - λ} = \frac{1}{1/4 - 1/5} = 20$ とも合う。
よって平均待ち時間は 16 分。

答え: $16$

よくある誤り

平均待ち行列長を $L_{q} = L - 1$ としてしまう誤り。系が空（ $n = 0$ ）のときは引く人がいないので、正しくは $L_{q} = \sum_{n \geq 1} (n - 1) p_{n} = L - P (N \geq 1) = L - ρ$ 。例題なら $4 - 1 = 3$ ではなく $\frac{16}{5}$ 。
リトルの公式でサービス率を使い $W = L / μ$ としてしまう誤り。公式の比例定数は系に入ってくる割合なので、正しくは $W = L / λ$ 。例題で $4 \div \frac{1}{4} = 16$ 分を $W$ としてはいけない（正しくは $W = 20$ 分）。
$λ$ と $μ$ の単位をそろえずに $ρ$ を計算してしまう誤り。例題で「12 人/時」と「4 分」から $ρ = 12/4 = 3$ などとするのは誤りで、正しくは両方を分あたりにして $ρ = \frac{1/5}{1/4} = \frac{4}{5}$ 。
$ρ \geq 1$ のときにも公式を使ってしまう誤り。例えば $ρ = 2$ で $L = \frac{2}{1 - 2} = - 2$ となるが、これは意味がない。 $\sum ρ^{n}$ が発散するので定常分布は存在せず、公式は $ρ < 1$ のときだけ使える。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

M/M/c 待ち行列（大学数学オペレーションズ・リサーチ）