12019/5/31

１

２

３

５

７ ６

４

1

7

2

5 1

2

8

3

4 3

先週の演習課題

ダイクストラ法を用いて最短路を求めよ

１

２

３

５

７ ６

４

1

7

2

5 1

2

8

3

4 3

1 8

0 3

1



2 2

ダイクストラ法の計算が終了したとき

4

10

4 6 3

6

各ノードから

p(i)

を遡って辿ると

１

２

３

５

７ ６

４

1

7

2

5 1

2

8

3

4 3

1 8

0 3

1



2 2

ダイクストラ法の計算が終了したとき

4

10

4 6 3

6

d(i)

始点１からノード

i

への最短距離を表す 始点１から各ノードへの最短路木が得られる

ダイクストラ法のまとめ

 最適性の原理に基づくシンプルな方法

 計算終了時には始点から各ノードへの最短 路と最短距離が求まっている

 計算量は

 １反復ごとに一つのノードが S に入る

 Step 1,2 で探索するノードの数は高々 n

 それぞれの枝が計算で用いられるのは１

回のみ

ネットワークシンプレックス法

 最短路問題，最大流問題，最小費用流問題 などはすべて LP に定式化できる

 定式化の方法

 特徴

最小費用流問題

各枝の容量と，１単位フローを流すときのコストが与えられたと き，各ノードでの需要量と供給量を満たすような最も費用の安 いフローを求めよ．

１

２

３

５

７ ６

４

(7,1)

(6,5)

(2,2)

(8,2)

(7,1)

(10,3)

(4,5)

(7,1)

(5,5) (7,2)

（容量，コスト） 0 ー8

10 0

3 0

ー5

供給量（需要量）

 供給量が正：ソース，供給節点 (supply)

（１，２）

 供給量が負：シンク，需要節点 (demand)

（７，６）

 供給量が０：通過ノード

（３，４，５）

LP への定式化

とおくと，目的関数は

合もある）

の容量（下限がある場 枝

良い）

の単位コスト（負でも 枝

を通るフロー 枝

) , ( :

) , ( :

) , ( :

j i u

j i c

j i x

ij ij

ij



j E i

ij ij

x c

) , (

min

制約条件

 容量制約

 フロー保存則

（ノードから出て行くフロー）

ー（ノードに入ってくるフロー）＝需要供給量 E

j i u

x

_ij



_ij





^

( , )

0

   

での需要供給量 ノード i

b

V i

b x

x

E i j j

i ji

E j i j

ij

:

) , ( )

, (







^









１

２

３

５

７ ６

４

(7,1)

(6,5)

(2,2)

(8,2)

(7,1)

(10,3)

(4,5)

(7,1)

(5,5) (7,2)

ー8 0

10 0

3 0

ー5

8 )

( :

0 )

( :

10 :

76 36

65

74 24

43

13 12



















x x

x

x x

x

x x

ノード６（需要点）

ノード４（通過点）

ノード１（供給点）

LP への定式化

, 10 0

, 6 0

, 2 0

, 8 0

, 7 0

5 8 0 0 0 3 10 s.t.

5 5

2 3

5 2

2 min

76 74

57

76 65

36

65 57

25

74 43

24

43 36

13

25 24

12

13 12

76 74

65 57

43 36

25 24

13 12































































































x x

x x

x

x x

x

x x

x

x x

x

x x

x

x x

x

x x

x

x x

x x

x x

x x

x x

x x

係数行列を

A

とおく

 

 

   

u x b

Ax x c A

b c

u

x x

x x

x x

x x

x x x







 

 

 

 







 

 

 

 









































0 , s.t.

min

1 1

1

1 1

1

1 1

1

1 1

1

1 1

1

1 1

1

1 1

5 , 8 , 0 , 0 , 0 , 3 , 10 ,

5 , 5 , 2 , 1 , 1 , 5 , 5 , 2 , 2 , 1

5 , 4 , 7 , 7 , 7 , 10 , 6 , 2 , 8 , 7

, ,

, ,

, ,

, ,

,

T

T T

T

T 76 74

65 57

43 36

25 24

13 12

とおくと

上下限付き線形計画問題

 

 

 

 







 

 

 

 



























1 1

1

1 1

1

1 1

1

1 1

1

1 1

1

1 1

1

1 1

（節点枝）接続行列

76 74

65 57

43 36

25 24

13

12

x x x x x x x x x

x

7 6 5 4 3 2 1

１

すべての行を足すと０になる

２ ３ ４

節 点

枝

基底行列をみつけるのが難しい

１

２

３

５

７ ６

４

(7,1)

(6,5)

(2,2)

(8,2)

(7,1)

(10,3)

(4,5)

(7,1)

(5,5) (7,2)

ー8 0

10 0

3 0

ー5

補助節点

(U,C)

(U,C) (U,C)

(U,C)

補助節点を作り，補助枝

供給点から補助節点への枝 補助節点から需要点への枝

を追加．枝の単位コスト

C

：十分大，容量

U

：十分大 とする







































































































































5 8 0 0 0 3 10

1 1

1 1

1 1

1 1

1 1

1

1 1

1

1 1

1

1 1

1 1

1 1

1

7 6 2 1 76 74 65 57 43 36 25 24 13 12

a a a a

x x x x x x x x x x x x x x

補助接点を含んだ接続行列

A’

はフルランク

補助枝のフロー

フルランクにするためには適当な行を消去するだけ でもよい（打ち切り接続行列という

)

 

 

 

 







 

 

 

 





























1 1

1

1 1

1

1 1

1

1 1

1

1 1

1

1 1

1

1 1

A

例えば，最下行を消すとフルランク

（ただしシンプレックス法には不向き）

 補助枝は，人為変数に対応 単位コストを十分大きく取る

補助枝以外のコスト＝０（二段階法）

→ シンプレックス法で最適解が求まる

→ 補助枝にフローがあれば実行不能

 接続行列の特徴

疎性＋完全ユニモジュラ性

により，実用上最も有効に解ける

逆行列の要素が０，±１

最大流問題の場合

１

２

３

５

７ ６

４

7

4

4

2 1

4

2

3

4 3

元の枝の単位コストはすべて０として最小費用流問題を解く 需要点，供給点がない：循環流問題

補助枝：単位コスト＝－１，容量無限大（十分大）

最大流最小カットの定理と LP

１

２

３

５

７ ６

４

7

4

4

2 1

4

2

3

4 3

S T

カット：ソース

1

を含むノード集合

S

とシンク

7

を 含むノード集合

T

に分割したもの

カット容量：

=

最大流最小カットの定理と LP

１

２

３

５

７ ６

４

7

4

4

2 1

4

2

3

4 3

S T

最大流最小カットの定理：

カット容量 の最小値は最大流と等しい

（これは

LP

の双対定理と同じである）

上の例は最小カット２＋１＋２＋３＝８（最大流）

組み合わせ的解法の計算量

節点数 n ，枝数 m とする．

 最短路問題

ダイクストラ法：

 最大流問題

Dinic (1970) ：

Goldberg, Tarjan(1986) ：

  ⁿ

²

^{O   m O}   ⁿ

²

O  

  ^{n m}

O

²

 

 ^{mn n m} 

O log

²

 最小費用流

Tardos (1985) ：

Goldberg, Tarjan (1987) ：

（強）多項式時間アルゴリズム：

計算時間が，節点数と枝数の多項式

ネットワークシンプレックス法は多項式アルゴリ ズムではないが，実用上早い

 ^{nm n n m} 

O

²

log

²



³

 

 ^{nm n n m} 

O

²

log log

²

演習課題

1. ダイクストラ法は負のコストを持つ枝があるとうまくいかないことがある．

そのような例を示せ．ただし，負閉路を持ってはいけない．

2. 以下の最短路問題（１から７までの最短路を求めよ）をLPに定式化せよ．

また，LPの最適性条件を用いて，得られた経路が最短路であることを示せ．

１

２

３

５

７ ６

４

1

7

2

5 1

2

8

3

4 3