Bland`s rule for the Network Simplex Algorithm

ネットワークシンプレックス法に対する
Bland規則
同志社大学
渡辺扇之介
同志社大学
渡邊芳英
最小費用流問題を解く方法
はじめに
負閉路除去法，逐次最短路法
最小費用流問題
ネットワークシンプレックス法
全域木 (基底) の更新
B
巡回
A
D
解1
解2
解3
解4
最適解
巡回
C
解5
費用
巡回を防ぐ方法
各頂点には需要・供給量
各辺には (下限容量，上限容量)と費用
制約条件
・容量制約
・需要供給制約
目的
費用を最小にする．
最終(第一)閉鎖辺選択規則
主結果
Bland規則が巡回を防ぐ．
シンプレックス法における巡回
を防ぐ規則として有名．
１
シンプレックス法と巡回
補足
線形計画問題
⑤
① ②
③ ④
①
初期解
④
②
最適解
⑤
巡回発生!!
③
１’
以下の2つの条件を満たす
最小費用流問題
を考える．
フロー
有向グラフ
・容量制約
：需要供給量
頂点
を満たす．
・需要供給制約
：下限容量
辺
：上限容量
を満たす．
に対して
※
，
：単位費用
フロー
の費用
B
が最小となるフロー
A
D
を求める．
費用
B
A
D
C
C
２
ネットワークシンプレックス法 (1)
ネットワークシンプレックス法の更新
1. 初期解
2. 最適性の判定
3. 更新
省略
B
全域木の更新
全域木の更新
A
D
C
1. 初期解（何とかして見つけたとする．）
B
A
費用
D
C
３
ネットワークシンプレックス法 (2)
費用
全域木
B
A
B
D
C
A
最適性の
判定より
閉鎖辺
D
C
費用
B
A
B
D
C
閉路の
向き
A
D
C
４
巡回のメカニズム (1)
・・・
1. 全域木を選ぶ．
2. 最適性の判定より，加える辺を選ぶ．
3. 閉鎖辺を選ぶ．
選ぶ辺に自由度がある !!
巡回の原因
1. 全域木を選ぶ ??
B
A
D
C
５
巡回のメカニズム (2)
2. 最適性の判定より，加える辺を選ぶ ??
B
B
A
D
A
D
C
C
3. 閉鎖辺を選ぶ ??
B
A
B
D
C
A
D
C
６
巡回を防ぐ規則～最終閉鎖辺選択規則～
1. 全域木の選び方
: 上限に達する辺
: 下限に達する辺
: 上限にも下限にも達しない辺
B
B
A
D
B
A
C
D
A
D
C
2. 全域木に加える辺の選び方
C
自由
3. 閉鎖辺の選び方
B
A
B
D
C
A
D
C
７
新しい巡回を防ぐ規則～Bland規則～
◎ 辺の間に順序を決める :
1. 全域木の選び方
自由
2. 全域木に加える辺の選び方
&
3. 閉鎖辺の選び方
決めた辺に関する順序について，最小の辺を選択する．
B
A
B
A
D
C
B
D
A
D
C
C
B
B
A
D
C
A
D
C
８
おわりに
◎ ネットワークシンプレックス法の更新において
Bland規則 (迷ったら小さい辺を選ぶ)
を用いることで，巡回を防ぐことが出来る．
最小費用流問題
ネットワークシンプレックス法
帰着可能
線形計画問題
シンプレックス法
◎ 全域木の更新（グラフの組み合わせ論的更新）を
シンプレックス法の更新と完全に対応させることは難しい（と思う）．
◎ このBland規則による計算量の改善は期待できない．
◎ 実装は簡単．
Thank you very much!!
９

Download Report