待ち行列モデルをケンドール記号で表現したM/M/1
- 前回の勉強内容
- きっかけとなった試験問題
- 待ち行列理論は、行列がどのくらい混んでいるかを考えることです。
- 難しい待ち行列理論をわかりやくしようとD.G.ケンドールさんがケンドールの記号を作りました。
- このケンドールの記号で表された超基本のモデルがM/M/1です。
- M/M/1は、ケンドールの記号で表された待ち行列のモデルです。
- M : サービス要求の到着間隔はポアソン分布に従って「ランダム」です。
- M : サービス時間は指数分布に従って「ランダム」です。
- 1 : サービス窓口は1つです。
- M/M/1には公式があります。
- 次回の勉強内容
前回の勉強内容
きっかけとなった試験問題
通信回線を使用したデータ伝送システムにM/M/1の待ち行列モデルを適用すると，平均回線待ち時間，平均伝送時間，回線利用率の関係は，次に式で表すことができる。
回線利用率が0%から徐々に上がっていく場合，平均回線待ち時間が平均伝送時間よりも最初に長くなるのは，回線利用率が何%を超えたときか。ア. 40 イ. 50 ウ. 60 エ. 70
平成25年秋期問5 M/M/1の待ち行列モデル｜応用情報技術者試験.com
待ち行列理論は、行列がどのくらい混んでいるかを考えることです。
- 英語 : queueing(待機・列を作る) theory
顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論である。
待ち行列理論 - Wikipedia
よくわからないので、過去問とラーメン屋さんでイメージを掴みます。
待ち行列に対する操作を，次のとおり定義する。
ENQ n : 待ち行列にデータnを挿入する 。
DEQ : 待ち行列からデータを取り出す 。空の待ち行列に対し，ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQの操作を行った。
次にDEQ操作を行ったとき，取り出される値はどれか。ア. 1 イ. 2 ウ. 5 エ. 6
平成30年秋期問5 待ち行列に対する操作｜基本情報技術者試験.com
ラーメン屋さんの行列を思い浮かべてみます。
待っている人が待ち行列というキューのおしりに次々入っていく。
順番が来たらキューの頭から次々に出ていく感じ・・・。
- ラーメン屋の行列に３人やってきた
- 操作：ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQ
- 待ち行列(キュー)：1 2 3
- １つ席が空いたから１人行列から出ていく
- 操作：ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQ
- 待ち行列(キュー)：2 3
- ラーメン屋の行列に２人やってきた
- 操作：ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQ
- 待ち行列(キュー)：2 3 4 5
- １つ席が空いたから１人行列から出ていく
- 操作：ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQ
- 待ち行列(キュー)：3 4 5
- ラーメン屋の行列に１人やってきた
- 操作：ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQ
- 待ち行列(キュー)：3 4 5 6
- ２つ席が空いたから２人行列から出ていく
- 操作：ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQ
- 待ち行列(キュー)：5 6
- 次に席が空いたら「5」がラーメン食べられる
難しい待ち行列理論をわかりやくしようとD.G.ケンドールさんがケンドールの記号を作りました。
「A / B / C」の形でモデルの性質を表現するそうです。(本当はCの後に続きがありますが今回は割愛)
- A：サービス要求の到着、一定間隔で到着とかランダムに到着とかね
- B：サービス時間、１要求にサービスする時間
- C：サービスを受け入れる窓口の数、サービスをしてくれる物の数
M/M/1は、ケンドールの記号で表された待ち行列のモデルです。
Mの意味は、「現在の情報で将来起こる確率が決まる」と推測します。
調べていて「MはMarkovian」というのをカワギリにわからない言葉を追ってみました。
そして、自分なり理解で「Markovian = 現在の情報で将来起こる確率が決まる」となりました。
このようなモデルをM/M/1モデルと言います（MはMarkovianの頭文字，1は窓口の数を表す）。
待ち行列理論（M/M/1モデル）の定理とその証明 | 高校数学の美しい物語
markovianとは
マルコフ過程に関連した、またはマルコフ過程によって作られた
markovianの意味・使い方 - 英和辞典 WEBLIO辞書
マルコフ過程とは、マルコフ性をもつ確率過程のことをいう。すなわち、未来の挙動が現在の値だけで決定され、過去の挙動と無関係であるという性質を持つ確率過程である。
マルコフ過程 - Wikipedia
マルコフ性
将来における事象の起こる確率は現在の状態だけから決まり、過去の状態には依存しないという性質のこと。
マルコフ性とは - はてなキーワード
M : サービス要求の到着間隔はポアソン分布に従って「ランダム」です。
M/M/1の待ち行列モデルにおいて，一定時間内に到着する客数の分布はどれか。
エ. ポアソン分布
平成24年春期問2 M/M/1の待ち行列モデル｜応用情報技術者試験.com
ポアソン分布は、偶然の事象が起こる回数の分布です。
このようにポアソン分布とは、時間（例えば1時間当たり）、場所（例えば1平方メートル当たり）、距離（例えば1キロメートル当たり）などある一定区間の中で、偶然に起こる事象の数の分布です。
ポアソン分布 - NtRand
ポアソン分布とは、(どの時点でも同様な起こりやすさでランダムに起こる現象と仮定した場合に)「単位時間あたりに平均 λ 回起こる現象が、単位時間に k 回起きる確率」を表すのに使われる確率分布のこと。
ポアソン分布とは何か。その性質と使い方を例題から解説 【馬に蹴られて死ぬ兵士の数を予測した数式】 | アタリマエ！
平均到着時間 = 1 / 到着率
到着率は、単位時間あたりやってくる利用者の平均人数です。
平均到着時間は、１人の利用者がやってくる平均時間です。
平均到着時間は、ポアソン分布に従うと新たな利用者が単位時間当たり(到着率)人のスピードで「ランダムに」来るということです。
M : サービス時間は指数分布に従って「ランダム」です。
指数分布は、ランダムなイベントの発生間隔を表す分布です。
長くなる要求もあれば、即終わる要求もあるということです。
ランダムな現象を「発生回数で捉えるとポアソン分布」「発生間隔で捉えると指数分布」です。
ランダムな現象を「発生間隔で捉えると指数分布，発生回数で捉えるとポアソン分布」と覚えておきましょう。
指数分布の意味と具体例 | 高校数学の美しい物語
平均サービス時間 = 1 / サービス率
サービス率は、単位時間あたりに処理できる平均人数です。
平均サービス時間は、１人の利用者を処理する平均時間
平均サービス時間は、指数分布に従うと店主は単位時間当たり(サービス率)人のスピードで行列をさばいていくということです。
M/M/1には公式があります。
公式がよくわからないので過去問に当てはめながら考えます。
ATM(現金自動預払機)が1台ずつ設置してある二つの支店を統合し，統合後の支店にはATMを1台設置する。統合後のATMの平均待ち時間を求める式はどれか。ここで，待ち時間はM/M/1の待ち行列モデルに従い，平均待ち時間にはサービス時間を含まず，ATMを1台に統合しても十分に処理できるものとする。
〔条件〕
平均サービス時間：Ts
統合前のシステムの利用率：両支店ともρ
統合後の利用者数は，統合前の両支店の利用者数の合計ア. (ρ / (1 - ρ)) × Ts
イ. (ρ / (1 - 2ρ)) × Ts
ウ. (2ρ / (1 - ρ)) × Ts
エ. (2ρ / (1 - 2ρ)) × Ts
平成27年春期問1 M/M/1の待ち行列モデル｜応用情報技術者試験.com
利用率 = 到着率 / サービス率
利用率は、平均どのくらい混んでいるかということです。
- 「統合前のシステムの利用率：両支店ともρ」
- 「ATMを1台設置」から統合後もサービス率は変わらない。
- 「統合後の利用者数は，統合前の両支店の利用者数の合計」で到着率は２倍になる。
| 統合前 | 統合後 | |
|---|---|---|
| 利用率 | 支店A：ρ = 到着率 / サービス率 支店B：ρ = 到着率 / サービス率 |
(2 × 到着率) / サービス率 = 2 × 到着率 / サービス率 = 2(到着率 / サービス率) = 2ρ |
行列に並んでいる人数 = 利用率 / (1 - 利用率)
統合後の行列に並んでいる人数 = 2ρ / (1 - 2ρ)
平均待ち時間 = (利用率 / (1 - 利用率)) * 平均サービス時間
待ち時間は「行列に並んでいる人数」が「平均サービス時間」のサービスを受け終わるまでの時間です。
- 「平均サービス時間：Ts」
待ち時間 = 行列に並んでいる人数 × Ts = (2ρ / (1 - 2ρ)) × Ts
