書誌事項
- タイトル別名
-
- The maximum flow problem and its dual
- サイダイリュウ モンダイ ト ソノ ソウツイ モンダイ
この論文をさがす
説明
本論文では,フローネットワーク最適化問題の1つとして有名な最大流問題に注目する.最大流問題とは,ネットワークにおいて2つの制約,容量制約と流量保存則のもとでフローの値が最大となるフローを見つける問題である.多くの組み合わせ最適化問題は線形計画問題(LP問題)として定式化され,最大流問題についてもLPへの定式化の方法は知られている.一方で,組み合わせ最適化問題において有名な定理,最大フロー・最小カットセット定理はネットワークにおけるフローとカットセットの双対性を表したものだと知られている.我々の研究の目的は,フローとカットセットの双対性をLP問題を通して明らかにすることである.本論文では知られている定式化とは違う新しい最大流問題の定式化を行った.実験結果によると,新しい定式化の双対問題は解として0-1ベクトルが現れ,これは最小カットセットを与えていた.この結果よりこの定式化は我々の意図するものだといえる.しかし,LP問題の双対問題を作ったのにもかかわらず,0-1ベクトルが解として現れた理由についてはまだ分かっておらず,これを今後の課題とする.
収録刊行物
-
- 同志社大学理工学研究報告
-
同志社大学理工学研究報告 53 (2), 99-103, 2012-07-31
同志社大学理工学研究所
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1390853649843884416
-
- NII論文ID
- 110009443892
-
- NII書誌ID
- AN00165868
-
- NDL書誌ID
- 023930119
-
- ISSN
- 00368172
-
- 本文言語コード
- ja
-
- 資料種別
- departmental bulletin paper
-
- データソース種別
-
- JaLC
- IRDB
- NDLサーチ
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用可