[PR]当サイトはアフィリエイト広告を利用しています。
はじめに
以前このブログで釣銭問題のシミュレーションについて書きました。
ただこの記事、それなりに実用的な内容を扱おうとして結構複雑になっていて、いきなりこの記事から釣銭問題のシミュレーションをやってみようという方には、少しハードルが高いものになっています。
そこで今回は、もっと単純な内容にして、釣銭シミュレーションの原理的な部分がわかるように、釣銭シミュレーションの入門記事を書いてみました。
今回の記事を読むことで、文化祭屋台の釣銭シミュレーションの理解が深まれば幸いです。
参考としてこの記事のシミュレーションのアイディアは次の書籍のミニアイスの例題を元に考えました。初学者向けにわかりやすく解説されています。
参考: 松井泰子 根本俊男 宇野毅明（2008）『入門オペレーションズ・リサーチ』東海大学出版部.
今回の問題
次のような例題を考えましょう。
電池1パックを700円で販売する。
支払いは100円玉か1000円札でのみ行う。
販売個数は100個とする。
釣銭用の100円玉は何個用意すればよいだろうか？
100個の電池パックを販売する問題だね
考え方
700円の商品を購入した際のお釣りの出し方が全部で何パターンあるか考えます。
考えられるのは次の二つのパターンです。
1. 1000円札で支払う→お釣り300円
2. 100円玉7枚で支払う→お釣り0円
次にこの1と2の二つのパターンがどのくらいの確率で起きるかを考えます。
2はお財布に100円玉7枚が入っている可能性は少ないでしょうから、1よりは確率は低いと考えて、2の確率を0.3としましょう。
1は2以外の確率となるので0.7となります。つまり千円払う確率の方が発生しやすいと考えます。
1と2の確率を足すと1.0になることに注意しましょう。パターンが2つ以上ある場合も確率を足すと1.0になると考えます。
以下の図はお釣り用の100円玉が3個必要な（パターン1）確率と、必要ない確率（パターン2）の合計が1になることを示した図です。
問題は100円玉が足りなくなることだから、1000円札の枚数ではなく、100円玉の残数に着目するよ。ちなみに100円玉が減らないときは100円玉が7つ手に入るよ。上の図の0はお釣り用の100円玉の必要数だよ
100円玉7つで支払ってくれればお釣りを支払う必要がないので苦労しません。しかし1000円札で支払われるとお釣り用の100円玉が3つ必要です。100円玉7つで支払ってもらう人を確保しつつ、1000円札支払いのために時折100円玉が3つ必要になる。このバランスをシミュレーションしようという話になります。
これで下準備は整いました。
次ではこれをコンピュータでシミュレーションする方法を述べます。
シミュレーションのやり方
まず次のアルゴリズムを見てみましょう。
1： 0から1の乱数を発生させて、0.7以下なら100円玉を3つ減らす。0.7より大きく1以下なら7つ増やす。
2： 1を100回繰り返す。ただし繰り返すたびに100円玉の数の最小値を保存する。
3： 100円玉の最小値の値を「最も100円玉が少なかったとき」として、この絶対値を準備するべき100円玉の枚数とする。
何をやっているかもう少し具体的に見ていきます。
1ですが、乱数を発生させて0.34が出たとします。これは0.7以下なので1000円払ったときが発生したと考えます。すると100円玉残高は-3となります。
100円玉残高は初期値を0とします。他の値で始めるより0のほうが手間が少ないので0を使いましょう。
残数がマイナスになっても驚かないでね。残数が-30とかになっても最初に30個用意しておけばよかったと結論付けるだけだよ。初期値が100でも0でも結局同じことをやっているからね
初期値を0にして、何回もお釣り用に100円玉が-3されていき、100回乱数を発生させて-30が最低値となると、最初に30枚用意しておけばよかったという結論が導けます。ただしこの100回乱数を発生させるという一回のシミュレーションだと偶然の要素が強いので、何回もシミュレーションして統計的な結論を使います。それについてはこの後の項「一回のシミュレーションでいいのか」で扱います。
続いて2です。現在100円玉残高は-3でした。
100円玉の数の最小値は-3です。
ここでもう一回乱数を発生させます。0.52が出たとしましょう。
0.7以下なので100円玉残高を-3します。残高は-6になります。
100円玉の最小値は-6です。
繰り返し3回目は0.81が出ました。この時0.7より大きいので100円玉残高を+7します。
すると残高は+1となります。最小値は-6のままです。
なぜ+7するかですが、お釣りは0円でも100円玉は7つ取得できるのでそれを残高に追加します。
販売個数が100個なので100回乱数を発生させます。
100回目で残高-22、最小値-33となったとします。
この-33が一番ピンチになるときの100円玉の必要枚数と考えます。
つまりとりあえず33枚最初に持っていれば、釣銭が足りないということはなさそうです。
とりあえずシミュレーションはできた、かな？
本当にこれでいいのでしょうか？次の項に続きます。
一回のシミュレーションでいいのか？
しかし普通に考えて1日分電池を販売したとしても、2日目はまた違う結果になることが予想されます。
何日分かシミュレーションしてみて、その結果から考えたほうが精度が上がりそうです。
とりあえず100日分シミュレーションしてみましょう。
つまり100個販売する日を100日分シミュレーションしてみるよ
ちなみにもう少し数学的にちゃんとした日数の決め方は、モンテカルロ法という学問で扱っているのですが、今回は100日としています。
100回の乱数を一回区切りにして、それを100回シミュレーションします。
乱数は100×100で10000回発生していることに気をつけましょう。
これで100日分の100円玉の最小値が蓄積されます。
具体的なプログラムは後に記述するとして、100日分の最小値が貯まったら何をするのかという話を次にします。
分布を求める
まずマイナスの最小値を絶対値に直して、それの出現回数の分布を求めます。
ただし最小値がプラスの値だったら、「プラスだった」という分類に入れます。お釣りを準備しなくても、誰かが最初に100円玉7枚払ってくれたら足りましたという場合です。
例えば最小値が5と出た日が2回あったら出現回数は2、最小値が7と出た日が4回あったら出現回数は4とします。
つまり最小値-5で終了した日が2回あった、-7で終了した日が4回あったということだよ
プラスだった→2
これはひとまとめに扱います。続いて最小値が負数で終わった日の結果です。
（最小値）→（出現回数）の順で記載
1→1回
2→2回
3→1回
4→1回
5→2回
6→3回
7→4回
…
32→2回
33→2回
34→1回
この～回の数値を1から順に足していきます。
5まで足してみましょう。
1+2+1+1+2=7
この7の意味ですが、100回最小値を求めた中の7回ということですから、釣銭を5枚準備すれば足りた確率は
7 / 100 = 0.07
つまり7％だったということになります。
1から5までの場合を考えているから、5枚最初に準備していれば今考えている状況ではすべて対応可能ということだね。それが100日中7日に当てはまったということだよ
5枚準備すれば、それ以下の枚数準備する場合は網羅できますからね。
最後の方の32だと、97回が合計となるので（最小値34で100日分のデータが集まったとしています）
97 / 100 = 0.97
つまり32枚準備すれば97％足りると考えることができます。
例えば95%足りる準備枚数は何枚かと考えたいときは、上で述べたような足し算を最小値1から順に行って、合計が95を超えればよいと考えられます。
上の例では31か32あたりで超えるだろうね
100%足りるというのは最悪値-3×100個分の-300です。つまり300枚100円玉を用意していれば絶対足ります。でもそんなに準備するとそれだけ手間と硬貨発行のお金、保管場所もかかります。なので実際は95%などの適当なところで妥協して、足りなくなったらしょうがないから銀行へ、みたいになります。ただし95%くらいは上で求めた32とか31枚で足りる可能性が高いということです。
実際のプログラム
次のようになります。
import random
yaritori = 0
zandaka = 0
minZandaka = 0
minList = [0] * (100 * 3)
goukei = 0
for i in range(100):
zandaka = 0
minZandaka = 0
for j in range(100):
yaritori = random.random()
if(yaritori <= 0.7):
zandaka -= 3
else:
zandaka += 7
if(zandaka < minZandaka):
minZandaka = zandaka
if(minZandaka >= 0):
minList[0] += 1
else:
minList[-minZandaka] += 1
for i in range(3 * 100):
goukei += minList[i]
if(goukei > 95):
print("coin: ", i)
breakプログラムの解説
for j in range(100):
yaritori = random.random()
if(yaritori <= 0.7):
zandaka -= 3
else:
zandaka += 7
if(zandaka < minZandaka):
minZandaka = zandakaこの部分で乱数を発生させて、-3するか+7するか決定しています。
残高の最小値も更新します。
if(minZandaka >= 0):
minList[0] += 1
else:
minList[-minZandaka] += 1この部分で最小値の蓄積を行います。
最小値が0以上なら0番目の要素のカウントを一つ増やします。
それ以外なら最小値の要素番号のカウントを一つ増やします。
minList = [0] * (100 * 3)最小値の蓄積用のリストです。
今回は-3が100回出るのが最悪の場合なので、-300まで出ると想定すればよいでしょう。
つまりリストの要素数は300となります。
for i in range(3 * 100):
goukei += minList[i]
if(goukei > 95):
print("coin: ", i)
break最小値蓄積用リストの値を小さい順に合計していきます。
合計が95を超えた時点の最小値を出力します。
出力
実際の出力がこちら。
coin: 83
100円玉は83枚も必要のようですね。
上で述べた例より結構離れました。
95%うまくいくとすると、それなりに1000円札ばかりの時が続くという場面もシミュレーションしているんだろうね
なお、1000円札の支払い確率を0.7、700円を100円玉で支払う確率を0.3としていますが、この確率を変えれば当然結果は変わります。できればこれまでの実際の支払データからどのくらいの確率になるか想定しておければなお良いですね。
まとめ
今回は釣銭シミュレーションの原理的な部分がわかるように、釣銭シミュレーションの入門記事を書きました。
乱数を発生させて、一番不都合な状態の100円玉を数えて、蓄積して、分布を求めることで必要な100円玉の枚数を導きました。
釣銭シミュレーションのイメージがつかめると幸いです。
