Research index
ネットワークシンプレックス法における巡回を防ぐ方法
米田, 渡辺, 渡邊 and 6 others
30 Apr 2013Open access
NobleIDark:/48914/w1/20260525/00EEAD3DDOI10.14988/pa.2017.0000013085
Open access
ネットワークシンプレックス法における巡回を防ぐ方法
米田, 渡辺, 渡邊 and 6 others · 2013
NobleIDark:/48914/w1/20260525/00EEAD3DDOI10.14988/pa.2017.0000013085
Abstract
本論文では,フローネットワークにおける最適化問題の1つである,最小費用流問題に着目する.最小費用流問題とは,容量制約と需要条件を満たすフローの中で,そのコストが最小となるフローを求める問題で,実社会に広く応用されている問題である.この最小費用流問題を解くアルゴリズムとして,最も効率的であるのがネットワークシンプレックス法である.このアルゴリズムは木構造と呼ばれるものを更新し,最小費用流問題の最適解を求めるアルゴリズムであるが,更新が収束しない現象が頻繁に起こる.この現象は巡回と呼ばれ,巡回は強認容木構造をと呼ばれる特別な木構造を保つことで防ぐことができる.本論文では,この強認容木構造を保ちながら更新するための新しい方法について述べる.この新しい方法を第一閉鎖辺選択規則と呼ぶ.この方法はネットワークシンプレックス法における巡回の数学的構造をあきらかにする,重要な役割を果たす.