問題解決のアプローチ 南山大学 数理情報学部 情報システム数理学科 稲川敬介
OUTLINE 問題解決のアプローチ 最適化手法と OR ( オペレーションズ・リサーチ ) OR の事例 悪魔の城へ 捕えられたネズミ 最適化 実践的な OR まとめ
最適化手法と OR OR （オペレーションズ・リサーチ, Operations Research, Operational Research) システムマネジメント (System Management) 経営科学 （ Management Science ） 経営の効率化 （コスト削減） 意思決定者の支援 Operation ：操作, 動作, 工程. 業務, 運営, 経営. 作戦行動。
OR の単純な事例 ３つの例 悪魔の城へ 捕えられたネズミ 最適化
悪魔の城へ お姫様が悪魔にさらわれました。 悪魔の城へ助けに行こう。
悪魔の城へ 最も近い道（最短路）を探そう
ダイクストラ法 A) 出発点の距離を０とし，それ以外のノード までの最短距離を無限大とする。 B) すべてのノードをチェックしていれば終了。 そうでなければ，まだチェックしていない ノードの内，最も距離の短いノードを選択 する。 C) 選択されたノードから，それぞれのノード までの最短距離を計算し，すでに設定され ている距離より短ければ，更新する。更新 が終了したら B) へ。
ダイクストラ法 ∞ Nul ∞ 0 - ∞ ∞ ∞
ダイクストラ法 ∞ Nul ∞ 0 - ∞ ∞ ∞
ダイクストラ法 ∞ Nul ∞50 Nul0 0 - ∞80 Nul0 ∞55 Nul0 ∞
ダイクストラ法 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞
ダイクストラ法 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞95 Nul
ダイクストラ法 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞95 Nul
ダイクストラ法 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞9585 Nul
ダイクストラ法 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞9585 Nul
“ 悪魔の城へ ” のまとめ ダイクストラ法を用いれば，最短路がわかる それより短い経路はないことが保障される はっきりとした計算手順（アルゴリズム）を 使う コンピュータが理解可能 小さな問題だけでなく、大きな問題でも最短路が 得られる 応用例 カーナビ、水道管の設置（最小木）
OR の単純な事例 ３つの例 悪魔の城へ 最短路；ダイクストラ法 捕えられたネズミ 最適化
捕らえられたネズミ 一匹のネズミが捕らえられ，あるトラップに 入れられました。
捕らえられたネズミ そのトラップには， A,B,C のドアがあり， A のドアを進むと 4 時間かかって脱出できます B のドアを進むと 7 時間かかって元に戻ります C のドアを進むと 3 時間かかって元に戻ります このとき，ネズミは平均何時間でこのトラッ プを脱出できるでしょうか？ ただし，ネズミはそれぞれのドアを 1/3 の確率で 選び，何度元に戻ってもその確率は変わらないも のとします。
捕らえられたネズミ ネズミが脱出できずにトラップ内で過ごす時 間を滞在時間と呼ぶことにする． ネズミはそれぞれのとびらを 1/3 の確率で選 ぶので， 1 回目のとびらの選択のみを考えた 平均滞在時間は以下の通りになる．
捕らえられたネズミ ２回目のとびらの選択のみを考えた平均滞在 時間は以下の通りになる．
捕らえられたネズミ ３回目のとびらの選択のみを考えた平均滞在 時間は以下の通りになる．
捕らえられたネズミ 同様に考えると， n 回目のとびらの選択では， 以下の時間となる ∞ 回目まで計算する。
捕らえられたネズミ ∞ 回目までの計算
モデリング 確率モデル 平均滞在時間を X とおく A のドア： 4 時間 → 脱出 ( 残り 時間 ) B のドア： 7 時間 → 元に戻る ( 残り 時間 ) C のドア： 3 時間 → 元に戻る ( 残り 時間 ) この方程式の X を求めると … そんなことを考えなくても …
モデリング この方程式の X を求めると よって， 平均滞在時間は１４時間。
“ 捕らえられたネズミ ” のまとめ トラップのシステムをモデル化することによ り，平均滞在時間を簡単に得ることができる。 モデル化：構造を理解し，数式で表現 確率的に起こる事象を合理的に考える。 ネズミの平均滞在時間は 14 時間 応用例 電話線の本数、銀行の窓口の数
OR の単純な事例 ３つの例 悪魔の城へ 最短路；ダイクストラ法 捕えられたネズミ モデリング；確率モデル 最適化
現実世界の中で 利益 → できるだけ大きくしたい 費用 → できるだけ小さくしたい 最適化とは 大きくしたいものを 最大に 小さくしたいものを 最小に すること。
在庫管理（コストの最小化） K くんは自動車工場の倉庫係りを担当してい る。彼の扱っている部品 A は，毎日の使用量 ( 需要 ) が一定で，年間需要量は R 個である。 彼の調査では，部品 A を 1 年間保管しておく ために要する費用は，金利も含めて 1 個あた り a 円で，また部品 A を発注するのにかかる 発注費用は，発注量に関係なく 1 回当たり b 円 であった。どのように発注したら費用は最小 ですむか。 (OR 入門～意思決定の基礎～，実況出版 )
在庫管理 年間需要量： R 個 (= 500 個 ) 年間保管費（ 1 個当たり）： a 円 (=6,000 円 ) 発注費（ 1 回当たり）： b 円 (=1,200 円 ) 1 回当たりの発注量をどのように決定すべきか？
在庫管理 在庫量の変化 発注量を とおく 発注
在庫管理 年間発注費（ 1 回 b 円）＝ 年間 R 個必要なので、発注回数は R/x 回
在庫管理 年間保管費（ 1 個 a 円）＝ 発注量を とおく
在庫管理 年間保管費（ 1 個 a 円）＝ 発注量を とおく
在庫管理 年間保管費（ 1 個 a 円）＝ 発注量を とおく
在庫管理 年間保管費（ 1 個 a 円）＝ 発注量を とおく
在庫管理 年間保管費（ 1 個 a 円）＝ 年間発注費（ 1 回 b 円）＝ R=500, a=6000, b=1200 のとき =10 とすると総費用は 3 万 万 =10.5 万円 =30 とすると総費用は 9 万 万 =11.5 万円 発注費は安くなったが保管費が上がり、総費 用は 1 万円高くなった。 トレードオフ
在庫管理 関数として描くと ( 保管費 ) ( 発注費 ) R=500, a=6000, b=1200 のとき
在庫管理 関数として描くと ( 保管費 ) ( 発注費 ) 極値： 接線の傾 きが 0 。 すなわち、 微分して 0 となる 点。 R=500, a=6000, b=1200 のとき
在庫管理 総費用の関数を微分し、それが 0 となるよう なｘを求める。
在庫管理 R=500, a=6000, b=1200 のとき =10 とすると総費用は 3 万 万 =10.5 万円 =30 とすると総費用は 9 万 万 =11.5 万円 =16 とすると総費用は 48, , 875 =94, 875 円 1 万円以上の差
“ 最適化 ” のまとめ 費用の最小化 統計などによる費用の分析 （多くの人がやってい る） モデルと最小化 （なかなかやられていない） 感よりも数学 合理的な意思決定 応用例 在庫管理、ロジスティクスや SCM など経営戦略
より現実的な応用例 救急車の配備場所の決定 最短路：救急車は呼び出された場所まで最も近い 道を通ってやってくる （ダイクストラ法） モデリング：呼び出しはいつ起こるかわからない、 救急車は利用中かもしれない （確率モデル） 最適化：救急車を呼び出してから現場に到着する までの時間（対応時間）を最小にしたい （最小 化）
一般道路と主要道路 ある市の道路網 黒；一般道路 赤；主要道路 速度 一般： km/ 時 主要： km/ 時
計算結果 1 現在ある施設 だけを用いた 場合，現状が 最適． このとき， w = ， P b = :100,000
計算結果 2 右図の場所に 配置すること が最適． このとき， w = , P b = ( 現状 ; w = , P b = ) 1:100,000
ドリンカーの救命曲線 1966 年，ドリ ンカーが WHO に報告した救 命曲線．横軸 は脳に酸素が 送られなく なってから ( 心 停止から ) の 分数． ( 参考；東京消防庁ホームページ ） 5 分で約 25%
M ． Cara の曲線 ( 仏， 1981) ( 提供；東京消防庁ホームページ ）
まとめ 問題解決のアプローチ 分析 ( 統計 ) モデリング ( 数理モデルの構築 ) 最適化 ( 問題独自の特性や数学的性質を利用 ) 問題解決のためには 問題点と改善案 ( 文型の想像力 ) 実践的な数学 ( 理系の技術 ) 問題を見る眼 ( 経験とセンス ) OR （オペレーションズ・リサーチ）
Thank you. 南山大学 数理情報学部 情報システム数理学科 稲川敬介