最小費用フロー問題
読み方：さいしょうひようふろーもんだい
【英】：minimum cost flow problem
【英】：minimum cost flow problem
最小費用流問題ともいう．有向グラフと, 枝の容量と費用, 点の供給(需要)量が与えられたときに, 各枝の容量を超えず, 各点での正味の流出量が供給量と等しくなる枝上の流れをフローという. 各枝の流量に対する費用の総和を最小にするフローを求める問題の総称. 線形計画問題の特殊ケースである. 強多項式時間で解けることが知られている.
「OR事典」の他の用語
| グラフ･ネットワーク： | 最大フロー最小カット定理 最大マッチング最小被覆定理 最小木問題 最小費用フロー問題 最短路問題 最近近傍法 有向グラフ |
最小費用流問題
(最小費用フロー問題 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/07 07:59 UTC 版)
|
この記事は英語版の対応するページを翻訳することにより充実させることができます。（2025年6月）
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
最小費用流問題（さいしょうひようりゅうもんだい、最小費用フロー問題、英: minimum-cost flow problem、略称：MCFP）とは、フローネットワークにおいてある与えられた量のフローを流すとき、最も費用がかからないものを求める最適化・決定問題である。最小費用流問題の主な応用例としては道路網に容量と費用が付随した中での工場から倉庫までの最適な配送経路を求める事例が挙げられる。多くのフローや循環に関する問題は最小費用流問題として定式化することができ、それをネットワーク単体法を用いて効率良く解くことができるため、最小費用流問題は最も基本的な問題の一つとして挙げられる。
定義
フローネットワークでは有向グラフ 
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) |
|||||
|---|---|---|---|---|---|
| グラフ理論 |
|
||||
| フローネットワーク |
|
- 最小費用フロー問題のページへのリンク
