Document

問題解決のアプローチ
南山大学数理情報学部
情報システム数理学科
稲川敬介
OUTLINE

問題解決のアプローチ


ORの事例





最適化手法とOR (オペレーションズ・リサーチ)
悪魔の城へ
捕えられたネズミ
最適化
実践的なOR
まとめ
最適化手法とOR

OR（オペレーションズ・リサーチ, Operations
Research, Operational Research)





システムマネジメント (System Management)
経営科学（Management Science）
経営の効率化（コスト削減）
意思決定者の支援
Operation：操作, 動作, 工程. 業務, 運営, 経営.
作戦行動。
ORの単純な事例
３つの例
 悪魔の城へ
 捕えられたネズミ
 最適化
悪魔の城へ


お姫様が悪魔にさらわれました。
悪魔の城へ助けに行こう。
悪魔の城へ

最も近い道（最短路）を探そう
15
1
50
20
80
0
4
30
10
2
5
15
20
55
3
40
ダイクストラ法
A)
B)
C)
出発点の距離を０とし，それ以外のノードまで
の最短距離を無限大とする。
すべてのノードをチェックしていれば終了。そう
でなければ，まだチェックしていないノードの内，
最も距離の短いノードを選択する。
選択されたノードから，それぞれのノードまでの
最短距離を計算し，すでに設定されている距離
より短ければ，更新する。更新が終了したらB)
へ。
ダイクストラ法
∞
∞
Nul
Nul
15
1
50
4
0
10
20
-
80
0
2
20
55
3
∞
Nul
30
5
15
∞
∞
Nul
Nul
40
ダイクストラ法
∞
50
∞
Nul
0
Nul
15
1
50
4
0
10
20
-
80
0
5
2
20
55
30
15
∞
80
Nul
0
Nul
40
3
∞
55
Nul
0
∞
ダイクストラ法
∞
50
∞
65
Nul
0
Nul
1
15
1
50
4
0
10
20
-
80
0
5
2
20
55
30
15
∞
80
70
Nul
0
1
Nul
40
3
∞
55
Nul
0
∞
ダイクストラ法
∞
50
∞
65
Nul
0
Nul
1
15
1
50
4
0
10
20
-
80
0
5
2
20
55
30
15
∞
80
70
Nul
0
1
40
3
∞
55
Nul
0
∞
95
Nul
3
ダイクストラ法
∞
50
∞
65
Nul
0
Nul
1
15
1
50
4
0
10
20
-
80
0
5
2
20
55
30
15
∞
80
70
Nul
0
1
40
3
∞
55
Nul
0
∞
95
Nul
3
ダイクストラ法
∞
50
∞
65
Nul
0
Nul
1
15
1
50
4
0
10
20
-
80
0
5
2
20
55
30
15
∞
80
70
Nul
0
1
40
3
∞
55
Nul
0
∞
95
85
Nul
3
2
ダイクストラ法
∞
50
∞
65
Nul
0
Nul
1
15
1
50
4
0
10
20
-
80
0
5
2
20
55
30
15
∞
80
70
Nul
0
1
40
3
∞
55
Nul
0
∞
95
85
Nul
3
2
ダイクストラ法
∞
50
∞
65
Nul
0
Nul
1
15
1
50
4
0
10
20
-
80
0
5
2
20
55
30
15
∞
80
70
Nul
0
1
40
3
∞
55
Nul
0
∞
95
85
Nul
3
2
“悪魔の城へ”のまとめ

ダイクストラ法を用いれば，最短路がわかる


はっきりとした計算手順（アルゴリズム）を使う



それより短い経路はないことが保障される
コンピュータが理解可能
小さな問題だけでなく、大きな問題でも最短路が得ら
れる
応用例

カーナビ、水道管の設置（最小木）
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万 + 7.5万 =10.5 万円
=30 とすると総費用は 9万 + 2.5万 =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万 + 7.5万 =10.5 万円
=30 とすると総費用は 9万 + 2.5万 =11.5 万円
=16 とすると総費用は 48,000 + 46,875 =94,875 円
1万円以上の差
“最適化”のまとめ

費用の最小化



感よりも数学


統計などによる費用の分析（多くの人がやっている）
モデルと最小化（なかなかやられていない）
合理的な意思決定
応用例

在庫管理、ロジスティクスやSCMなど経営戦略
より現実的な応用例

救急車の配備場所の決定



最短路：救急車は呼び出された場所まで最も近い道
を通ってやってくる（ダイクストラ法）
モデリング：呼び出しはいつ起こるかわからない、救
急車は利用中かもしれない（確率モデル）
最適化：救急車を呼び出してから現場に到着するま
での時間（対応時間）を最小にしたい（最小化）
一般道路と主要道路

ある市の道路網



黒；一般道路
赤；主要道路
速度


一般：27.51 km/時
主要：46.34 km/時
計算結果 1


現在ある施設だ
けを用いた場合，
現状が最適．
このとき，
w = 5.5645，
Pb = 0.0023.
1:100,000
計算結果2


右図の場所に配
置することが最
適．
このとき，
w = 4.6740,
Pb = 0.0011 .
(現状; w = 5.5645,
Pb = 0.0023.)
1:100,000
ドリンカーの救命曲線

1966年，ドリン
カーがWHOに
報告した救命
曲線．横軸は
脳に酸素が送
られなくなって
から(心停止か
ら) の分数．
5分で約25%
(参考；東京消防庁ホームページ
http://www.tfd.metro.tokyo.jp/ ）
M．Caraの曲線(仏，1981)
(提供；東京消防庁ホームページ
http://www.tfd.metro.tokyo.jp/ ）
まとめ

問題解決のアプローチ




問題解決のためには




分析 (統計)
モデリング (数理モデルの構築)
最適化 (問題独自の特性や数学的性質を利用)
問題点と改善案 (文型の想像力)
実践的な数学 (理系の技術)
問題を見る眼 (経験とセンス)
OR（オペレーションズ・リサーチ）
Thank you.
南山大学数理情報学部
情報システム数理学科
稲川敬介
[email protected]

Download Report