「基礎OR」／「OR演習」
第５回
11/10/2009
森戸 晋
1
中間試験のお知らせ
• 中間試験日程
２００９／１１／２４（火）
• 時間： １３：００～１４：３０
• 場所
– ５６－１０３，５２－２０３教室 （座席指定制）
• ００１～１００まで ５６－１０３教室
• １０１～ （過年度を含む） ５２－２０３教室
2
ネットワーク上の最適化
（ネットワーク計画）の
代表的問題
3
最短路問題
1
10
始
s
点
終
t
点
1
3
2
5
6
2
2
3
各枝の数字は、枝の距離（費用）を表す
4
最大流問題
1
8
5
ｖ
s
t
ｖ
2
6
8
5
2
3
各枝の数字は、枝の容量を表す
5
最小費用流問題
1
10（5）
10
s
1（8）
t
10
3（2）
6（6）
5（8）
2（5）
2
3
各枝の数字は、各点間の単位当たり費用、
（ ）内の数字は、各枝の容量を表す
6
最短路問題
（＝流量1の最小費用流問題）
1
10
始点
1
1
（１）
s
3
2
（１）
（１）
1
6
（１）
5
（１）
t
（１）
終点
2
2
（１）
3
各枝の数字は、各点間の距離（費用）、
（ ）内の数字は、各枝の容量を表す
7
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
（閉路を構成しない、連結な枝の集合）を選ぶ問題
２
1
10
１
５
４
3
6
5
３
2
４
各枝の数字は、各点間の距離（費用）
8
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
（閉路を構成しない、連結な枝の集合）を選ぶ問題
２
1
10
１
５
４
3
6
5
３
2
４
木ではない： 連結していない
9
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
（閉路を構成しない、連結な枝の集合）を選ぶ問題
２
1
10
１
５
４
3
6
5
３
2
４
木ではない： 閉路が存在する
10
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
（閉路を構成しない、連結な枝の集合）を選ぶ問題
２
1
10
１
５
４
3
6
5
３
2
４
すべての点を張らない木
11
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
（閉路を構成しない、連結な枝の集合）を選ぶ問題
２
1
10
１
５
４
3
6
5
３
2
４
すべての点を張る木（全域木）
12
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
（閉路を構成しない、連結な枝の集合）を選ぶ問題
２
1
10
１
５
４
3
6
5
３
2
４
各枝の数字は、各点間の距離（費用）
13
貪欲アルゴリズム（Kruskal法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
14
貪欲アルゴリズム（Kruskal法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
15
貪欲アルゴリズム（Kruskal法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
16
貪欲アルゴリズム（Kruskal法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
17
貪欲アルゴリズム（Kruskal法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
18
貪欲アルゴリズム（Prim法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
19
貪欲アルゴリズム（Prim法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
20
貪欲アルゴリズム（Prim法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
21
貪欲アルゴリズム（Prim法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
22
貪欲アルゴリズム（Prim法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
23
貪欲アルゴリズム（Prim法）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
24
改善法（初期解生成）
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
目的関数値 12
25
改善法
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
26
改善法
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
目的関数値 10(12+3-5)
27
改善法
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
28
改善法
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
目的関数値 9(10+3-4)
29
改善法
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
30
改善法
3
ホ
コ
2
1
ア
1
5
ブ
4
3
シ
目的関数値 8(9+1-2)
31
最短路問題
（ｓからｔへの最短路を求める）
枝の「距離」
7
s
始点
1
8
3 5
5
2
t
終点
6
4
3
33
最短路問題の
線形計画問題による定式化
枝の「距離」
7
s
1
8
3 5
t
終点
6
始点
5
2
4
3
最小化 7xs1+5xs2+5x12+8x1t+3x21+4x23+6x3t
条件 -xs1 - xs2
=-1
xs1
- x12 -x1t + x21
=0
xs2 + x12
- x21 - x23
=0
x23 - x3t =0
x1t
+ x3t =1
xs1, xs 2 , x12 , x1t , x21 , x23 , x3t  0
34
ダイクストラ法(０)
∞
1
∞
1
t
10
ラベル（gi）
2 の初期化
0
s
3
5
2
∞
2
6
3
∞
ラベル（gi）
の初期化
35
ダイクストラ法(1)
∞
1
1
∞
t
10
0
s
3
5
ラベル（gi）
最小の点を走査
2
2
∞
2
6
3
∞
36
ダイクストラ法(2)
∞→10
1
1
∞
t
10
0
s
3
5
6
2
2
∞→5
2
3
∞
37
ダイクストラ法（3）
10
1
1
∞
t
10
ラベル
最小の点を走査
2
0
s
3
5
走査済み
2
5
2
6
3
∞
38
ダイクストラ法（4）
10→8
1
1
∞
t
10
0
s
3
5
6
2
2
5
2
3
∞→7
39
ダイクストラ法（5）
8
1
1
∞
t
10
ラベル
最小の点を走査
2
0
s
3
5
2
5
2
6
3
7
40
ダイクストラ法（6）
8
1
1
∞→13
t
10
0
s
3
5
6
2
2
5
2
3
7
41
ダイクストラ法（7）
8
1
1
13
t
10
ラベル
最小の点を走査
2
0
s
3
5
2
5
2
6
3
7
42
ダイクストラ法（8）
8
1
1
13→9
t
10
0
s
3
5
6
2
2
5
2
3
7
43
ガントチャートもどきの図による解法
44
ガントチャートもどきの図による解法
45
任意の2点間の最短路ｄij ← min｛ｄij，ｄik＋ｄkj｝
1
2
3
4
5
6
7
1
2 3
0
3 4
3
0 ∞
4 ∞ 0
8
4 2
∞ 8 ∞
∞ ∞ 7
∞ ∞ ∞
4
8
4
2
0
2
4
7
5 6
7
∞ ∞ ∞
8 ∞ ∞
∞ 7 ∞
2 4
7
0 ∞ 1
∞ 0
1
1 1
0
k=1 1
2
3
4
5
6
7
1
0
3
4
8
∞
∞
∞
3
4
∞
0
2
∞
7
∞
4
8
4
2
0
2
4
7
5
∞
8
∞
2
0
∞
1
k=1 1
2
3
4
5
6
7
1
2 3
0
3 4
3
0 7
4 7
0
8
4 2
∞ 8 ∞
∞ ∞ 7
∞ ∞ ∞
4
8
4
2
0
2
4
7
5 6
7
∞ ∞ ∞
8 ∞ ∞
∞ 7 ∞
2 4
7
0 ∞ 1
∞ 0
1
1 1
0
8
2
3
0
∞
4
8
∞
∞
6
∞
∞
7
4
∞
0
1
7
∞
∞
∞
7
1
1
0
46
Warshall-Floyd法
任意の2点間の最短路
三角オペレーション
• 距離行列 D＝［ｄij］
• 点 ｊ に関する三角オペレーション
ｄij ← min｛ｄij，ｄik＋ｄkj｝
for all i, j＝1,…,n； i, j ≠ k
k
i
ｊ
47
Warshall-Floyd法のアルゴリズム
任意の2点間の最短路
• 元々の距離行列 C＝［ｃij］
• 初期化
for all i ≠j do ｄij ← ｃij
for i ＝1,…,n do ｄii ← 0
• 基本部分
for k ＝1,…,n do
for i ＝1,…,n ; i ≠ k do
for j ＝1,…,n ； j ≠ k do
ｄij ← min｛ｄij，ｄik＋ｄkj｝
48
任意の2点間の最短路ｄij ← min｛ｄij，ｄik＋ｄkj｝
1
2
3
4
5
6
7
1
2 3
0
3 4
3
0 ∞
4 ∞ 0
8
4 2
∞ 8 ∞
∞ ∞ 7
∞ ∞ ∞
4
8
4
2
0
2
4
7
5 6
7
∞ ∞ ∞
8 ∞ ∞
∞ 7 ∞
2 4
7
0 ∞ 1
∞ 0
1
1 1
0
k=1 1
2
3
4
5
6
7
1
0
3
4
8
∞
∞
∞
3
4
∞
0
2
∞
7
∞
4
8
4
2
0
2
4
7
5
∞
8
∞
2
0
∞
1
k=1 1
2
3
4
5
6
7
1
2 3
0
3 4
3
0 7
4 7
0
8
4 2
∞ 8 ∞
∞ ∞ 7
∞ ∞ ∞
4
8
4
2
0
2
4
7
5 6
7
∞ ∞ ∞
8 ∞ ∞
∞ 7 ∞
2 4
7
0 ∞ 1
∞ 0
1
1 1
0
8
2
3
0
∞
4
8
∞
∞
6
∞
∞
7
4
∞
0
1
7
∞
∞
∞
7
1
1
0
49
1
k=2 2
3
4
5
6
7
1
2 3
0
3 4
3
0 7
4
7 0
8
4 2
∞ 8 ∞
∞ ∞ 7
∞ ∞ ∞
4
8
4
2
0
2
4
7
5 6
7
∞ ∞ ∞
8 ∞ ∞
∞ 7 ∞
2 4
7
0 ∞ 1
∞ 0
1
1 1
0
1
k=2 2
3
4
5
6
7
1 2 3
0 3 4
3 0 7
4 7 0
7
4 2
11 8 15
∞ ∞ 7
∞ ∞ ∞
4
7
4
2
0
2
4
7
5 6 7
11 ∞ ∞
8 ∞ ∞
15 7 ∞
2 4 7
0 ∞ 1
∞ 0 1
1 1 0
1
2
k=3 3
4
5
6
7
1
2 3
0
3 4
3
0 7
4
7 0
7
4 2
11 8 15
∞ ∞ 7
∞ ∞ ∞
4
7
4
2
0
2
4
7
5 6
7
11 ∞ ∞
8 ∞ ∞
15 7 ∞
2 4
7
0 ∞ 1
∞ 0
1
1 1
0
1
2
k=3 3
4
5
6
7
1
2 3
0
3 4
3
0 7
4
7 0
6
4 2
11 8 15
11 14 7
∞ ∞ ∞
4
6
4
2
0
2
4
7
5 6
7
11 11 ∞
8 14 ∞
15 7 ∞
2 4
7
0 ∞ 1
∞ 0
1
1 1
0
50
1
2
3
k=4 4
5
6
7
1 2 3
0 3 4
3 0 7
4 7
0
6 4 2
11 8 15
11 14 7
∞ ∞ ∞
4
6
4
2
0
2
4
7
5 6 7
11 11 ∞
8 14 ∞
15 7 ∞
2 4 7
0 ∞ 1
∞ 0 1
1 1 0
1
2
3
k=4 4
5
6
7
1
2
0
3
3
0
4 6
6
4
8
6
10 8
13 11
4
6
4
2
0
2
4
7
5
8
6
4
2
0
6
1
3
4
6
0
2
4
6
9
6
7
10 13
8 11
6
9
4
7
6
1
0
1
1
0
1
2
3
4
k=5 5
6
7
1
2
3
4
k=5 5
6
7
1
2
0
3
3
0
4
6
6
4
8
6
10 8
13 11
1
0
3
4
6
8
10
9
2
3
0
6
4
6
8
7
3
4
6
0
2
4
6
9
3
4
6
0
2
4
6
5
4
6
4
2
0
2
4
7
4
6
4
2
0
2
4
3
5
8
6
4
2
0
6
1
5
8
6
4
2
0
6
1
6
7
10 13
8 11
6 9
4 7
6
1
0
1
1
0
6
10
8
6
4
6
0
1
51
7
9
7
5
3
1
1
0
1
2
3
4
5
k=6 6
7
1
0
3
4
6
8
10
9
2
3
0
6
4
6
8
7
3
4
6
0
2
4
6
5
4
6
4
2
0
2
4
3
5
8
6
4
2
0
6
1
6
10
8
6
4
6
0
1
7
9
7
5
3
1
1
0
1
2
3
4
5
6
k=7 7
1
0
3
4
6
8
10
9
2
3
0
6
4
6
8
7
3
4
6
0
2
4
6
5
4
6
4
2
0
2
4
3
5
8
6
4
2
0
6
1
6
10
8
6
4
6
0
1
7
9
7
5
3
1
1
0
1
2
3
4
5
6
7
1
0
3
4
6
8
10
9
2
3
0
6
4
6
8
7
3
4
6
0
2
4
6
5
4
6
4
2
0
2
4
3
5
8
6
4
2
0
2
1
6
10
8
6
4
2
0
1
7
9
7
5
3
1
1
0
52
負の閉路を含む最短路問題
２
１
２
－４
１
４
１
３
３
53
輸送問題
需要量
供給量
１０
工場P1
６
４
１５
工場P2
工場P3
１８
需要地M2
９
需要地M3
１２
需要地M3
１１
１
５
２５
需要地M1
６
３
２
５ ６
８
７
１０
枝上に輸送費
54
需給の一致しない輸送問題（ダミーの追加）
需要量
供給量
１０
６
工場P1
４
１５
工場P2
工場P3
６
２
５ ６
８
００
５
ダミー工場
１８
需要地M2
９
需要地M3
１２
需要地M3
１１
１
５
２０
需要地M1
３
７
０ １０
０
枝上に輸送費
55
変数の０－１制約、整数制約指定
EXCELソルバーでは制約条件の一部として指定
0-1変数
整数変数
56
０－１変数を含む
ソルバーパラメータ設定
57
施設配置問題
関東地方を中心に営業を行ってきた輸入品販売業の
Ｋ社では、関西地方に活動を拡大するため、京阪神地方
に倉庫の賃借を行う計画を立てている。賃借の候補とな
る倉庫はｍカ所にあって、第ｉ地点の倉庫Ｗｉ(i=1,･･･,m)の
月間処理能力はａｉ（トン／月）で、その経費（賃借料や維
持費など毎月の固定費）はｄｉ（千円／月）である。また、
関西一円に広がる消費地Ｄｊ(j=1,･･･,n)での輸入品の需
要量ｂｊ（トン／月）と、ＷｉからＤｊへのトン当たり輸送費ｃｉｊ
（千円）が与えられたとして、すべての需要を満たし、毎
月の総費用（倉庫経費＋輸送費）を最小にする倉庫配置
と輸送計画を求めたい。この問題を数理計画問題として
定式化せよ。
58
施設配置問題（p.100）
59
施設配置問題の定式化
• 定数：ｄi ＝ 倉庫ｉの経費（固定費）
ｃij ＝ 倉庫ｉからｊへの輸送単価
• 変数： ｙi ＝ 倉庫ｉを借りるとき１、さもなくば０
ｘij ＝ 倉庫ｉからｊへの輸送量（ｘij≧０）
• 目的関数（総費用最小）：
最小化 ｚ ＝ Σi ｄiｙi ＋ ΣiΣj ｃijｘij
制約
需要を満足しなければならない
倉庫を借りないならば、送り出してはいけない
60
施設配置問題の定式化
最小化
制約
ｚ ＝ Σi ｄiｙi ＋ ΣiΣj ｃijｘij
Σi ｘij≧ｂj
ｊ＝1,2,…,n
Σj ｘij≦ａｉｙi
ｉ＝1,2,…,m
ｘij≧０，ｙi ＝０ or １
61
補足： 輸送問題
ポテンシャル法による被約費用の計算
１．被約費用＝ｃij－（ｕi＋ｖj）
２．基底変数の被約費用＝０，から
ｍ＋ｎ－１本の連立方程式
変数はｍ＋ｎ個
どれか1個を適当に固定しｕi，ｖjを決定
３．非基底変数（非基底マス）に対して
被約費用＝ｃij－（ｕi＋ｖj）
62

Document

PowerPoint プレゼンテーション

Case study: the inventory vehicle routing for