輸送問題・最小費用フロー

確定済みネットワークの容量制約下で各拠点の正味需給を満たす最小費用の物量配分を求める。

単一品目・整数の物量・0以上の単位輸送費用が対象です。輸送ルートの訪問順や拠点の新設場所は最適化しません。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は3項目です。

すべての拠点と辺で同じ単位を使います。小数の重量は整数単位(例:1.5t→1500kg)に換算してください。

拠点と供給需要必須
行拠点ID供給(+)/需要(−)(選択単位)操作
1
2

2列を左端の欄へタブ区切りで貼り付けられます。25行まで。

供給は正、需要は負、中継拠点は0。拠点IDは重複せず、辺の起点・終点と一致させます。

輸送辺・容量・費用必須
行起点ID終点ID容量(選択単位)単位費用(円/選択単位)操作
1
2

4列を左端の欄へタブ区切りで貼り付けられます。80行まで。

有向辺の起点→終点を入力。同じ拠点間の複数辺も別々に扱います。容量0・単位費用0を指定できます。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

最小化する総費用 Z=Σ(各辺の単位費用 cₑ × 流量 fₑ)。各拠点で出流量−入流量=正味供給量 bᵢ(供給正/需要負)、各有向辺で0≦fₑ≦容量uₑを満たします。正味供給量の合計は0にしてください。残余ネットワーク上で最短増加路を繰り返して整数の最適配分を求めます。費用は円、数量・容量は選択した同一単位です。

最小輸送費用(円)、総出荷量、辺別最適流量と費用、拠点別流量保存の確認表。

計算例(架空の数値)

Google OR-Toolsの公開例:拠点0~4、供給[20,0,0,−5,−15]、9辺の容量・費用を指定した場合、最小費用150。ここでは単位費用を円/個とした例に相当します。

適用対象と限界

単一品目の供給・需要量と、既設輸送ネットワークの有向辺容量・単位費用が既知の業務計画。小数流量、負の単位費用、固定費、運行順、時間制約、複数品目、拠点設置判断、輸送距離や運賃表の自動取得は対象外。

方法と出典

方法:単一品目・整数最小費用フロー v1.0(Google OR-Toolsの問題定義・2026-03-18更新版と照合)。データ記録日:2026-11-13。