最小費用流問題

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2025年6月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Minimum-cost flow problem|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

最小費用流問題（さいしょうひようりゅうもんだい、最小費用フロー問題、英: minimum-cost flow problem、略称：MCFP）とは、フローネットワークにおいてある与えられた量のフローを流すとき、最も費用がかからないものを求める最適化・決定問題である。最小費用流問題の主な応用例としては道路網に容量と費用が付随した中での工場から倉庫までの最適な配送経路を求める事例が挙げられる。多くのフローや循環に関する問題は最小費用流問題として定式化することができ、それをネットワーク単体法を用いて効率良く解くことができるため、最小費用流問題は最も基本的な問題の一つとして挙げられる。

フローネットワークでは有向グラフ ${\displaystyle G=(V,A)}$ および始点となる頂点 ${\displaystyle s\in V}$ と、終点となる頂点 ${\displaystyle t\in V}$ が与えられる。ただし、各辺 ${\displaystyle (u,v)\in A}$ に対して正の値をとる容量 ${\displaystyle c(u,v)>0}$ とフロー量 ${\displaystyle f(u,v)}$、費用 ${\displaystyle a(u,v)}$ が定義され、最小費用流問題に対するアルゴリズムでは非負の費用であることが求められる。辺 ${\displaystyle (u,v)}$ にフローを流すときにかかる費用は ${\displaystyle f(u,v)\cdot a(u,v)}$ によって求まる。この問題は始点 ${\displaystyle s}$ から終点 ${\displaystyle t}$ へフロー ${\displaystyle d}$ を流すことを考える。

最小費用流問題で求めることはすべての辺においてフローを流すときにかかる費用の総和の最小化である。

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

これを達成するために、守らなければならない条件（制約条件）は:

容量制約:	${\displaystyle \,f(u,v)\leq c(u,v)}$
流量保存則:	${\displaystyle \,f(u,v)=-f(v,u)}$
始終点に関する制約:	${\displaystyle \,\sum _{w\in V}f(u,w)=0\quad \forall u\neq s,t}$
フロー需給量制約:	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d}$

最小費用流問題の類似問題としてはフローネットワークにおいて最大流を流すときに、その中で最も費用が掛からないものを求める問題が挙げれられる。これは最小費用最大流問題として知られ、最小費用の下で最大マッチングを求めるために利用されている。

最小費用最大流問題はいくつかの解法によって、多くの問題に対して効率よく最小費用最大流を求めることができる。そうでない場合は、二分探索によってある ${\displaystyle d}$ の下での最小費用流を解いていくことで、最小費用最大流を求めることができる。

以下の問題は最小費用流問題の特殊な問題として知られている^{[1][注釈 1]}:

• （単一の始点をもつ）最短経路問題: 始点 ${\displaystyle s}$ から終点 ${\displaystyle t}$ へ単一のフローを流すときにかかる費用が最小の解を求めることと等しい。なお、各辺の容量は無限であると仮定する。
• 最大流問題: 十分に大きな需要量 ${\displaystyle d}$ を与える（${\displaystyle d}$ は始点から出る辺の容量の総和を超すようなフロー量などフローネットワークでの最大流より十分に大きなものとする）。そして、各辺の費用をすべてゼロとする。また、始点から終点へ単位費用と ${\displaystyle d}$ の容量を持つ辺を新たに加える。
• 割当問題（英語版）: 二つに分けられた部分集合がそれぞれ ${\displaystyle n}$ 個の頂点を持っているとする。また、二つの部分集合を ${\displaystyle (X,Y)}$ と記述する。各 ${\displaystyle x\in X}$ では供給量 ${\displaystyle 1/n}$ を持ち、各 ${\displaystyle y\in Y}$ においては需要量 ${\displaystyle 1/n}$ を持つとする。各辺は単位容量を持つとする。

最小費用流問題は線形で表される制約の下で線形関数の最適化を行うため、線形計画法により解くことができる。

これ以外にも多くの厳密解法が知られている^[1]。いくつかの解法は最大流問題に対する解法を一般化させたものではあるが、異なるアプローチにより提案された解法も存在している。

（変種も含めた）一般的に知られているアルゴリズムは以下が挙げられる:

• 負閉路消去法（Cycle canceling）^[2]: 一般的に知られている解法で主（プライマル）法に分類される^[3]。
• カット消去法（Cut canceling）^[4]: 双対法に分類される解法で、一般的に知られている^[5][6]。
• 最小平均閉路消去法（Minimum mean cycle canceling）^[7]: 単純な解法で強多項式時間（英語版）で実行できる^[8]。
• 逐次最短路法（最短路繰り返し法、Successive shortest path）・容量スケーリング法（capacity scaling）^[9]: 最大流問題に対するフォード・ファルカーソン法を一般化させた解法で、双対法に分類される^[10]。
• 費用スケーリング法（Cost scaling）^[11]: 最大流問題に対するプリフロープッシュ法を一般化させた解法であり、主双対法に分類される^[12]。
• ネットワーク単体法（ネットワークシンプレックス法、Network simplex algorithm）^[13]: 線形計画法に対する単体法を最小費用流問題に特化させた解法^[14]。
• アウトオブキルタ法（Out-of-kilter algorithm）^[15]: レイ・ファルカーソン（英語版）により提案された。

• 繁野麻衣子 著「第9.5章　最小費用流問題」、久保幹雄、田村明久、松井知己 編『応用数理計画ハンドブック』（1版）、2002年、390-408頁。CRID 1130000795637802368。ISBN 4254270046。 NCID BA56729727。OCLC 674964887。 

• GNU Linear Programming Kit（英語版）
• ネットワークフロー問題（英語版）

• LEMON C++ライブラリでは複数の最小費用流問題に対する解法が提供されている。
• MCFClass C++プロジェクトライブラリでは複数の最小費用流および最短経路問題に対する解法が提供されている。

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法 逐次線形二次計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 逆削除法 　最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 フローネットワーク 最大流問題 ディニッツ法 エドモンズ–カープ法 フォード–ファルカーソン法 プリフロープッシュ法 最小費用流問題 ネットワーク単体法 アウトオブキルタ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ 群知能（ACO・PSO） ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア （一覧）