問題解決のアプローチ 南山大学 数理情報学部 情報システム数理学科 稲川敬介. OUTLINE 問題解決のアプローチ  最適化手法と OR ( オペレーションズ・リサーチ ) OR の事例  悪魔の城へ  捕えられたネズミ  最適化 実践的な OR まとめ.

Presentation on theme: "問題解決のアプローチ 南山大学 数理情報学部 情報システム数理学科 稲川敬介. OUTLINE 問題解決のアプローチ  最適化手法と OR ( オペレーションズ・リサーチ ) OR の事例  悪魔の城へ  捕えられたネズミ  最適化 実践的な OR まとめ."— Presentation transcript:

1 問題解決のアプローチ 南山大学 数理情報学部 情報システム数理学科 稲川敬介

2 OUTLINE 問題解決のアプローチ  最適化手法と OR ( オペレーションズ・リサーチ ) OR の事例  悪魔の城へ  捕えられたネズミ  最適化 実践的な OR まとめ

3 最適化手法と OR OR （オペレーションズ・リサーチ, Operations Research, Operational Research)  システムマネジメント (System Management)  経営科学 （ Management Science ）  経営の効率化 （コスト削減）  意思決定者の支援 Operation ：操作, 動作, 工程. 業務, 運営, 経営. 作戦行動。

4 OR の単純な事例 ３つの例 悪魔の城へ 捕えられたネズミ 最適化

5 悪魔の城へ お姫様が悪魔にさらわれました。 悪魔の城へ助けに行こう。

6 悪魔の城へ 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 最も近い道（最短路）を探そう

7 ダイクストラ法 A) 出発点の距離を０とし，それ以外のノード までの最短距離を無限大とする。 B) すべてのノードをチェックしていれば終了。 そうでなければ，まだチェックしていない ノードの内，最も距離の短いノードを選択 する。 C) 選択されたノードから，それぞれのノード までの最短距離を計算し，すでに設定され ている距離より短ければ，更新する。更新 が終了したら B) へ。

8 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞ Nul ∞ 0 - ∞ ∞ ∞

9 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞ Nul ∞ 0 - ∞ ∞ ∞ 0 50 0 55 0 80 0

10 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞ Nul ∞50 Nul0 0 - ∞80 Nul0 ∞55 Nul0 ∞ 0 65 1 70 1 1

11 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞ 0 70 1 95 3 1 3

12 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞95 Nul3 0 95 3 1 3 4

13 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞95 Nul3 0 85 2 1 3 4 2

14 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞9585 Nul32 0 1 3 4 2 5

15 ダイクストラ法 0 3 1 4 2 5 50 80 55 20 10 15 40 30 20 ∞65 Nul1 ∞50 Nul0 0 - ∞8070 Nul01 ∞55 Nul0 ∞9585 Nul32 0 1 2 5

16 “ 悪魔の城へ ” のまとめ ダイクストラ法を用いれば，最短路がわかる  それより短い経路はないことが保障される はっきりとした計算手順（アルゴリズム）を 使う  コンピュータが理解可能  小さな問題だけでなく、大きな問題でも最短路が 得られる 応用例  カーナビ、水道管の設置（最小木）

17 OR の単純な事例 ３つの例 悪魔の城へ  最短路；ダイクストラ法 捕えられたネズミ 最適化

18 捕らえられたネズミ 一匹のネズミが捕らえられ，あるトラップに 入れられました。

19 捕らえられたネズミ そのトラップには， A,B,C のドアがあり，  A のドアを進むと 4 時間かかって脱出できます  B のドアを進むと 7 時間かかって元に戻ります  C のドアを進むと 3 時間かかって元に戻ります このとき，ネズミは平均何時間でこのトラッ プを脱出できるでしょうか？  ただし，ネズミはそれぞれのドアを 1/3 の確率で 選び，何度元に戻ってもその確率は変わらないも のとします。

20 捕らえられたネズミ ネズミが脱出できずにトラップ内で過ごす時 間を滞在時間と呼ぶことにする． ネズミはそれぞれのとびらを 1/3 の確率で選 ぶので， 1 回目のとびらの選択のみを考えた 平均滞在時間は以下の通りになる．

21 捕らえられたネズミ ２回目のとびらの選択のみを考えた平均滞在 時間は以下の通りになる．

22 捕らえられたネズミ ３回目のとびらの選択のみを考えた平均滞在 時間は以下の通りになる．

23 捕らえられたネズミ 同様に考えると， n 回目のとびらの選択では， 以下の時間となる ∞ 回目まで計算する。

24 捕らえられたネズミ ∞ 回目までの計算

25 モデリング 確率モデル  平均滞在時間を X とおく  A のドア： 4 時間 → 脱出 ( 残り 時間 )  B のドア： 7 時間 → 元に戻る ( 残り 時間 )  C のドア： 3 時間 → 元に戻る ( 残り 時間 ) この方程式の X を求めると … そんなことを考えなくても …

26 モデリング この方程式の X を求めると よって， 平均滞在時間は１４時間。

27 “ 捕らえられたネズミ ” のまとめ トラップのシステムをモデル化することによ り，平均滞在時間を簡単に得ることができる。  モデル化：構造を理解し，数式で表現 確率的に起こる事象を合理的に考える。  ネズミの平均滞在時間は 14 時間 応用例  電話線の本数、銀行の窓口の数

28 OR の単純な事例 ３つの例 悪魔の城へ  最短路；ダイクストラ法 捕えられたネズミ  モデリング；確率モデル 最適化

29 現実世界の中で  利益 → できるだけ大きくしたい  費用 → できるだけ小さくしたい 最適化とは  大きくしたいものを 最大に  小さくしたいものを 最小に すること。

30 在庫管理（コストの最小化） K くんは自動車工場の倉庫係りを担当してい る。彼の扱っている部品 A は，毎日の使用量 ( 需要 ) が一定で，年間需要量は R 個である。 彼の調査では，部品 A を 1 年間保管しておく ために要する費用は，金利も含めて 1 個あた り a 円で，また部品 A を発注するのにかかる 発注費用は，発注量に関係なく 1 回当たり b 円 であった。どのように発注したら費用は最小 ですむか。  (OR 入門～意思決定の基礎～，実況出版 )

31 在庫管理 年間需要量： R 個 (= 500 個 ) 年間保管費（ 1 個当たり）： a 円 (=6,000 円 ) 発注費（ 1 回当たり）： b 円 (=1,200 円 ) 1 回当たりの発注量をどのように決定すべきか？

32 在庫管理 在庫量の変化  発注量を とおく 発注

33 在庫管理 年間発注費（ 1 回 b 円）＝  年間 R 個必要なので、発注回数は R/x 回

34 在庫管理 年間保管費（ 1 個 a 円）＝  発注量を とおく

35 在庫管理 年間保管費（ 1 個 a 円）＝  発注量を とおく

36 在庫管理 年間保管費（ 1 個 a 円）＝  発注量を とおく

37 在庫管理 年間保管費（ 1 個 a 円）＝  発注量を とおく

38 在庫管理 年間保管費（ 1 個 a 円）＝ 年間発注費（ 1 回 b 円）＝ R=500, a=6000, b=1200 のとき  =10 とすると総費用は 3 万 + 7.5 万 =10.5 万円  =30 とすると総費用は 9 万 + 2.5 万 =11.5 万円 発注費は安くなったが保管費が上がり、総費 用は 1 万円高くなった。  トレードオフ

39 在庫管理 関数として描くと ( 保管費 ) ( 発注費 ) R=500, a=6000, b=1200 のとき

40 在庫管理 関数として描くと ( 保管費 ) ( 発注費 ) 極値： 接線の傾 きが 0 。 すなわち、 微分して 0 となる 点。 R=500, a=6000, b=1200 のとき

41 在庫管理 総費用の関数を微分し、それが 0 となるよう なｘを求める。

42 在庫管理 R=500, a=6000, b=1200 のとき  =10 とすると総費用は 3 万 + 7.5 万 =10.5 万円  =30 とすると総費用は 9 万 + 2.5 万 =11.5 万円  =16 とすると総費用は 48,000 + 46, 875 =94, 875 円 1 万円以上の差

43 “ 最適化 ” のまとめ 費用の最小化  統計などによる費用の分析 （多くの人がやってい る）  モデルと最小化 （なかなかやられていない） 感よりも数学  合理的な意思決定 応用例  在庫管理、ロジスティクスや SCM など経営戦略

44 より現実的な応用例 救急車の配備場所の決定  最短路：救急車は呼び出された場所まで最も近い 道を通ってやってくる （ダイクストラ法）  モデリング：呼び出しはいつ起こるかわからない、 救急車は利用中かもしれない （確率モデル）  最適化：救急車を呼び出してから現場に到着する までの時間（対応時間）を最小にしたい （最小 化）

45 一般道路と主要道路 ある市の道路網  黒；一般道路  赤；主要道路 速度  一般： 27.51 km/ 時  主要： 46.34 km/ 時

46 計算結果 1 現在ある施設 だけを用いた 場合，現状が 最適． このとき， w = 5.5645 ， P b = 0.0023. 1:100,000

47 計算結果 2 右図の場所に 配置すること が最適． このとき， w = 4.6740, P b = 0.0011. ( 現状 ; w = 5.5645, P b = 0.0023.) 1:100,000

48 ドリンカーの救命曲線 1966 年，ドリ ンカーが WHO に報告した救 命曲線．横軸 は脳に酸素が 送られなく なってから ( 心 停止から ) の 分数． ( 参考；東京消防庁ホームページ http://www.tfd.metro.tokyo.jp/ ） http://www.tfd.metro.tokyo.jp/ 5 分で約 25%

49 M ． Cara の曲線 ( 仏， 1981) ( 提供；東京消防庁ホームページ http://www.tfd.metro.tokyo.jp/ ） http://www.tfd.metro.tokyo.jp/

50 まとめ 問題解決のアプローチ  分析 ( 統計 )  モデリング ( 数理モデルの構築 )  最適化 ( 問題独自の特性や数学的性質を利用 ) 問題解決のためには  問題点と改善案 ( 文型の想像力 )  実践的な数学 ( 理系の技術 )  問題を見る眼 ( 経験とセンス ) OR （オペレーションズ・リサーチ）

51 Thank you. 南山大学 数理情報学部 情報システム数理学科 稲川敬介 inakawa@nanzan-u.ac.jp