４節 シミュレーション
［第５章 問題解決とその方法］ 
ＡＴＭでの待ち行列（確率的モデル）
授業 第９回
【課題】
銀行にATM(現金自動預払機)が１台設置されている。このATMが使用されているときには，新たに来た客はATMが空くまで列を作って待たなくてはならない。この待ち時間はどのくらいになるのか，また待ち時間を少なくするためにはどのような改善策があるのだろうか。
ただし，前の客が到着してから次の客が到着するまでの到着間隔と，客がATMに対面し操作を始め操作を終了しATMから離れるまでの使用時間は，過去のデータから下の表のようになっていることが分かっている。
到着間隔(分) 人数
１ １１
２ １７
３ １３
４  ９
使用時間(分) 人数
１  ７
２ １６
３ ２７
【考察】
  プログラムは，到着間隔及び使用時間を求める関数部分と
  待ち行列を処理する Main Routine の２部構成でコーディングする。
【プログラム①】到着間隔及び使用時間を求める関数
 算出のアルゴリズム
① 過去のデータから，各階級（時間 : 分）の累積確率を算出しておく。
② 0～1 未満の乱数を発生させる。
③ 乱数の値が累積確率の値を超えない最大の階級（時間 : 分）を求める。
 例）乱数 0.12 ⇒ 1分，乱数 0.16 ⇒ 2分，乱数 0.45 ⇒ 2分，乱数 0.50 ⇒ 3分
 変数一覧
※｢使用時間｣の場合の例
jikan
Dosu
kaikyu
kaikyusu
Kakuritsu
Ruiseki
：時間を求める関数
：各時間の人数（配列変数の引数）
：時間･階級の値
：時間を表す階級の個数
：各時間の人数割合（配列変数）
：各時間の人数累積割合（配列変数）
戻り値は｢分｣ 
[7,16,27] 
1,2,3 のいずれか 
3 
[0.14,0.32,0.54] 
[0.14,0.46,1]
 関数の説明
乱数() ･･･ 0 以上 1 未満のランダムな小数を返す。
例えば，x = 乱数() のとき x に 0.57309 など無作為な小数が代入される。
要素数(配列変数) ･･･ 配列変数の要素の個数を返す。
例えば，Data = [2,4,6] のとき 要素数(Data) の値は 3 である。
 プログラムについて
05～07行
08,09行
10～12行
13～18行
：配列変数 各時間の人数 Dosu の合計を求める。
：配列変数 各時間の人数割合（確率）Kakuritsu を求める。
：配列変数 各時間の人数累積割合（累積確率）Ruiseki を求める。
：乱数を発生させ，それが人数累積割合を超えない最大の使用時間
 を求め，関数の戻り値とする。
【DNCL】時間を求める関数部分 ※配列の添え字は1より始まるものとする。
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
関数 jikan(Dosu):
│   kaikyusu = 要素数(Dosu)
│   Kakuritsu の全ての値を0にする
│   Ruiseki の全ての値を0にする
│   sum = 0
│   i を 1 から kaikyusu まで 1 ずつ増やしながら繰り返す:
│   ⎿   sum = sum + Dosu[i]
│   i を 1 から kaikyusu まで 1 ずつ増やしながら繰り返す:
│   ⎿   Kakuritsu[i] = Dosu[i] / sum
│   Ruiseki[1] = Kakuritsu[1]
│   i を 2 から kaikyusu まで 1 ずつ増やしながら繰り返す:
│   ⎿   Ruiseki[i]=Ruiseki[i-1]+Kakuritsu[i]
│   r = 乱数()
│   kaikyu = 1
│   True の間繰り返す:
│   │   もし r < Ruiseki[kaikyu] ならば:
│   │   ⎿   kaikyu を返す
⎿   ⎿   kaikyu = kaikyu + 1
 ⇨ IDEで動作確認  ※動作確認の為の追加コードを含む
 
0  1  kaikyu  kaikyu+1  kaikyu-1
1 から kaikyusu まで  2 から kaikyusu まで
sum + i  sum+Dosu[i]  Dosu[i]/sum
Kakuritsu[1]  Kakuritsu[i]  Kakuritsu[i-1]
Kakuritsu[kaikyu]  Ruiseki[1]  Ruiseki[i]
Ruiseki[i-1]  Ruiseki[kaikyu]
Ruiseki[i]+Kakuritsu[i-1]  Ruiseki[i-1]+Kakuritsu[i]
×
【プログラム②】行列のモデル（Main Routine)
 数式モデル
・［到着時刻］＝［前の客の到着時刻］＋［確率的に算出した到着間隔］
・［開始時刻］＝［前の客の終了時刻］と［到着時刻］を比較し遅い方の時刻
・［終了時刻］＝［開始時刻］＋［確率的に算出した使用時間］
・［待ち時間］＝［開始時刻］－［到着時刻］
※プログラムでは，それぞれの値を下の行番号で求めている。
客番号 到着間隔 到着時刻 開始時刻 使用時間 終了時刻 待ち時間
13 14 15 16～19 20 21 22
 変数一覧
jikan

kyakusu
kyaku
Chakukan
Chakuji
Kaishiji
Shiyoji
Shuryoji
Machiji
Chakubnp
Shiyobnp
：時間を求める関数
 ※引数は各時間の人数分布（配列変数）
：客全部の人数
：客の番号
：到着間隔（配列変数）
：到着時刻（配列変数）
：開始時刻（配列変数）
：使用時間（配列変数）
：終了時刻（配列変数）
：待ち時間（配列変数）
：到着間隔の人数分布（配列変数）
：使用時間の人数分布（配列変数）
【DNCL】Main Routine ※配列の添え字は1より始まるものとする。
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
kyakusu = 10
Chakukan の全ての値を0にする
Chakuji の全ての値を0にする
Kaishiji の全ての値を0にする
Shiyoji の全ての値を0にする
Shuryoji の全ての値を0にする
Machiji の全ての値を0にする
Chakubnp = [11, 17, 13, 9]
Shiyobnp = [7, 16, 27]

Shiyoji[1] = jikan(Shiyobnp)
Shuryoji[1] = Shiyoji[1]
kyaku を 2 から kyakusu まで 1 ずつ増やしながら繰り返す:
│   Chakukan[kyaku] = jikan(Chakubnp)
│   Chakuji[kyaku]=Chakuji[kyaku-1]+Chakukan[kyaku]
│   もし Shuryoji[kyaku - 1] > Chakuji[kyaku] ならば:
│   ⎿   Kaishiji[kyaku] = Shuryoji[kyaku - 1]
│   そうでなければ:
│   ⎿   Kaishiji[kyaku] = Chakuji[kyaku]
│   Shiyoji[kyaku] = jikan(Shiyobnp)
│   Shuryoji[kyaku] = Kaishiji[kyaku] + Shiyoji[kyaku]
⎿   Machiji[kyaku] = Kaishiji[kyaku] - Chakuji[kyaku]
kyaku を 1 から kyakusu まで 1 ずつ増やしながら繰り返す:
│   表示する("客",kyaku,"：到着間隔",Chakukan[kyaku],
│        "：到着時刻",Chakuji[kyaku],
│        "：開始時刻",Kaishiji[kyaku],
│        "：使用時間",Shiyoji[kyaku],
│        "：終了時刻",Shuryoji[kyaku],
⎿        "：待ち時間",Machiji[kyaku])
 ⇨ IDEで動作確認  ※関数 jikan(Dosu) のコードを含む
 関数を用いて一部修正
上のプログラム Main Routine で，開始時刻を求める16～19行目の部分は，
下の関数を用いると一行で記述ができる。このコードを求めなさい。
最大値(x,y) ･･･ 引数として与えられた二つの値の最大値を返す。
例えば，最大値（1,5）は5となり，最大値(2,2)は2となる。
16
17
18
19
│   もし Shuryoji[kyaku - 1] > Chakuji[kyaku] ならば:
│   ⎿   Kaishiji[kyaku] = Shuryoji[kyaku - 1]
│   そうでなければ:
│   ⎿   Kaishiji[kyaku] = Chakuji[kyaku]
Kaishiji[kyaku] = 最大値(Shuryoji[kyaku-1] , Chakuji[kyaku])
 
kyakusu  kyakusu + 1  kyaku  kyaku + 1
Chakukan[kyaku]  Chakukan[kyaku-1]
Chakuji[kyaku]  Chakuji[kyaku-1]
Kaishiji[kyaku]  Kaishiji[kyaku-1]
Shiyoji[kyaku]  Shiyoji[kyaku-1]
Shuryoji[kyaku]  Shuryoji[kyaku-1]
Machiji[kyaku]  Machiji[kyaku-1]
×
［通常版］
# 関数 jikan =========================== def jikan(dosu):     import random     kaikyusu = len(dosu)     kakuritsu = [0] * kaikyusu     ruiseki = [0] * kaikyusu     #度数の合計 -----------------------     sum = 0     for n in dosu:         sum = sum + n     #確率 -----------------------------     for i in range(kaikyusu):         kakuritsu[i] = dosu[i] / sum     #累積確率 -------------------------     ruiseki[0] = kakuritsu[0]     for i in range(1,kaikyusu):         ruiseki[i] = ruiseki[i-1] + kakuritsu[i]     #出現確率に応じた階級の取得 -------     r = random.random()     kaikyu = 0     while True:         if r < ruiseki[kaikyu]:             return kaikyu + 1         kaikyu = kaikyu + 1 # Main Routine ===========================
kyakusu = 10 chakubnp = [11,17,13,9] shiyobnp = [7,16,27] chakukan = [0] * kyakusu chakuji = [0] * kyakusu kaishiji = [0] * kyakusu shiyoji = [0] * kyakusu shuryoji = [0] * kyakusu machiji = [0] * kyakusu
# 客の総数 # 到着間隔の過去の統計 # 使用時間の過去の統計 # 到着間隔 # 到着時刻 # 開始時刻 # 使用時間 # 終了時刻 # 待ち時間
#最初の客の設定 ----------------------- chakuji[0] = 0 kaishiji[0] = 0 shiyoji[0] = jikan(shiyobnp) shuryoji[0] = shiyoji[0] machiji[0] = 0 #２番目以降の客の設定 ----------------- for kyaku in range(1,kyakusu):     chakukan[kyaku] = jikan(chakubnp)     chakuji[kyaku] = chakuji[kyaku-1] + chakukan[kyaku]     if shuryoji[kyaku-1] > chakuji[kyaku]:         kaishiji[kyaku] = shuryoji[kyaku-1]     else:         kaishiji[kyaku] = chakuji[kyaku]     shiyoji[kyaku] = jikan(shiyobnp)     shuryoji[kyaku] = kaishiji[kyaku] + shiyoji[kyaku]     machiji[kyaku] = kaishiji[kyaku] - chakuji[kyaku] #状況の表示 --------------------------- for kyaku in range(kyakusu):     print("客",kyaku,              "：到着間隔",chakukan[kyaku],              "：到着時刻",chakuji[kyaku],              "：開始時刻",kaishiji[kyaku],              "：使用時間",shiyoji[kyaku],              "：終了時刻",shuryoji[kyaku],              "：待ち時間",machiji[kyaku])