問題解決のアプローチ
南山大学 数理情報学部
情報システム数理学科
稲川敬介
OUTLINE

問題解決のアプローチ


ORの事例





最適化手法とOR (オペレーションズ・リサーチ)
悪魔の城へ
捕えられたネズミ
最適化
実践的なOR
まとめ
最適化手法とOR

OR(オペレーションズ・リサーチ, Operations
Research, Operational Research)





システムマネジメント (System Management)
経営科学 (Management Science)
経営の効率化 (コスト削減)
意思決定者の支援
Operation:操作, 動作, 工程. 業務, 運営, 経営.
作戦行動。
ORの単純な事例
3つの例
 悪魔の城へ
 捕えられたネズミ
 最適化
悪魔の城へ


お姫様が悪魔にさらわれました。
悪魔の城へ助けに行こう。
悪魔の城へ

最も近い道(最短路)を探そう
15
1
50
20
80
0
4
30
10
2
5
15
20
55
3
40
ダイクストラ法
A)
B)
C)
出発点の距離を0とし,それ以外のノードまで
の最短距離を無限大とする。
すべてのノードをチェックしていれば終了。そう
でなければ,まだチェックしていないノードの内,
最も距離の短いノードを選択する。
選択されたノードから,それぞれのノードまでの
最短距離を計算し,すでに設定されている距離
より短ければ,更新する。更新が終了したら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の単純な事例
3つの例
 悪魔の城へ



最短路;ダイクストラ法
捕えられたネズミ
最適化
捕らえられたネズミ

一匹のネズミが捕らえられ,あるトラップに入れ
られました。
捕らえられたネズミ

そのトラップには,A,B,Cのドアがあり,




Aのドアを進むと 4時間かかって脱出できます
Bのドアを進むと 7時間かかって元に戻ります
Cのドアを進むと 3時間かかって元に戻ります
このとき,ネズミは平均何時間でこのトラップを
脱出できるでしょうか?

ただし,ネズミはそれぞれのドアを1/3 の確率で選び,
何度元に戻ってもその確率は変わらないものとします。
捕らえられたネズミ


ネズミが脱出できずにトラップ内で過ごす時間を
滞在時間と呼ぶことにする.
ネズミはそれぞれのとびらを 1/3 の確率で選ぶ
ので,1回目のとびらの選択のみを考えた平均
滞在時間は以下の通りになる.
捕らえられたネズミ

2回目のとびらの選択のみを考えた平均滞在時
間は以下の通りになる.
捕らえられたネズミ

3回目のとびらの選択のみを考えた平均滞在時
間は以下の通りになる.
捕らえられたネズミ

同様に考えると,n 回目のとびらの選択では,以
下の時間となる

∞回目まで計算する。
捕らえられたネズミ

∞回目までの計算
モデリング
そんなことを考えなくても…

確率モデル





平均滞在時間をXとおく
Aのドア:4時間 → 脱出 (残り 時間)
Bのドア:7時間 → 元に戻る (残り 時間)
Cのドア:3時間 → 元に戻る (残り 時間)
この方程式のXを求めると…
モデリング

この方程式のXを求めると
よって,
平均滞在時間は14時間。
“捕らえられたネズミ”のまとめ

トラップのシステムをモデル化することにより,平
均滞在時間を簡単に得ることができる。


確率的に起こる事象を合理的に考える。


モデル化:構造を理解し,数式で表現
ネズミの平均滞在時間は14時間
応用例

電話線の本数、銀行の窓口の数
ORの単純な事例
3つの例
 悪魔の城へ


捕えられたネズミ


最短路;ダイクストラ法
モデリング;確率モデル
最適化
最適化

現実世界の中で



利益 → できるだけ大きくしたい
費用 → できるだけ小さくしたい
最適化とは


大きくしたいものを 最大に
小さくしたいものを 最小に すること。
在庫管理(コストの最小化)

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となるようなxを
求める。
在庫管理

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]
ダウンロード

0 - 南山大学 瀬戸キャンパスホームページ