高校~社会人の情報学基礎知識講座

乱数を用いたシミュレーション2 待ち行列理論

»

がっつり書き出すとそれで1冊本が書けるくらいの話になるのでさわりだけ。

行列を処理する場合を考えると、どういう風にさばいていけば滞りなく処理できるでしょうか?
(あ、ここでいう行列は数学のほうではなく真面目に人間が並んでいる状態のほうです。)

ということをシミュレーションしてみる。

このとき、一人当たりの処理にかかる時間や新しい人の発生タイミングなどに乱数を用いてシミュレーションすることがある。

例えばスーパーマーケットみたく各レジで行列を作るほうが効率が良いのか、銀行のように1列に並んで複数窓口で対応するほうが良いのか、といった例である。
後者の類似事例としてコールセンターにおける電話対応などのシミュレーションにも応用できる。

このような行列をどうさばくのか、というシミュレーションに対して対応するのが待ち行列理論である。

あるいは、カウンター席のみの行列ができるラーメン屋とかを考えてみるといい。

これをシミュレートすると何がいいのか、というと「何席用意すればいいの?」という問題を解くことができるわけです。
席数が多いほうが同時に処理できる人数は増えるけどお金がかかる。また、空席は無駄であると考えられる。
かといって席数を少なくしすぎると行列処理が滞り、顧客満足度が下がる。
このバランス妥協点を探すことになるわけですが・・・

という話。

基本情報とかだと、午前問題で出てくる特殊用語としてはM/M/1待ち行列というのが存在する。
レジ1か所で処理してるスーパーマーケットのレジ行列、と考えるといい。
詳細な話だとhttps://www.virtualinvader.com/mm1-queue-theory/ とかわかりやすかったかな。


確率分布

ランダム、と一口に言っても出てくる値に偏りがある場合があるよ、という話。
理想的な6面体サイコロを振った場合、1~6まで出てくる確率はそれぞれ同じで1/6です。
これを一様分布という。

では、このサイコロを2つ振って(TRPG界隈ではこれを2d6と表現する)その合計値を考えてみる。
2: 1/36
3: 2/36
4: 3/36
5: 4/36
6: 5/36
7: 6/36
8: 5/36
9: 4/36
10:3/36
11:2/36
12:1/36
と合計値によって出やすさが異なってくる。
(カタンの開拓者たち、というボードゲームだと7で盗賊が動くし、6,8は出やすい目として赤くマーキングされていたりする)
で、これはサイコロの数を増やせば増やすほどに顕著化する。
(桃鉄で急行系使うと移動できる歩数が概ね同じになるかんじ。)

こんな感じで真ん中に偏った確率分布を正規分布という。

他にポアソン分布なんかも存在する。

乱数を用いたシミュレーションをする場合、「どの確率分布に従って生成された乱数を用いるべきか」は割とモデルの正確性に寄与する部分なので脳死で一様分布(rand関数とか使うと概ねこれ)はやめとくほうが良い。

ちなみにこれを「乱数のコク」と表現した人がいる。
https://togetter.com/li/1044668

Comment(0)

コメント

コメントを投稿する