最小費用流・輸送問題

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：最大流・最小カット・線形計画の標準形と幾何　|　関連：割当問題（ハンガリアン法）

要点（BLUF）

最小費用流：容量と単位費用を持つネットワークで、需給を満たしつつ 総費用を最小にする流れ。
輸送問題はその特殊例：供給地から需要地へ、供給量・需要量を満たして総輸送費を最小化。
制約行列が 全ユニモジュラなので、LP として解いても 自動的に整数解（整数計画とは・LP緩和のギャップ0）。

概念 ── 流れに費用をつける

最大流（最大流・最小カット）は「最も多く流す」だった。最小費用流は「決められた量を、最も安く流す」。各辺 $(u,v)$ に容量 $c(u,v)$ と単位費用 $a(u,v)$ があり、ノードには供給（ $+$ ）・需要（ $-$ ）がある：

\min\ \sum_{(u,v)} a(u,v)\, f(u,v) \quad \text{s.t.}\quad \underbrace{\sum_w f(v,w) - \sum_u f(u,v) = b(v)}_{\text{各ノードの需給バランス}},\ \ 0 \le f \le c

$b(v)$ はノード $v$ の正味供給（供給地は正、需要地は負、中継は0）。配送・物流・通信路の費用最小化が典型。

輸送問題

最小費用流の最も使われる特殊形。 $m$ 個の 供給地（供給量 $s_i$ ）から $n$ 個の 需要地（需要量 $d_j$ ）へ、単位輸送費 $c_{ij}$ で運ぶ。総需給が釣り合う（ $\sum s_i = \sum d_j$ ）として：

\min \sum_{i,j} c_{ij}\, x_{ij} \quad \text{s.t.}\quad \sum_j x_{ij} = s_i\ (\forall i),\ \ \sum_i x_{ij} = d_j\ (\forall j),\ \ x_{ij}\ge0

供給地ごとの出荷量＝供給量、需要地ごとの受取量＝需要量。割当問題（割当問題（ハンガリアン法））は、供給・需要がすべて1の輸送問題。

graph LR
  S1["供給地1 (20)"] -->|"費用cij"| D1["需要地1 (10)"]
  S1 --> D2["需要地2 (25)"]
  S2["供給地2 (30)"] --> D1
  S2 --> D2
  S2 --> D3["需要地3 (15)"]
  S1 --> D3

Pythonで輸送問題を解く

供給 $[20,30]$ 、需要 $[10,25,15]$ 、費用行列を与えて総費用最小の輸送計画を LP で解く。

import numpy as np
from scipy.optimize import linprog

supply = [20, 30]
demand = [10, 25, 15]
cost = np.array([[8, 6, 10],     # 供給地1から需要地1,2,3への単位費用
                 [9, 12, 4]])    # 供給地2から
m, n = 2, 3
c = cost.flatten()

A_eq, b_eq = [], []
for i in range(m):                       # 各供給地の出荷量 = 供給量
    row = [0]*(m*n)
    for j in range(n): row[i*n+j] = 1
    A_eq.append(row); b_eq.append(supply[i])
for j in range(n):                       # 各需要地の受取量 = 需要量
    row = [0]*(m*n)
    for i in range(m): row[i*n+j] = 1
    A_eq.append(row); b_eq.append(demand[j])

res = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=[(0, None)]*(m*n), method="highs")
print(f"最小総輸送費 = {res.fun:.0f}")
print(f"輸送量(行=供給地, 列=需要地):\n{np.round(res.x.reshape(m, n), 1)}")

実行結果：

最小総輸送費 = 330
輸送量(行=供給地, 列=需要地):
[[ 0. 20.  0.]
 [10.  5. 15.]]

総費用 330。供給地1は需要地2へ20、供給地2は需要地1へ10・需要地2へ5・需要地3へ15を運ぶ。連続 LP として解いたのに、輸送量がすべて整数になっている ── 全ユニモジュラ性のおかげで、整数制約を課さずとも整数解が出る。供給地2は需要地3への費用が安い（4）ので、需要地3を全部担当している点に注目。

数式の直観的意味

最小費用流が「整数なのに易しい」のは、需給バランス制約の係数行列が 接続行列（incidence matrix） で、これが全ユニモジュラだから。全ユニモジュラ行列を持つ LP は、右辺が整数なら 頂点（基底解）がすべて整数になる（線形計画の標準形と幾何の頂点最適＋整数性）。だから整数計画（整数計画と組合せ最適化章目次）の難しさ（NP 困難）を免れ、LP の多項式時間解法（シンプレックス法・内点法入門）やネットワーク専用の ネットワークシンプレックス法で高速に解ける。最小費用流は、最短路（単一の単位流、最短経路問題（ダイクストラ・ベルマンフォード））・最大流（費用を無視、最大流・最小カット）・輸送・割当を すべて特殊例として含む統一問題で、ネットワーク最適化の中心に位置する。双対変数（感度分析）は各ノードの「ポテンシャル（価格）」と解釈でき、最適性条件（被約費用が非負）が経済的な意味を持つ。

⚠️ よくある誤解・落とし穴

需給バランスが前提： $\sum s_i \ne \sum d_j$ ならダミー供給地／需要地で釣り合わせる。
全ユニモジュラだから整数性：右辺（供給・需要）が整数でないと整数解は保証されない。
費用に負があってもよい（最短路の負辺に対応）が、負閉路があると非有界。
大規模では汎用 LP より ネットワークシンプレックスや専用アルゴリズムが桁違いに速い。