オペレーションズリサーチA 第8回ネットワーク最適化 11/27 椎名孝之 • 授業サポートページ 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 最短路問題：双対問題   s.t .       5    2    1    3    2    6 max 4 1 2 0 2 1 4 1 1 2 3 2 4 3 • πj-πi≦cij 0 0  10 • 点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 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 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 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 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 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 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*)とする（us*=1としてよい） •完全単模性より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 実行例１ 0/5 （∞,□） 1 (5,1+) 0/6 (5,3+) 0/5 (7,1+) 2 0/7 0/5 （∞,□） 1 (6,2+) (6,4+) 6 1 6 2 4 0/6 0/6 5 4 (5,1+) 0/6 (5,3+) 3 5 0/5 (1,1+) 6/7 4/5 （∞,□） 3 5 0/4 3 1 2 (5,3+) 6/6 3 (4,5+) 6 4 6/6 5 1 6 2 4 (1,1+) 4/6 (1,3+) 5 4/4 3 0/5 (1,1+) 6/7 0/4 2 6/6 (1,3+) 6 4 6/6 22 実行例２ 0/5 1 （∞,□） (5,1+) 0/6 (5,2+) 0/5 3 1 5/5 3 3 5/5 （∞,□） 1 (1,4+) 5 1 4 5/6 0/6 4 6 3 4 2 5 (5,4-) 0/6 (5,2+) 5 0/4 2 5/5 (6,1+) 1/7 5/5 （∞,□） 2 6 (6,3+) (7,1+) 0/7 6 4 0/6 0/6 (5,4-) 0/6 (5,2+) 5/5 2 5 0/4 （∞,□） 5 1 (5,4+) 6 (5,2+) (7,1+) 0/7 2 5 0/4 2 1 3 1/6 (5,3+) (4,5+) 4 6/6 1 6 3 4 (1,4-) 4/6 (1,2+) 5 4/4 2 1/5 (2,1+) 5/7 6 3 5/6 (1,3+) 4 6/6 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 iX , jX ij  x iX , jX ij   h iX , jX ij ( xij  hij ならば　jにラベルがつくはず）  0 ( xij  0ならば iにラベルがつくはず） 24