Day 057-Q5 | 線形計画双対 × MCMF（最適輸送・強双対定理）

問題

$N$ 個の工場と $M$ 個の倉庫がある。工場 $i$ は供給量 $s_i$、倉庫 $j$ は需要量 $d_j$、単位輸送コスト $c_{ij}$ が与えられる。

全需要を満たす輸送計画のうち総コスト最小のものを求めよ。また双対問題の最適解も出力し、強双対定理（主問題の最適値 = 双対問題の最適値）を確認せよ。

制約

パラメータ	範囲
$N, M$	$1 \le N, M \le 50$
$s_i, d_j$	$1 \le s_i, d_j \le 100$
$c_{ij}$	$0 \le c_{ij} \le 1000$
均衡条件	$\sum s_i = \sum d_j$

入出力例

入力例 1

出力例 1

主問題最適値: 14
双対問題最適値: 14

供給 [3,5]、需要 [2,3,3]、コスト行列 [[1,4,3],[5,2,1]]。主=双対 = 14 で強双対定理を確認。

概念図: 最適輸送と LP 双対

ヒント（段階的開示）

ヒント1: 方向性

最適輸送問題は最小費用流（MCMF）に直接帰着できる。供給源ノード $S$、吸収ノード $T$ を追加し、$S \to$ 工場 $\to$ 倉庫 $\to T$ のグラフで最小費用最大流を計算。 MCMF の最終ポテンシャル $h[v]$ が LP 双対の最適解になる。

ヒント2: アプローチ

グラフ構築: $S \to$ 工場 $i$（容量 $s_i$、コスト 0）、工場 $i \to$ 倉庫 $j$（容量 $\infty$、コスト $c_{ij}$）、倉庫 $j \to T$（容量 $d_j$、コスト 0）
MCMF をポテンシャル法（Bellman-Ford 初期化 + Dijkstra）で解く
最終ポテンシャル $h$ から双対変数 $u_i = h[\text{工場}_i]$、$v_j = h[\text{倉庫}_j]$ を取得
強双対の確認: $\sum s_i u_i + \sum d_j v_j$ = 主問題の最適値

ヒント3: コード骨格

# Bellman-Ford 初期ポテンシャル
h = [INF]*n; h[s] = 0
for _ in range(n-1):
    for u in range(n):
        if h[u]==INF: continue
        for v,cap,cost,_ in g[u]:
            if cap>0 and h[u]+cost < h[v]:
                h[v] = h[u]+cost

# Dijkstra（reduced cost を使用）
nd = dist[u] + cost + h[u] - h[v]  # reduced cost >= 0

# 更新後のポテンシャル
h[i] += dist[i]  # 各反復後に更新

模範解答 (Python)

import sys, heapq
input = sys.stdin.readline
INF = float('inf')

class MCMF:
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]

    def add_edge(self, u, v, cap, cost):
        self.g[u].append([v, cap, cost, len(self.g[v])])
        self.g[v].append([u, 0, -cost, len(self.g[u])-1])

    def solve(self, s, t, f):
        n = self.n; g = self.g
        h = [INF]*n; h[s] = 0
        for _ in range(n-1):
            for u in range(n):
                if h[u]==INF: continue
                for v,cap,cost,_ in g[u]:
                    if cap>0 and h[u]+cost < h[v]:
                        h[v] = h[u]+cost

        flow = cost = 0
        while flow < f:
            dist = [INF]*n; dist[s] = 0
            pv = [-1]*n; pe = [-1]*n
            pq = [(0,s)]
            while pq:
                d,u = heapq.heappop(pq)
                if d>dist[u]: continue
                for i,(v,cap,c,_) in enumerate(g[u]):
                    if cap>0:
                        nd = d+c+h[u]-h[v]
                        if nd 0:
                    print(f"({i}->{j}): {used}")

    print(f"双対変数 u: {u}")
    print(f"双対変数 v: {v_dual}")

solve()

Step-by-Step 解説

Step 1: 最適輸送 → MCMF 変換

供給・需要をフローの量として表現し、輸送コストを辺コストとして MCMF グラフを構築する。均衡条件（$\sum s_i = \sum d_j$）により最大流 = 総供給量になる。

Step 2: ポテンシャル法（Johnson's algorithm）

Bellman-Ford で初期ポテンシャル $h$ を計算後、reduced cost $\tilde{c}_{uv} = c_{uv} + h[u] - h[v] \ge 0$ を使った Dijkstra で最短路を探索。負辺があっても安全に動作する。

Step 3: ポテンシャルの更新

各反復後に $h[i] += \text{dist}[i]$ で更新することで、次回以降の Dijkstra も正しい reduced cost を使える。

Step 4: 強双対定理の確認

最終ポテンシャル $h$ が LP 双対の最適解。$\sum s_i h[\text{工場}_i] + \sum d_j h[\text{倉庫}_j]$ = 主問題の最適値が成立することで強双対定理を確認。

計算量

処理	計算量
Bellman-Ford 初期化	$O((N+M) \cdot NM)$
各反復（Dijkstra）	$O(NM \log(N+M))$
反復回数	$O(\text{flow}) = O(\sum s_i)$
全体	$O(NM \cdot \text{flow} \cdot \log(N+M))$

よくあるミス

ミス	原因	正しい書き方
Bellman-Ford 初期化	`h[s] = INF` のまま	`h[s] = 0` に設定
reduced cost の符号	$+ h[u] - h[v]$ の向き	辺 $u \to v$ の reduced cost = $c_{uv} + h[u] - h[v]$
辺容量の復元	残余グラフの残容量から計算	`orig_cap - remaining_cap` で使用量を計算
双対変数の解釈	ポテンシャルの絶対値が異なる	基準点 ($h[S] = 0$) からの相対値を確認

次のステップ

発展: Earth Mover's Distance（1次元 Wasserstein 距離を累積和で $O(N \log N)$）
類題: AtCoder AGC010D "Decrementing", Codeforces 164C
応用: Sinkhorn アルゴリズム（エントロピー正則化付き最適輸送）

自己評価

完全理解おおむね理解要復習

自分の回答:

気づき・メモ: