「基礎OR」/「OR演習」
第5回
10/27/2015
森戸 晋
1
中間試験のお知らせ
• 中間試験日程
2015/11/10(火)
• 時間: 13:00~14:30(3限)
• 場所
– 56-103,56-102教室 (座席指定制)
• 001~070まで 56-103教室
• 071~ (過年度を含む) 56-102教室
• 11/10の4限は招聘講師による特別講義
NTTデータ数理システム(株) 田辺隆人先生
2
ネットワーク上の最適化
(ネットワーク計画)の
代表的問題
3
最短路問題
1
10
始
s
点
終
t
点
1
3
2
5
6
2
2
3
各枝の数字は、枝の距離(費用)を表す
4
最大流問題
1
8
5
v
s
t
v
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
(1)
s
3
2
(1)
(1)
1
6
(1)
5
(1)
t
(1)
終点
2
2
(1)
3
各枝の数字は、各点間の距離(費用)、
( )内の数字は、各枝の容量を表す
7
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
(閉路を構成しない、連結な枝の集合)を選ぶ問題
2
1
10
1
5
4
3
6
5
3
2
4
各枝の数字は、各点間の距離(費用)
8
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
(閉路を構成しない、連結な枝の集合)を選ぶ問題
2
1
10
1
5
4
3
6
5
3
2
4
木ではない: 連結していない
9
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
(閉路を構成しない、連結な枝の集合)を選ぶ問題
2
1
10
1
5
4
3
6
5
3
2
4
木ではない: 閉路が存在する
10
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
(閉路を構成しない、連結な枝の集合)を選ぶ問題
2
1
10
1
5
4
3
6
5
3
2
4
すべての点を張らない木
11
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
(閉路を構成しない、連結な枝の集合)を選ぶ問題
2
1
10
1
5
4
3
6
5
3
2
4
すべての点を張る木(全域木)
12
最小木問題
無向グラフ上で、すべての点を張る最小コストの木
(閉路を構成しない、連結な枝の集合)を選ぶ問題
2
1
10
1
5
4
3
6
5
3
2
4
各枝の数字は、各点間の距離(費用)
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
構築法と改善法
• 構築法
解の存在しない状態から、順次、解を作成し
ていく解法
例:貪欲解法(最小木問題に対するKruscal
法やPrim法など)
• 改善法
与えられた実行可能解から出発して、順次、
よりよい解を見つけていく解法
例:局所探索法(最小木問題に対する改善
法、線形計画問題に対する単体法など)
32
最短路問題
(sからtへの最短路を求める)
枝の「距離」
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
ダイクストラ法(0)
∞
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点間の最短路dij ← min{dij,dik+dkj}
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=[dij]
• 点 j に関する三角オペレーション
dij ← min{dij,dik+dkj}
for all i, j=1,…,n; i, j ≠ k
k
i
j
47
Warshall-Floyd法のアルゴリズム
任意の2点間の最短路
• 元々の距離行列 C=[cij]
• 初期化
for all i ≠j do dij ← cij
for i =1,…,n do dii ← 0
• 基本部分
for k =1,…,n do
for i =1,…,n ; i ≠ k do
for j =1,…,n ; j ≠ k do
dij ← min{dij,dik+dkj}
48
任意の2点間の最短路dij ← min{dij,dik+dkj}
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
負の閉路を含む最短路問題
2
1
2
-4
1
4
1
3
3
53
輸送問題
需要量
供給量
10
工場P1
6
4
15
工場P2
工場P3
18
需要地M2
9
需要地M3
12
需要地M3
11
1
5
25
需要地M1
6
3
2
5 6
8
7
10
枝上に輸送費
54
No.0(元問
題)
需要地
M1
6
需要地
M2
4
需要地
M3
3
需要地
M4
供給量
7
工場P1
10
1
5
6
2
工場P2
25
5
6
8
10
工場P3
15
需要量
No.0(北西
隅法)
18
9
12
11
需要地
M1
需要地
M2
需要地
M3
需要地
M4
6
工場P1
4
3
7
10
10
1
工場P2
5
8
5
6
9
6
18
2
9
25
8
8
工場P3
需要量
供給量
10
4
11
12
11
15
55
No.0(北西
隅法)
需要地
M1
需要地
M2
6
工場P1
需要地
M3
4
需要地
M4
3
7
10
10
1
工場P2
5
8
6
9
5
2
25
8
6
8
工場P3
2
10
4
11
18
9
12
11
No.1
需要地
M1
需要地
M2
需要地
M3
需要地
M4
6
15
-1
需要量
工場P1
供給量
4
3
供給量
7
10
10
-6
1
工場P2
5
8
6
5
5
6
工場P3
2
8
10
4
11
3
需要量
25
12
18
1
9
12
11
15
56
No.2
需要地
M1
需要地
M2
6
工場P1
4
5
需要地
M4
3
供給量
7
10
5
1
工場P2
需要地
M3
5
6
13
2
25
12
6
5
6
工場P3
8
10
4
11
15
-3
需要量
18
9
12
11
No.3
需要地
M1
需要地
M2
需要地
M3
需要地
M4
6
工場P1
4
1
3
供給量
7
10
9
-8
1
工場P2
5
6
13
5
4
需要量
18
25
12
6
工場P3
2
8
10
11
9
12
11
15
57
No.4
需要地
M1
6
需要地
M2
需要地
M3
4
工場P1
3
9
1
工場P2
需要地
M4
7
10
1
5
6
14
供給量
2
25
11
-2
5
6
工場P3
4
需要量
18
No.5
9
12
需要地
M2
4
3
需要地
M4
供給量
7
10
10
1
工場P2
5
14
5
6
9
2
25
2
6
8
10
4
18
15
11
-3
需要量
15
11
需要地
M3
工場P1
工場P3
10
11
需要地
M1
6
8
9
12
11
58
No.6
需要地
M1
需要地
M2
6
需要地
M3
4
需要地
M4
3
工場P1
供給量
7
10
10
8
1
工場P2
2
5
18
6
5
2
25
2
-7
5
6
工場P3
8
10
4
3
1
需要量
18
9
12
11
No.7
需要地
M1
需要地
M2
需要地
M3
需要地
M4
6
15
11
4
3
工場P1
供給量
7
10
10
8
1
工場P2
5
6
18
2
2
5
25
6
15
7
5
6
工場P3
8
10
9
-4
需要量
18
9
12
11
59
No.8
需要地
M1
需要地
M2
6
需要地
M3
4
需要地
M4
3
工場P1
7
10
10
8
1
工場P2
8
5
6
12
工場P3
2
2
5
6
6
25
11
8
10
15
9
-2
4
需要量
18
9
12
11
No.9
需要地
M1
需要地
M2
需要地
M3
需要地
M4
6
4
3
工場P1
供給量
7
10
10
6
1
工場P2
3
5
6
6
2
14
5
6
4
25
11
3
工場P3
供給量
2
8
9
10
15
2
4
需要量
18
9
12
11
60
No.0(ハウ
ザッカー
需要地
M1
需要地
M2
6
需要地
M3
4
需要地
M4
3
工場P1
供給量
7
10
10
3
1
工場P2
5
2
6
2
18
7
5
6
工場P3
7
25
15
6
8
10
9
2
4
-4
需要量
18
9
12
11
No.1'(最
適)
需要地
M1
需要地
M2
需要地
M3
需要地
M4
6
4
3
工場P1
7
10
10
6
1
工場P2
3
5
6
6
2
14
5
6
4
25
11
3
工場P3
供給量
2
8
9
10
15
2
4
需要量
18
9
12
11
61
需給の一致しない輸送問題(ダミーの追加)
需要量
供給量
10
6
工場P1
4
15
工場P2
工場P3
6
2
5 6
8
00
5
ダミー工場
18
需要地M2
9
需要地M3
12
需要地M3
11
1
5
20
需要地M1
3
7
0 10
0
枝上に輸送費
62
施設配置問題
関東地方を中心に営業を行ってきた輸入品販売業の
K社では、関西地方に活動を拡大するため、京阪神地方
に倉庫の賃借を行う計画を立てている。賃借の候補とな
る倉庫はmカ所にあって、第i地点の倉庫Wi(i=1,・・・,m)の
月間処理能力はai(トン/月)で、その経費(賃借料や維
持費など毎月の固定費)はdi(千円/月)である。また、
関西一円に広がる消費地Dj(j=1,・・・,n)での輸入品の需
要量bj(トン/月)と、WiからDjへのトン当たり輸送費cij
(千円)が与えられたとして、すべての需要を満たし、毎
月の総費用(倉庫経費+輸送費)を最小にする倉庫配置
と輸送計画を求めたい。この問題を数理計画問題として
定式化せよ。
63
施設配置問題(p.100)
64
施設配置問題の定式化
• 定数:di = 倉庫i の経費(固定費)
cij = 倉庫i から需要地 j への輸送単価
ai = 倉庫i を借りた場合の供給能力
bj = 需要地 j の需要量
• 変数: yi = 倉庫i を借りるとき1、さもなくば0
xij = 倉庫i からj への輸送量(xij≧0)
• 目的関数(総費用最小):
最小化 z = Σi diyi + ΣiΣj cijxij
制約
需要を満足しなければならない
倉庫を借りないならば、送り出してはいけない
65
変数の0-1制約、整数制約指定
EXCELソルバーでは制約条件の一部として指定
0-1変数
整数変数
66
0-1変数を含む
ソルバーパラメータ設定
67
ダウンロード

第5回授業 スライド