OR-A 第11回(2007/12/21) ネットワーク理論

オペレーションズリサーチA
第8回ネットワーク最適化
11/26 椎名孝之
• 授業サポートページ
http://www.morito.mgmt.waseda.ac.jp/ora/
• ソフトウェアAMPL+CPLEX(非常に有用)
• 質問は [email protected]
• 最短路問題
• 最大流問題
1
ネットワークに関する定義
• 有向グラフ G=(V, A)を考える(V:点集合、A:辺集
合)
• 各辺(i, j) ∈Aに対して辺容量hij が与えられている
• 各点i ∈Vに対してbi が与えられている( bi >0 なら
ば需要量、 bi <0ならば供給量)
• xij は辺(i, j)上のフロー(流量)を表す
• V+(i)={k: (i,k)∈A} 点i から出る辺の終点集合
• V-(i)={k: (k,i) ∈A} 点i に接続する辺の始点集合
2
最小費用流問題
• 定式化
min
c x
( i , j ) A
ij
subject t o
ij
x
kV ( i )
ki

x
kV ( i )
0 x  h
ij
V -(i)
ij
ik
 bi , i  V
, (i, j )  A
V+(i)
i
流量保存則
bi
3
ネットワークの例
• 流量保存則
 x12  x13
 10, 点1への供給量 10
 x24
 0, 点2への流入量=流出量 供給量10, b =-10
x12
1


0
,
点
3
への流入量=流出量
x13
x34
x24  x34  10,点4での需要量10
  1  1 0 0  x12    10




3
1


1
0

1
0
0

 x13 




 0 1 0  1
 0 

 x24  

 0 0 1 1 



10

 x34  

接続行列
2
4
需要量10, b4=10
4
接続行列の性質
• 線形計画問題として定式化
• b,hが整数ベクトルならば最適解は必ず整数解
• 接続行列:完全単模性を持つ(任意の小行列式
が0,-1,1のどれかに等しい (totally unimodular)
• クラメルの公式:
基底解 xB=B-1b=(1/det B)(adj B)b の分母が-1ま
たは1⇒整数性
5
最短路問題(Shortest Path Problem)
• ネットワーク上の点s(始点;ソース)から点t
(終点;シンク)までの最短路
min  c x
( i , j ) A
ij
subject t o
ij
x
ki
x
ki
kV  ( i )
kV ( i )
x
kV  ( i )
ki
0 x
ij

x
kV  ( i )

x
kV ( i )

ik
x
kV  ( i )
ik
ik
 1, i  s
 0, i  V \ {s, t}
 1, i  t
, (i, j )  A
最適解はxij∈{0,1}
6
最短路問題の双対問題
 
 
max t 
subject t o
s
j
i
 cij , (i, j )  A
•任意のaについてπiをπi+a と置き換えても実行
可能⇒ 始点でπs=0と定める
•πiとは?⇒始点sから点iへの最短距離の下界
•πiをsからiへの最短距離と定めると双対問題の
実行可能解なので、双対問題を解いてもsからt
への最短距離が求められることがわかる
7
最短路問題:主問題
• 辺上の数字は辺の長さ
10
0
5
1
1
3
4
6
2
2
3
2
min 10 x01  5 x02  2 x12  x14  3 x21  2 x23  6 x34
s.t. - x01 - x02
 -1
- x12 - x14  x21
0
x01
- x21 - x23
0
x02  x12
x23 - x34  0
 x34  1
x14
xij  0, (i, j )  A
8
最短路問題:双対問題
• πj-πi≦cij
• 点j までの最短路の距離
≦
(点iまでの最短路の距離
+(i, j) 間の距離)
9
Dijkstra(ダイクストラ)法
•
•
ステップ1 : π0=0, πi=∞ (i∈V-{0}),
M={1,2,...,n}, i=0
ステップ2 : M≠φ(空集合)でない場合(i)(ii)(iii)
を繰り返す
(i) j∈Mに対しπj >πi+cijならばπj =πi+cij , pj=i
(ii) min j∈M πj = πk となるkを求める
(iii) kをMから除く、i=k とする
•M:最短路未確定な点の集合
•集合Mから削除されると最短路確定
•pj:点 jへの最短路の直前点(終了時)
10
最短路問題:演習
• 辺上の数字は辺の長さ
π3= ∞
π1= ∞
15
1
30
50
π0= 0
3
10
20
80
0
ステップ1:
π0=0, πi=∞, (i∈M),
M={1,2,3,4}
点0のみ最短路確定
i=0 よりスタート
15
2
π2= ∞
4
π4= ∞
11
π1= ∞⇒
3
30
20
80
π0= 0
15
1
50
0
π3 = ∞
10
2
π2= ∞⇒
15
4
π4 = ∞
ステップ2(1回目):i=0, M={1,2,3,4}
(i) M={1,2,3,4}に到達する直前点を可能なら仮に i=0とする
j=1については
なのでπ1=
, p1=
.
j=2については
なのでπ2=
, p2= .
j=3,4については、直接i=0と接続していないのでそのまま
(ii) minj∈M πj ={π1, π2, π3, π4 } =
.
点k= の最短路確定: 点 に到達する直前点が i=0となる
(iii) k= をMから削除し、i= より再びステップ2を行う
12
π1= ∞⇒50
3
30
20
80
π0= 0
15
1
50
0
π3= ∞⇒
10
2
π2= ∞⇒80⇒
15
4
π4 = ∞
ステップ2(2回目):i=1, M={2,3,4}
(i) M={2,3,4}に到達する直前点を可能なら仮に i=1とする
j=2については
なのでπ2=
, p2= .
j=3については
なのでπ3=
, p3= .
j=4については、直接i=1と接続していないのでそのまま
(ii) minj∈M πj ={π2, π3, π4 } =
.
点k= の最短路確定: 点
に到達する直前点が i=1となる
(iii) k= をMから削除し、i= より再びステップ2を行う
13
π1= ∞⇒50
3
30
20
80
π0= 0
15
1
50
0
π3= ∞⇒65
10
2
15
π2= ∞⇒80⇒70
4
π4= ∞⇒95
ステップ2(3回目):i=3, M={2,4}
(i) M={2,4}に到達する直前点を可能なら仮に i=3とする
j=2については、直接i=3と接続していないのでそのまま
j=4については
なのでπ4
, p4= .
(ii) minj∈M πj ={π2, π4 } =
.
点k= の最短路確定:
に到達する直前点が i=1となる
(iii) k= をMから削除し、i= より再びステップ2を行う
14
π1= ∞⇒50
3
30
20
80
π0= 0
15
1
50
0
π3= ∞⇒65
10
2
15
π2= ∞⇒80⇒70
4
π4= ∞⇒95⇒
ステップ2(4回目):i=2, M={4}
(i) M={4}に到達する直前点を可能なら仮に i=2とする
j=4については
なのでπ4=
, p4= .
(ii) minj∈M πj ={π4 } = π4
点k=
の最短路確定:
に到達する直前点が i=2となる
(iii) k=
をMから削除するとMは空集合になるため、最短路
が得られた
15
最大流問題(Max Flow Problem)
• 始点(ソース)sから終点(シンク)tへのフロー
vの最大化
• 辺(i,j)の容量hij
max
v
subject t o
x
kV ( i )
x
kV ( i )
x
kV ( i )
ki
ki
ki

x
kV ( i )


x
kV ( i )
x
kV ( i )
0 x  h
ij
ij
ik
ik
ik
 v, i  s
 0, i  V \ {s, t}
 v, i  t
, (i, j )  A
16
最大フロー最小カット定理
•
•
•
•
•
始点(ソース)s、終点(シンク)t
s を含みtを含まない任意の点集合:X
t を含みXに含まれない点集合:X-=V-X
辺集合{(i,j)| i ∈X, j ∈ X-}をカット(X, X-)
カット容量 ∑i ∈X, j∈X- hij
 h
v
i X , j X
ij
(
LP弱双対性定理)
 h (双対性+完全単模性)
max v  min
i X , j X
5
6
2
ij
(手続的証明:ラベリ
ング法)
5 4
5
1
7
カット容量12
3
6
6
X
X-
4 6
カット容量10
17
最大流問題の双対問題
min
h w
( i , j ) A
ij
ij
subject t ou i  u j  wij  0, (i, j )  A
u  u  1,
w  0, u は符号制約無し
s
ij
t
j
•始点sを含む点集合X, 終点tを含む点集合X-に対して
•ui=1, i∈X
•uj=0, j∈X-
•wij=1, i∈X, j∈X- それ以外wij= 0
•上のように定めると双対問題の実行可能解が得られる
•全てのケースで実行可能性が確認できる
•{i ∈X, j ∈X}, {i ∈X, j ∈X-}, {i ∈X -, j ∈X},{i ∈X-, j ∈X-}
•双対問題における上の実行可能解に対する目的関数値
⇒カット容量と一致する
 hij wij   hij
( i , j )A
iX , jX
18
最大流問題:完全単模性
•双対問題の最適解を(u*,w*)とする
•完全単模性よりu* の各成分は1以上または0以下
•X={i ∈V: ui* ≧1}, X-=V-X= {j ∈V: uj* ≦0}とする
•i ∈X, j ∈X -に対してwij* ≧ui* -uj*≧1
•目的関数の下界は次のように計算できる
h w
( i , j )A
ij
ij


( i , j )A,iX , jX
hw
ij
ij


( i , j )A,iX , jX
h
ij
•双対問題の次の実行可能解に対する目的関数値は
下界と一致⇒最小カット
•ui=1, i∈X
•uj=0, j∈X-
•wij=1, i∈X, j∈X- それ以外wij= 0
19
Ford-Fulkerson法
• 残余ネットワーク: フローxijに対して容量hij -xij
の辺(i,j)と容量xijの辺(j,i)を考える
容量hij-xij
容量hij
i
フロー xij
j
i
j
容量 xij
•ソースsからシンクtへフローxが流れるとき、
残余ネットワークを考える。
•残余ネットワークでsからtへの路を見つける。
•路の上の最小容量=εをxに加える
20
ラベリング法
各点i∈Vはラベル(αi,βi)=(増加可能量,s→iの路の直前点)を
持つ
• ステップ1 xij=0, (i,j)∈A
• ステップ2 X={s}, αs=∞, αi =0∀i ∈V-{s}
• ステップ3 次の(i),(ii)の走査が完了していないラベルのつい
た点i∈X, およびiに接続する全てのラベルなしの点 j∈X-=V
-Xに対して(i),(ii)の走査手続を行い i を走査済とする
(i) xij <cij ならばj∈X-にラベル(αj,βj) =(min{αi, cij-xij }, i+)をつけ
X=X∪{j} (jにラベルはつくが、走査未完了)
(ii) xji >0ならばj∈X-にラベル(αj,βj) =(min{αi, xji }, i-)をつけ
X=X∪{j} (jにラベルはつくが、走査未完了)
ラベルのついた全ての点i∈Xに(i),(ii)の走査手続を繰り返
したとき、シンク t にラベルがつく(t∈X)ならば、ステップ4へ。
それ以外の場合は終了。
• ステップ4 シンク t からラベルβtをたどり、流量αtを増加させ
る。全てのラベルを削除しステップ2へもどる。
21
実行例1
0/5
(∞,□)
6
0/5
/5
2
4 0/6
0/6
/6
3
5
1
/4
6
/5
/7
/5
(∞,□)
5 0/4
3
1
0/7
(∞,□)
0/6
2
4
/6
/6
/6
3
1
5
/4
6
/5
/7
2
/6
4
/6
22
実行例2
0/6
0/5
1
(∞,□)
0/7
3
/5
2
3
5 /4
6
4 /6
/6
/6
/5
2
1
/4
5
6
/5
3
/7
/5
(∞,□)
4 0/6
0/6
/6
/5
/7
(∞,□)
6
0/5
1
(∞,□)
5 0/4
2
4
/6
/6
/6
2
1
5
/4
6
/5
/7
3
/6
4
/6
23
ラベリング法終了時
• s を含みtを含まない任意の点集合:X
• t を含みXに含まれない点集合:X-=V-X
• カット{(i,j)| i ∈X, j ∈ X-}
v
 x  x
iX , jX
ij
iX , jX
ij

 h
iX , jX
ij
•ステップ3より、X(ラベルのついた点集合)および
X-に対して次の関係が得られる
 x  h
 x 0
iX , jX
iX , jX
ij
iX , jX
ij
ij
24