- ベストアンサー
難プログラミングです。
待ち行列のシミュレーション問題です。 頭を抱えているので、良かったらプログラミングがお分かりになる方、 レスポンスいただけますでしょうか。ちなみにVBAでやっています。 ある店の５分あたりの来客数は、お昼時に平均４人、夕食時は平均３人、その他の時間帯は平均２人のポアソン分布にそれぞれ近似的に従っている。（各時間帯は３時間ずつ）カウンターでお客を一人処理するのに必要な時間は一律５分である。ただし、待ち行列は１つだけとする。（カウンタごとに待ち行列をつくるのではない）以下のシュミレーションを行った上で検討せよ。 １．店舗の収益をできるだけ多くする観点からは、各時間帯においてカ ウンターを幾つ稼動させるのが望ましいか。（カウンター店員の自給 や客１人あたりの利益等各自で適当に与えて検討） ２．客があまり長時間待つことがないようにする。例えば行列で５人以 上が待つようなことが10日に1回以下しか起こらないようにする。そ のためには、各時間帯においてカウンターをいくつ稼動するのが望ま しいか。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
5分刻みでカウンターと待ち行列の状態を見ているのでは、その5分の間に「(a)ひとりの客が来て待ち行列に加わり、(b)カウンターでひとりの客の応対が終わった」というのが正しく処理できるでしょうか。(a)と(b)のどちらが先に生じたかで、その5分の間に待ち行列の長さの最大値が違ってきますぜ。 ●イベント・ドリブン(event driven)で考えた方が良いんじゃないかなー。ここでイベントというのは、 「j番目の客が来る」という出来事と、 「（どれかのカウンターで）j番目の客の応対が終わる」という出来事 です。時間を等間隔に区切るのではなくて、そういう出来事が生じた時点だけに注目して処理を行うんです。 ●カウンターがn個あるとしましょう。 j番目の客が来た時刻t[j]において、カウンターが応対しているうちで一番早く来た客はk番目の客だとします。 もし、j-k<nなら、待ち行列はありません。カウンターは(j-k)+1人(j番目の客を含めて）に応対中で、空いているカウンターはn-((j-k)+1)個です。 もし、j-k≧nなら、待ち行列に((j-k)+1)-n人(j番目の客を含めて）並んでいて、空いているカウンターは0個です。 ●さて、「j番目の客が来た時刻t[j]から j+1番目の客が来た時刻t[j+1]の直前までの時間に何が起こったか」を考えますと、 1. t[j]から t[j+1]の直前まで客は一人も来ていない。 2. k番目の客の応対が終わる時刻はt[k]+5(分）、k+1番目の客の応対が終わる時刻はt[k+1]+5(分）、…と分かっています。そして、「応対が終わる」というイベントが生じる度に もし待ち行列があれば、長さがひとつ減る。 もし待ち行列がなければ、空いているカウンターが一つ増える。 ということが起こります。 だから、例えば、 もし t[k]+5(分）< t[j+1] であって、しかも待ち行列があれば、 時刻t[j]に長さ((j-k)+1)-nだった待ち行列が、時刻t[k]+5(分)に長さ((j-k)+1)-n-1になる。つまり、t[j]から t[j+1]の直前までの時間の中で、待ち行列が長さ((j-k)+1)-nだった時間はt[k]+5(分)-t[j]である。 さらに もし t[k+1]+5(分）< t[j+1] であって、しかも待ち行列があれば、 （t[k]+5(分）< t[k+1]+5(分）であるから） 時刻t[k]+5(分）に長さ((j-k)+1)-n-1だった待ち行列が、時刻t[k+1]+5(分)に長さ((j-k)+1)-n-2になる。つまり、t[j]から t[j+1]の直前までの時間の中で、待ち行列が長さ((j-k)+1)-n-1だった時間はt[k+1]-t[k]である。 という具合です。 以下、t[k+m]+5(分)<t[j+1]である最大のmまで同様です。（もちろん、待ち行列が0になった場合には、以後の処理の中身が違います。） 従って、時刻t[j+1]の直前の時点で、カウンターが応対しているうちで一番早く来た客はk+m+1番目の客です。 で、時刻t[j+1]の直前の時点でカウンターが全て稼働中で長さL(L≧0)の待ち行列があったとします。そこに時刻t[j+1]に新しい客が来ると、待ち行列がひとつ伸びる。ですから、「t[j]から t[j+1]の直前までの時間の中で、待ち行列が長さLだった時間」はt[j+1]-(t[k+m]+5(分))です。 一方、時刻t[j+1]の直前の時点でカウンターがひとつでも空いていたとしますと、時刻t[j+1]に新しい客が来ると、空いているカウンターが一つ減ります。 ●従って、「営業開始からt[j+1] の直前までの間に、待ち行列の長さがLだった時間」を表す配列S[L]を用意して、待ち行列の長さが変化する度に累計して行けば良いですね。 ●ところで、客が来るというイベントをどうやって発生させれば良いか。ポアソン分布に従って客が来るということは、j番目の客が来た時刻t[j]とj+1番目の客が来た時刻t[j+1]との間隔( t[j+1]-t[j] )が指数分布に従うということです。その間隔がTよりも大きい確率Pは P=1-exp(-λT) ということになりますから、0から1までの一様乱数に従う値rを一つ発生して r=1-exp(-λT) となるTを計算すれば、t[j+1] = t[j]+Tが計算できます。 ★「行列が出来る店」は開店前に既に列が出来てますねー。あと、閉店時刻にまだ行列が残っていたときにどうするんだろ？（お構いなしに「はい、本日終わりです」と店を閉めてしまうかどうか。）これらをどう扱うかは問題には指定されていないようで、自分で設定しなくちゃいけませんね。 ところで、もっとリアルにするには、列が長くなるにつれて並ぶのを諦める客が増える（λが小さくなる）ようにするとか、カウンターでの応対時間にばらつきを持たせる（到着順に応対が終わるとは限らなくなるので、どのカウンターがどの客を応対中かを示すデータを保持する必要があります）などが考えられます。いろいろ遊べます。 なお、「はい、本日終わりです」方式において人件費の低減だけを考えれば、どんなに列が長くなろうがカウンターは１個が最適であるのは自明です（どこかのブランド店とか、ソ連時代のモスクワの売店みたいです）。が、それだと機会損失（客が来ているのに販売を断ることで、得られた筈の利益をのがすこと）が生じます。この問題には(捌けた客の人数×客単価×利益率-店員の人件費)を最大にしたいという動機がある訳ですね。
その他の回答 (2)
- kts2371148
- ベストアンサー率70% (49/70)
以下の２点を直せば、コンパイルは通るようです。 If t / 5 = Int(t / 5) Then に対応する End If がない If mean = 1 Then に対応する End If がない OKWave上ではどうしてもレイアウトが崩れてしまうのですが、 インデント（字下がり）はつけていますか？ インデントをつけておけば、 どの If と End If が対応しているか、すぐにわかります。
- kts2371148
- ベストアンサー率70% (49/70)
５分あたりの来客数が平均４人の平均ポアソン分布に従うということは、例えば、 最初の５分の来客数は２人 次の５分の来客数は７人 次の５分の来客数は３人 次の５分の来客数は５人 次の５分の来客数は２人 次の５分の来客数は３人 次の５分の来客数は４人 次の５分の来客数は４人 次の５分の来客数は５人 次の５分の来客数は５人 （上記の平均は４．２人） ということになります。（ＶＢＡで実験しました。） 問題は、上記の来客数をどうやって発生させるかになります。 ０～１の乱数を発生させる Rnd 関数はありますので、 その乱数をポアソン分布を使って来客数に変換すればいいことになります。 とりあえずここまでにします。 考えてみてわからなければご質問下さい。
お礼
わざわざ、実験までしていただき、ありがとうございます。 以下に現在奮闘中のソースを貼ります。 コンパイルエラーが出るので、間違っていることは確かなのですが もしよろしければ、何が足らないのか教えてくださりませんでしょうか。
補足
Sub shop() '変数の宣言 Dim period, mean, counter, speed, arrival, queue, process, total, t As Integer Dim r As Double 'シミュレーション条件の入力 period = InputBox("シミュレーション時間（分）を入力してください（5以上の整数）") mean = InputBox("5分あたり平均来客数を入力してください（1～3の整数）") counter = InputBox("カウンタ数を入力してください（1以上の整数）") speed = InputBox("5分あたりカウンタ処理数を入力してください（1以上の整数）") '初期化 Randomize arrival = 0: queue = 0 Cells(1, 1).Value = "経過時間（分）": Cells(2, 1).Value = 0 Cells(1, 2).Value = "待ち行列人数（人）" Cells(1, 3).Value = "新規来客数（人）" Cells(1, 4).Value = "カウンタ処理数（人）" '時間進行 For t = 0 To period '単位時間５分 If t / 5 = Int(t / 5) Then '乱数の発生 r = Rnd() '5分当たりの来客数 ' 平均1の場合 If mean = 1 Then If r < 0.368 Then arrival = 0 ElseIf r < 0.736 Then arrival = 1 ElseIf r < 0.92 Then arrival = 2 ElseIf r < 0.981 Then arrival = 3 ElseIf r < 0.996 Then arrival = 4 Else arrival = 5 End If ' 平均2～4の場合も同様 '来客総数 total = total + arrival '待ち行列人数の増加 process = counter * speed queue = queue + arrival - process If queue < 0 Then process = process + queue: queue = 0 End If '5分毎の結果の表示 Cells(Int(t / 5) + 2, 3).Value = arrival Cells(Int(t / 5) + 2, 4).Value = process Cells(Int(t / 5) + 3, 1).Value = t + 5 Cells(Int(t / 5) + 3, 2).Value = queue Next '来客総数の表示 msg = MsgBox(total & "人", vbInformation + vbOKOnly, "来客総数") End Sub
お礼
インデントは付けていたのですが、何か手違いがありました。 おかげさまで、コンパイルは直りました。 本当にありがとうございます。 しかしながら、このソースが合っていると思えないのです。 「お昼時に平均４人、夕食時は平均３人」というプログラミングを 入力しなければならないと思うのですが・・・ 頭がこんがらがります。。 お時間あるときでかまいませんので、また返信していただけると 幸いです。