最適化・シミュレーション演習 第１１回 やや複雑なSimul8のモデル， 分散減少法 • 授業サポートページ http://www.morito.mgmt.waseda.ac.jp/optsim/ • 数理計画による最適化と（離散事象型）シミュレーションに 関する演習を行う．使用するソフトウェアは，AMPL（＋ GurobiまたはCPLEX)，および，Simul8を想定している． • 演習では，数理計画による最適化やシミュレーションの実践 的能力を身につけることを目指す。履修者は，Cを使用でき る環境を有するPCを持参すること。受講者は，実験室にて， 演習で使用する C，AMPL，Simul8をダウンロードできる。 1 本日のトピックス • やや複雑なSimul8のモデル – ピザ屋のオーブン容量とバイク台数 • 分散減少法 – 考え方 – 共通乱数（法）と負相関法（＝対照変量法） – π推定のモンテカルロ法での実験 – Simul8での分散減少法 2 ピザ屋のオーブン容量とバイク台数 来月開店を予定している赤木ピザは，住宅街を周辺にもつ立地 条件のよい場所に製造専門の小さな店舗を置くことが決まりまし た．今週中には，ピザを焼くオーブンの大きさと，購入する配達用 バイクの台数を決めなければなりません．赤木店長の見積もりに よると，ピーク時には注文が平均到着時間間隔5分の指数分布に したがってランダムに到着すると想定されます．複数枚のピザを 要求する注文は事実上ありません．注文を受けてから，準備時間 を含めてピザを焼き上げるのには10分かかります．オーブンは， ピザ6枚分を単位として"増設”が可能で，オーブン容量の候補は6 枚，12枚，18枚，…となります．オー プンは随時開閉自由とします． バイクの片道配達時間は，下限3分，上限15分の一様分布にした がい，1回の配達では1件の顧客しか回らないことにします．配達 先からもどる時間は配達までの時間と同じとします．赤木店長の ために，顧客の注文からピザが配達されるまでの時間が35分以 内である確率を95％以上にするオーブンの容量と，バイク台数を 3 調べてください． ピザ屋のオーブン台数とバイク台数 • 森戸が考えた「正しくない」モデル • 正しくない理由： ピザが客に届くタイミングと バイクが配達を終えてショップに戻るタイミン グとが同じでない 4 分散減少法 • モンテカルロ法や不確定要素を含むシミュレー ションにおいて、同じ計算量に対し統計的により 精度の高い推定値を得るための技法 • 乱数を用いた数値実験では、使用する乱数系列 やサンプリング方法の操作が可能 • サンプリング方法を工夫した方法 – 層別サンプリング、加重サンプリング • 変量間の相関に着目した方法 – 共通乱数系列法、負相関法、制御変量法 • その他の方法 – 条件付きモンテカルロ法 5 層別サンプリング(stratified sampling) • 対象全体に均等なサンプリングを行わずに、重 要と考えられる領域を重点的に調べる方法 • 定積分I = 𝑔 𝑥 𝑑𝑥の評価では、𝑔 𝑥 の値の大 きい部分はIに及ぼす影響が大きいのでより綿 密に調べ、逆に影響が小さい部分は大雑把に調 べようという考え方 • 積分領域をいくつかの部分領域に分割し、各部 分領域の積分値の推定値の総和から定積分値I を推定 6 加重サンプリング(importance sampling) • 重要であると考えられる領域を重点的にサンプ リングする方法 𝑏 𝑔(𝑥) 𝑑𝑥の例では積分領域を分割 𝑎 • 定積分I = する代わりに𝑔(𝑥)が大きい部分ではf(x)も大きく なる適当な確率密度関数f(x)を 𝑎, 𝑏 上に考え、 に着目し、f(x)に従う乱数𝑋1 , 𝑋2 , … , 𝑋𝑁 を発生さ せ、(1/N) 𝑁 𝑖=1(𝑔(𝑋𝑖 )/𝑓(𝑋𝑖 ))によりIを推定 7 負相関法（Antithetic Variates） • ２つの確率変数X，Yの期待値が等しいときに 確率変数Z＝(X+Y)/2の期待値がX,Yの期待値 と等しく、さらに、XとYとの間に負の相関があ ればZの分散をX，Yの分散よりも小さくできる ことを利用 • 対照変量法と呼ばれることもある（対称変量 法と書いている場合もある） 8 負相関法を用いた π推定のモンテカルロシミュレーション • 𝑥が[0,1]の一様乱数であれば、1 − 𝑥も[0,1] の一様乱数と考えられる • 𝑥が[0,1]の一様乱数であれば、1 − 𝑥も小さめ （大きめ） → 𝑥と1 − 𝑥は負の相関 • 入門的（crude）モンテカルロによるπの推定 𝑥と1 − 𝑥で、y= 1 − 𝑥 2 やy= 1 − (1 − 𝑥)2 を推定 – 𝑥をn個発生させて、各𝑥で𝑦を評価 – 𝑥とをn/2個発生させて、𝑥と1 − 𝑥で、𝑦を評価 9 負相関法（＝対照変量法） シミュレーションの精度向上の方法 今泉 淳 シミュレーションによる値の推定 共分散：各実験間の相関の程度 推定精度を高めるためには? 実験結果のいくつかのペアが負の相関を 持てば小さくなる 負相関法（＝対照変量法） 具体的な実装の一例 具体的な実装の一例 πの推定において Simul8での分散減少法（負相関法） 普通 負相関法 17 宅配ピザのオーブン容量とバイク台数 来月開店を予定している赤木ピザは，住宅街を周辺にもつ立地 条件のよい場所に製造専門の小さな店舗を置くことが決まりまし た．今週中には，ピザを焼くオーブンの大きさと，購入する配達用 バイクの台数を決めなければなりません．赤木店長の見積もりに よると，ピーク時には注文が平均到着時間間隔5分の指数分布に したがってランダムに到着すると想定されます．複数枚のピザを 要求する注文は事実上ありません．注文を受けてから，準備時間 を含めてピザを焼き上げるのには10分かかります．オーブンは， ピザ6枚分を単位として"増設”が可能で，オーブン容量の候補は6 枚，12枚，18枚，…となります．オー プンは随時開閉自由とします． バイクの片道配達時間は，下限3分，上限15分の一様分布にした がい，1回の配達では1件の顧客しか回らないことにします．配達 先からもどる時間は配達までの時間と同じとします．赤木店長の ために，顧客の注文からピザが配達されるまでの時間が35分以 内である確率を95％以上にするオーブンの容量と，バイク台数を 18 調べてください． 宿題１１ （プログラム、結果、考察を提示すること） • 宿題１１．１（宅配ピザ） ピザショップの問題のモデルを作成し， 題意を満足するオーブンの容量とバイクの 台数を求めよ． 19 参考文献 ［１］森戸晋，逆瀬川浩孝，システムシミュレー ション，朝倉書店，2000． ［２］森雅夫，宮沢政清，生田誠三，森戸晋、山 田善靖，「オペレーションズリサーチⅡ」，朝倉 書店，1989． 20 負相関法の効果（πの推定） 実験条件 独立試行の回数＝10000 サンプルサイズ＝N（Non-antithetic) 実験条件 独立試行の回数＝10000 サンプルサイズ＝2*N（Antithetic) Non-antithetic crude (N= 10) pi = 3.137807; s.d. = 0.280934 crude (N= 20) pi = 3.140950; s.d. = 0.197036 crude (N= 30) pi = 3.143317; s.d. = 0.164204 crude (N= 40) pi = 3.141045; s.d. = 0.140282 crude (N= 50) pi = 3.139682; s.d. = 0.126427 crude (N= 60) pi = 3.140395; s.d. = 0.116255 crude (N= 70) pi = 3.142164; s.d. = 0.107834 crude (N= 80) pi = 3.141152; s.d. = 0.099156 crude (N= 90) pi = 3.140886; s.d. = 0.094106 crude (N= 100) pi = 3.140618;s.d. = 0.090154 Antithetic crude (N= 5) pi = 3.141589; s.d. = 0.148866 crude (N= 10) pi = 3.142995; s.d. = 0.104055 crude (N= 15) pi = 3.142442; s.d. = 0.085728 crude (N= 20) pi = 3.141570; s.d. = 0.073789 crude (N= 25) pi = 3.141797; s.d. = 0.066052 crude (N= 30) pi = 3.141578; s.d. = 0.060221 crude (N= 35) pi = 3.140907; s.d. = 0.055871 crude (N= 40) pi = 3.141372; s.d. = 0.052924 crude (N= 45) pi = 3.142005; s.d. = 0.049526 crude (N= 50) pi = 3.141706; s.d. = 0.046836 21
© Copyright 2024 ExpyDoc
