ダイクストラ法のまとめ最適性の原理に基づくシンプルな方法計算終了時には始点から各ノードへの最短路と最短距離が求まっている計算量は１反復ごとに一つのノードが S に入る Step 1,2で探索するノードの数は高々 n それぞれの枝が計算で用いられるのは１回のみ + = 2015/5/22 10 ネットワークシンプレックス法最短路問題，最大流問題，最小費用流問題などはすべてLPに定式化できる定式化の方法特徴 2015/5/22 11 最小費用流問題各枝の容量と，１単位フローを流すときのコストが与えられたとき，各ノードでの需要量と供給量を満たすような最も費用の安いフローを求めよ． (7,1) 10 １ (8,2) （容量，コスト） 3 ２ (2,2) (7,1) ３ 0 ４ (10,3) 0 0 (6,5) ５ (7,1) (4,5) ７ー5 (7,2) (5,5) ６ー8 供給量（需要量） 2015/5/22 12 供給量が正：ソース，供給節点(supply) （１，２）供給量が負：シンク，需要節点(demand) （７，６）供給量が０：通過ノード（３，４，５） 2015/5/22 13 LPへの定式化 xij : 枝(i, j )を通るフロー cij : 枝(i, j )の単位コスト（負でも良い） uij : 枝(i, j )の容量（下限がある場合もある）とおくと，目的関数は min cij xij (i , j ) E 2015/5/22 14 制約条件容量制約 0 xij uij (i, j ) E フロー保存則（ノードから出て行くフロー）ー（ノードに入ってくるフロー）＝需要供給量 xij j (i , j ) E x ji bi i V j ( j ,i ) E bi : ノード i での需要供給量 2015/5/22 15 (7,1) 10 １ (8,2) 3 ２ (2,2) (7,1) ３ 0 (6,5) 0 ４ (10,3) 0 ノード１（供給点）: x12 ５ (7,1) (4,5) ７ー5 (7,2) (5,5) ６ー8 x13 10 ノード４（通過点）: x43 ( x24 x74 ) 0 ノード６（需要点）: x65 x76 ) 2015/5/22 ( x36 8 16 LPへの定式化 min x12 2 x13 2 x24 5 x25 3 x36 s.t. x12 x13 x12 x24 x57 2 x65 5 x74 5 x76 10 係数行列をAとおく x25 x13 x43 x36 x24 3 x43 0 x43 x25 x74 x57 x36 0 x65 0 x65 x57 x74 0 x12 7, 0 x13 8, 0 x24 2, 0 x25 6, 0 x36 10, 0 x43 7, 0 x57 7 ,0 x65 7, 0 x74 4, 0 x76 2015/5/22 x76 8 x76 5 5 17 x x12 , x13 , x24 , x25 , x36 , x43 , x57 , x65 , x74 , x76 u 7,8,2,6,10,7,7,7,4,5 T c 1,2,2,5,5,1,1,2,5,5 T , 1 1 b T 10,3,0,0,0, 8, 5 T 1 1 1 1 A 1 1 1 1 1 1 1 1 1 1 1 1 1 1 とおくと min c T x s.t. Ax b, 0 2015/5/22 x u 上下限付き線形計画問題 18 （節点枝）接続行列 x12 x13 x24 枝 x25 x36 x43 x57 x65 x74 節点 1 1 1 1 1 2 1 1 1 1 3 4 1 1 1 5 1 1 1 6 1 1 7 基底行列をみつけるのが難しい 1 1 x76 １ 2015/5/22 1 1 ４３すべての行を足すと０になる２接続行列はフルランクではない 19 (7,1) 10 １ 3 ２ 0 (2,2) (7,1) (8,2) (U,C) (U,C) ３ 0 (6,5) ５ (4,5) ４７ー5 (7,2) (10,3) 0 (7,1) (U,C) (5,5) ６ー8 (U,C) 補助節点補助節点を作り，補助枝供給点から補助節点への枝補助節点から需要点への枝を追加．枝の単位コストC：十分大，容量U：十分大とする 2015/5/22 20 x12 補助接点を含んだ接続行列A’はフルランク 1 1 1 x13 x24 x25 1 1 1 1 x36 x43 x57 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 補助枝のフロー 2015/5/22 x65 x74 x76 x1a x2 a xa 6 10 3 0 0 0 8 5 xa 7 21 フルランクにするためには適当な行を消去するだけでもよい（打ち切り接続行列という) 1 1 1 1 1 1 A 1 1 1 1 1 1 1 1 1 2015/5/22 1 1 1 1 例えば，最下行を消すとフルランク（ただしシンプレックス法には不向き） 1 22 補助枝は，人為変数に対応単位コストを十分大きく取る補助枝以外のコスト＝０（二段階法） →シンプレックス法で最適解が求まる →補助枝にフローがあれば実行不能逆行列の要素が０，±１接続行列の特徴疎性＋完全ユニモジュラ性により，実用上最も有効に解ける 2015/5/22 23 最大流問題の場合 7 １ 4 ２ 4 ４５ 2 1 2 ３ 3 4 ７ 3 ６ 4 補助枝：単位コスト＝－１，容量無限大（十分大）元の枝の単位コストはすべて０として最小費用流問題を解く需要点，供給点がない：循環流問題 2015/5/22 24 最大流最小カットの定理とLP S １ 7 4 ２ 4 ４ 1 2 ３ 4 ５ T 3 2 ７ 3 ６ 4 カット：ソース 1 を含むノード集合 S とシンク 7 を含むノード集合 T に分割したものカット容量： , =∑( , )∈( , ) 上の例では２＋４＋３＝９ 2015/5/22 25 最大流最小カットの定理とLP S １ 7 4 ２ 4 ４ 1 2 ３ 4 ５ T 3 2 ７ 3 ６ 4 最大流最小カットの定理：カット容量 , の最小値は最大流と等しい（これはLPの双対定理と同じである）上の例は最小カット２＋１＋２＋３＝８（最大流） 2015/5/22 26 組み合わせ的解法の計算量節点数 n，枝数 m とする．最短路問題ダイクストラ法： O n 2 O m 最大流問題 Dinic (1970)： O n 2 m Goldberg, Tarjan(1986)： 2015/5/22 O n2 O mn log n 2 m 27 最小費用流 Tardos (1985)： O nm 2 log 2 n n3m Goldberg, Tarjan (1987)： O nm 2 log n log n 2 m （強）多項式時間アルゴリズム：計算時間が，節点数と枝数の多項式ネットワークシンプレックス法は多項式アルゴリズムではないが，実用上早い 2015/5/22 28 演習課題最短路問題をＬＰに定式化するにはどうすればよいか？ 2. 前問の方法を用いて，以下の最短路問題（１から７までの最短路を求めよ）をLPに定式化せよ．また，LPの最適性条件を用いて，最短路であることを示せ． 1. 1 １ 7 ２ 2 ４ 1 5 ３ 2 ５ 3 8 ７ 3 ６ 4 締め切り:5月28日(木)12時 Ⅳ系事務室まで 2015/5/22 29