<数理計画モデル>
・線形計画問題
・ネットワーク計画問題
・非線形計画問題
・組合せ計画問題
<輸送問題>
A社は2つの工場A1,A2で製品を生産し、3
つの取引先B1,B2,B3に納入している。
注文量
B1
B2
B3
70
40
60
生産量
A1
A2
90
80
輸送コスト
B1 B2 B3
A1 4 7 12
A2 11 6 3
<変数>
xij:工場Aiから取引先Bjへの輸送量
(i= 1,2 ; j= 1,2,3)
<制約条件>
x11 + x12 + x13 = 90
x21 + x22 + x23 = 80
x11 + x21 = 70
x12 + x22 = 40
x13 + x23 = 60
工場A1,A2
での生産量
取引先B1,B2,B3
の注文量
xij ≧0 (i= 1,2 ; j= 1,2,3) 輸送量の非負条件
<目的関数>
4x11 + 7 x12 + 12 x13 + 11x21 + 6x22 + 3x23
輸送コストの総和が最小となるようにする
90 A1
80 A2
x11
x12
x21
x22
B1
-70
B2
-40
x13
x23
輸送ネットワーク
B3 -60
ネットワークモデル
<グラフとネットワーク>
点:節点,ノード
矢印:枝,アーク
2
枝(i,j):節点iから節点jへの枝
V:節点全体の集合
E:枝全体の集合
4
1
V={1,2,3,4}
3
有向グラフ
E={(1,2), (1,3), (2,4),
(3,2),(3,4),(4,2)}
ネットワーク計画
線形計画問題の特別な場合
・最小木問題
・最短路問題
・最長路問題(PERT:日程計画)
・最大流問題
・最小費用流問題
・マッチング問題(割当問題)
最小木問題
木:閉路を含まない連結グラフ
最小木:長さ最小の全域木
ai :枝eiの長さ
<クラスカル法>
J.B.Kruskal (1956)
(0) グラフGの枝を短い順に並べ、 a1 ≦ a2 ≦
・・・ ≦ amを満たすように枝eiの番号(添字)
を付けかえる. T:={e1},k :=2 とおく.
(1) 枝集合T∪{ek}が閉路を含まないならば、
T:=T∪{ek} とする.
(2) TがGの全域木になっていれば計算終了.
さもなければ k :=k+1 としてステップ(1)へ.
欲張り法(Greedy Algorithm)
最短路問題
7
B
5
4
2
2
A
4
C
E
3
5
1
D
2
3
6
8
F
路の例:A→C→D→E→F→G
G
2
<最適性の原理>
P:節点sからtへの最短路
最短路Pのどの一部分を取り出しても,その
両端の節点間の最短路になっている.
aij:枝(i,j)の長さ
d(i):節点sから節点iへの最短路の
長さの上限値
p(i):節点sから節点iへの最短路において
節点iの直前に位置する節点
<ダイクストラ法>
E.Dijkstra (1959)
(0) S:=φ , S:=V , d(s):=0 ,
d(i):=∞ (i∈V-{s})とおく.
(1) S=Vなら計算終了.そうでないなら,
d(v)=min{d(i)|i∈ S} である節点v∈ Sを選ぶ.
(2) S:=S ∪{v}, S:= S -{v})とする.
d(j)> d(v)+ avj ならば d(j) := d(v)+ avj
((v,j) ∈E,j∈S)
p(j):= v とし,ステップ(1)へ.
<計算の複雑さ>
計算量:アルゴリズムは停止するまでに実行
される演算の総数
大きさNの問題をf(N)回の演算で解くこと
ができる
計算量O(f(N))
f(N)がNのべき乗で表される
多項式時間アルゴリズム
f(N)が2 NやN!
指数時間アルゴリズム
<多項式時間アルゴリズム>
大規模な問題に対しても効率的である
<指数時間アルゴリズム>
計算量が爆発的に増加
多項式時間アルゴリズムが存在する問題
クラスPに属する
多項式時間(polynomial time)
NP困難な問題:多項式時間アルゴリズムの存在が知られ
ていない
非決定計算による多項式時間(nondeterministic polynomial time )
<ダイクストラ法の計算量>
アルゴリズムの反復回数:節点数 n
ステップ(1):O(n2)
ステップ(2):O(m)
(m:枝数)
アルゴリズム全体の計算量:O(n2 + m)= O(n2)
m ≦n2
最長路問題
アサイクリックグラフ:閉路を含まない有向グラフ
7
B
5
4
2
A
4
E
5
1
D
C
G
3
6
8
3
F
計算量:O(|V|+|E|)
2
<PERT:日程計画>
PERT(program evaluation and review technique)
プロジェクトなどの工程管理
作業名
A
B
C
D
E
F
G
H
I
J
K
先行作業
-
-
A
A
C
B
F
D, E ,G
H
H
I, J
所要日数
1
1
1
3
2
1
1
7
1
2
1
アメリカ海軍のポラリス
潜水艦開発計画
D.G.Malcolm ら
(1950年代後半)
<プロジェクト・ネットワーク>
4
F,1
8
5
B,1
G,1
0
6
D,3
A,1
1
3
E,2
9
7
H,7
2
C,1
I,1
J,2
10
K,1
最早時刻= 点0からの最長路の長さ
2 最早時刻
3 最遅時刻
1
2
0
0
4
1
8
1
0
1
1
2
1
1
6
3
1
13
5
1
1
12
7
3
9
7
2
10
1
4
11
13
14
4
11
13
14
2
2
4
2
4
クリティカルパス
(臨界路)
18
5
7
B
5
4
2
A
4
13
E
5
1
D
C
7
G
3
6
8
3
F
19
2
21
<最大流問題と最小費用流問題>
60
B
90
120
A
70
80
30
20
C
D
10
100
100
50
40
30
E
F
130
80
A:ソース(フローを送り出す節点)
F:シンク(フローが流入する節点)
最大流問題
目的関数:
s:ソース
最大
f
t:シンク
制約条件:
Σ
xsj - Σ
xjs
= f
流出量
xij - Σ
xji
= 0
(i∈V-{s,t})
流れ保存則
{j|(s,j)∈E}
Σ
{j|(i,j)∈E}
Σ
{j|(j,s)∈E}
{j|(j,i)∈E}
xtj - Σ
{j|(t,j)∈E}
= -f
xjt
流入量
{j|(j,t)∈E}
0 ≦ xij ≦ uij
((i,j)∈E)
容量制約条件
x=(xij) :フロー
f:フローxの流量
あるフローxが与えられているとする
uxij
i
j
uxji
uxij= uij - xij
uxji= xij
uxij , uxji :フローxに対する枝(i,j)の残余容量
Gx=(V,Ex) :フローxに対する残余ネットワーク
フロー増加路:残余ネットワークにおける
ソースからシンクへの路
2
1(1)
4
5(3)
3(2)
1
5
5(0)
4(4)
8(6)
3
2
1
2
1
3
2
1
5
2
4
3
フローの例
4
2
1
3(1)
5
6
残余ネットワーク
<フロー増加法>
(0) 適当な初期フローxを定める (例えば xij=0)
(1)フロー増加路を見つける.
存在しなければ計算終了.
(2)フロー増加路に沿って可能な限りフローを追
加し,新しいフローxを得る.ステップ(1)に戻る.
最大流最小カット定理
カット(S,T):節点集合Vをソースsを含む集合Sと
シンクtを含む集合Tに分割したもの
C(S,T):カット(S,T)の容量
C(S,T) = Σ uij
(i,j)∈(S,T)
f = Σ xij - Σ xji ≦ C(S,T)
(i,j)∈(S,T)
(j,i)∈(T,S)
f * = C(S*,T*)
フロー増加法の終了時点
最大流問題の計算量
フロー増加法(Ford, Fulkerson(1956)):
O(mfmax)=O(m2U) , U=max{uij|(i,j) ∈E}
多項式時間アルゴリズムではない
Edmonds, Karp (1969):O(m2n)
Dinic (1970):O(mn2)
プリフロープッシュ法(Goldberg, Tarjan):O(mn2)
改良版:O(n2m1/2)
最小費用流問題
目的関数:
最小
cijxij
制約条件:
Σ
xij - Σ
{j|(i,j)∈E}
xji
= bi
{j|(j,i)∈E}
0 ≦ xij ≦ uij
((i,j)∈E)
(i∈V)
需要・供給量
容量制約条件
cij :枝(i,j)の1単位の流れに対するコスト
Σ bi = 0
i∈V
<負閉路除去法>
(0) 適当な初期フローxを定める
(1)残余ネットワークGx=(V,Ex)において負閉路
を見つける.存在しなければ計算終了.
(2)負閉路に沿って可能な限りフローを追加し,
新しいフローxを得る.ステップ(1)に戻る.
0,10
1
3,5
s
0,15
2
4,7
3
2,10
8,15
f = 25 = Σ bi
bi>0 (i∈V)
t
5,15
4
0,25
usi=bi
uit=-bi
csi=cit =0
最小費用流問題
目的関数:
最小
cijxij
t:シンク
制約条件:
Σ
xsj - Σ
xjs
= f
流出量
xij - Σ
xji
= 0
(i∈V-{s,t})
流れ保存則
{j|(s,j)∈E}
Σ
{j|(i,j)∈E}
Σ
s:ソース
{j|(j,s)∈E}
{j|(j,i)∈E}
xtj - Σ
{j|(t,j)∈E}
= -f
xjt
流入量
{j|(j,t)∈E}
0 ≦ xij ≦ uij
((i,j)∈E)
容量制約条件
<フロー増加法>
(0) 適当な初期フローxを定める (例えば xij=0)
(1)残余ネットワークGx=(V,Ex)においてソース
からシンクへの最短路を求める .
存在しなければ計算終了.
(2)最短路に沿って可能な限りフローを追加し,
新しいフローxを得る.流量= f になれば計算
終了.そうでなければステップ(1)に戻る.
最小費用流問題の計算量
負閉路除去法:反復回数=O(mCU)
C=max{cij|(i,j) ∈E}, U=max{uij|(i,j) ∈E}
多項式時間アルゴリズムではない
改良版:O(n2m3log n)
フロー増加法:O(n2f)
Goldberg, Tarjan(1988):O(nm2 log2 n)
最小費用循環流問題
目的関数:
最小
cijxij
制約条件:
Σ
xij - Σ
{j|(i,j)∈E}
xji
= 0
{j|(j,i)∈E}
lij ≦ xij ≦ uij
((i,j)∈E)
(i∈V)
流れ保存則
容量制約条件
0,10
1
3,5
s
0,15
2
4,7
3
2,10
t
5,15
8,15
0,(25,25)
4
0,25
マッチング問題
マッチングM(M⊂E):どの相異なる2つの枝
k,l∈ Mも端点を共有しない
B
A
D
F
C
E
最大マッチング問題の計算量:O(n3)
最適 k-マッチング問題の計算量:O(kn2)
割当問題
2部グラフ
2部グラフの最大マッチング
計算量:O(n2.5)
最大流問題
2部グラフの最適k-割当
計算量:O(kn2)
最小費用流問題
ダウンロード

Document