最小費用流問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/07 07:59 UTC 版)
|
この記事は英語版の対応するページを翻訳することにより充実させることができます。（2025年6月）
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
最小費用流問題（さいしょうひようりゅうもんだい、最小費用フロー問題、英: minimum-cost flow problem、略称：MCFP）とは、フローネットワークにおいてある与えられた量のフローを流すとき、最も費用がかからないものを求める最適化・決定問題である。最小費用流問題の主な応用例としては道路網に容量と費用が付随した中での工場から倉庫までの最適な配送経路を求める事例が挙げられる。多くのフローや循環に関する問題は最小費用流問題として定式化することができ、それをネットワーク単体法を用いて効率良く解くことができるため、最小費用流問題は最も基本的な問題の一つとして挙げられる。
定義
フローネットワークでは有向グラフ 
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) |
|||||
|---|---|---|---|---|---|
| グラフ理論 |
|
||||
| フローネットワーク |
|
- 最小費用流問題のページへのリンク
