一つの付加線形条件を有する最小費用流問題を解くための辞書式最短路アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
この論文では、一つの付加線形条件を有する最小費用流問題を解くためのプライマル・デュアル法を示す。ネットワークの個々の枝に、2次元の距離が付与されている。第1成分は、費用に関連し、第2成分は、付加条件の係数に関連している。辞書式順序に関して最小の距離を持つ路を辞書式最短路といい、負の距離を持つ閉路を辞書式負の閉路ということにする。第1成分が負である閉路は現われないが、第1成分が0であって。、第2成分が負である閉路が存在するときは現在の主問題の解(流れ)は、その閉路の流れを変えることによって改良される。負の閉路が存在しないときは、最短路が存在し、双対問題の解が改良される。この解法は、現在の解の基底を保持する必要がないという意味で、純ネットワーク的解法であり、退化現象がしばしば起こる場合に適している。
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
関連論文
- 最大流問題
- 最短路問題
- 一つの付加線形条件を有する最小費用プロジェクト・スケジューリング問題を解くための辞書式制約付き流れアルゴリズム
- 一つの付加線形条件を有する最小費用流問題を解くための辞書式最短路アルゴリズム
- ネットワ-ク流のモデリングと解法 (ネットワ-ク技術) -- (ネットワ-クに関する解析・設計・運用技法)
- ORにおける組合せ論的な問題とその解法 (組合せ論的システム特集号)