基于线性规划的图最小费用最大流问题的容量缩放原始-对偶算法求解示例 1. 问题描述 我们考虑一个有向图 \( G = (V, E) \)，其中： 每条边 \( (u, v) \in E \) 有一个 容量 \( c(u, v) \geq 0 \) 和一个 单位流费用 \( w(u, v) \in \mathbb{R} \)。 图中有 源点 \( s \) 和 汇点 \( t \)。 目标 ：在所有从 \( s \) 到 \( t \) 的可行流中，找到 流量最大 的流，并且在所有最大流中， 总费用 最小。 这是一个组合优化问题，可以自然地建模为线性规划，然后通过 容量缩放的原始-对偶算法 高效求解。 2. 线性规划建模 2.1 决策变量 对每条边 \( (u, v) \in E \)，定义流量变量 \( f(u, v) \geq 0 \)。 2.2 数学模型 目标 ：在流量最大的前提下，最小化总费用。 我们可以分为两步，但通常更直接的方法是 先求最大流，再在最大流中求最小费用 。 不过，经典的最小费用最大流问题（Min-Cost Max-Flow）可以统一为一个线性规划： \[ \begin{aligned} \text{最大化} &\quad \text{从 } s \text{ 发出的净流量} \\ \text{等价于} &\quad \text{最大化 } \sum_ {v: (s, v) \in E} f(s, v) - \sum_ {v: (v, s) \in E} f(v, s) \\ \text{约束} &\quad \text{对所有 } u \neq s, t: \quad \sum_ {v: (u, v) \in E} f(u, v) - \sum_ {v: (v, u) \in E} f(v, u) = 0 \quad (\text{流量守恒}) \\ &\quad 0 \leq f(u, v) \leq c(u, v) \quad \forall (u, v) \in E \end{aligned} \] 但 ，为了得到最小费用的最大流，我们实际上求解以下 两阶段 ： 用最大流算法找到最大流量值 \( F_ {\max} \)。 求解最小费用流问题，流量固定为 \( F_ {\max} \)： \[ \begin{aligned} \text{最小化} &\quad \sum_ {(u,v) \in E} w(u,v) f(u,v) \\ \text{约束} &\quad \sum_ {v} f(s,v) - \sum_ {v} f(v,s) = F_ {\max} \\ &\quad \sum_ {v} f(u,v) - \sum_ {v} f(v,u) = 0 \quad \forall u \neq s, t \\ &\quad 0 \leq f(u,v) \leq c(u,v) \quad \forall (u,v) \in E \end{aligned} \] 这个线性规划可用单纯形法求解，但网络流有特殊结构，我们可以用更快的原始-对偶算法结合容量缩放。 3. 对偶问题与互补松弛条件 3.1 原始问题整理 设 \( b(s) = F_ {\max}, b(t) = -F_ {\max} \)，其他 \( b(u) = 0 \)。 引入势变量 \( \pi(u) \) 对应对偶于流量守恒约束，对偶变量 \( \alpha(u,v) \geq 0 \) 对应 \( f(u,v) \geq 0 \)，对偶变量 \( \beta(u,v) \geq 0 \) 对应 \( f(u,v) \leq c(u,v) \)。 最终可推出经典 最小费用流的对偶 ： \[ \begin{aligned} \text{最大化} &\quad F_ {\max} (\pi(t) - \pi(s)) - \sum_ {(u,v) \in E} c(u,v) \beta(u,v) \\ \text{约束} &\quad \pi(v) - \pi(u) - \beta(u,v) \leq w(u,v) \quad \forall (u,v) \in E \\ &\quad \beta(u,v) \geq 0 \end{aligned} \] 令 \( r(u,v) = w(u,v) - \pi(v) + \pi(u) \) 是 简化费用 ，则对偶约束等价于 \( r(u,v) + \beta(u,v) \geq 0 \)。 由互补松弛条件： 如果 \( f(u,v) > 0 \)，则 \( r(u,v) + \beta(u,v) = 0 \)。 如果 \( f(u,v) < c(u,v) \)，则 \( \beta(u,v) = 0 \)。 因此，如果 \( 0 < f(u,v) < c(u,v) \)，则 \( r(u,v) = 0 \)。 如果 \( f(u,v) = 0 \)，则 \( r(u,v) \geq 0 \)。 如果 \( f(u,v) = c(u,v) \)，则 \( r(u,v) \leq 0 \)。 4. 容量缩放原始-对偶算法思想 算法基于 可行势 （feasible potentials）和 剩余网络 的概念。 给定势 \( \pi \)，定义简化费用 \( r(u,v) = w(u,v) + \pi(u) - \pi(v) \)。 如果 \( r(u,v) \geq 0 \) 对所有边成立，则 \( \pi \) 是可行势。 关键观察 ：如果 \( r(u,v) \geq 0 \) 对所有边成立，并且我们只沿简化费用为 0 的边增广，则得到的流是最小费用的（对当前流量）。 容量缩放 ： 我们从较大的容量界限 \( \Delta \) 开始（比如 2 的幂次，大于最大容量）。 在每一轮缩放中，我们只考虑容量至少为 \( \Delta \) 的边，寻找从 \( s \) 到 \( t \) 的路径，路径上所有边的简化费用为 0（称为“可接受边”），并沿该路径推送尽可能多的流量（不超过容量和 \( \Delta \)）。 推送后，更新势函数以保证不引入负简化费用的可接受边。当不存在这样的路径时，将 \( \Delta \) 减半，继续下一轮，直到 \( \Delta < 1 \) 算法结束。 5. 算法步骤详解 5.1 初始化 设流量 \( f(u,v) = 0 \) 对所有边。 设势 \( \pi(u) = 0 \) 对所有顶点。 计算最大流量值 \( F_ {\max} \)（可通过任意最大流算法得到，例如 Edmonds–Karp 或 Dinic）。 设目标流量 \( F^* = F_ {\max} \)，当前流量 \( F = 0 \)。 设 \( \Delta = 2^{\lfloor \log_ 2(\max_ {(u,v)\in E} c(u,v)) \rfloor} \)。 5.2 主循环（容量缩放阶段） 当 \( \Delta \geq 1 \) 时执行： 构建剩余网络 \( G_ f \)： 对每条原边 \( (u,v) \) 容量 \( c(u,v) \)，如果 \( f(u,v) < c(u,v) \)，则剩余容量 \( r(u,v) = c(u,v) - f(u,v) \)，方向同原图。 如果 \( f(u,v) > 0 \)，则有反向边 \( (v,u) \)，剩余容量 \( r(v,u) = f(u,v) \)，费用 \( w(v,u) = -w(u,v) \)。 只考虑剩余容量 \( r(u,v) \geq \Delta \) 的边，在这些边中，只考虑简化费用 \( w^{\pi}(u,v) = w(u,v) + \pi(u) - \pi(v) = 0 \) 的边，构成“可接受图”。 在可接受图中寻找从 \( s \) 到 \( t \) 的路径（用 BFS/DFS）。 如果找到路径 \( P \)，沿 \( P \) 推送流量 \( \delta = \min \{ \min_ {e \in P} r(e), F^* - F \} \)（但不能超过 \( \Delta \)）。 更新流量 \( f \)，更新 \( F = F + \delta \)。 更新剩余网络 \( G_ f \)。 如果 \( F = F^* \)，则停止（已得到最大流）。否则重复步骤 3。 如果在可接受图中无 \( s \to t \) 路径，则更新势函数： 在剩余网络中，对满足 \( r(u,v) \geq \Delta \) 的边，如果 \( w^{\pi}(u,v) < 0 \)，则允许其加入可接受图（即放宽条件，使更多边可接受）。 具体更新：从 \( s \) 出发，在剩余容量 \( \geq \Delta \) 的边中，计算从 \( s \) 到各点 \( v \) 的最短路径（按 \( w^{\pi} \)），设距离为 \( d(v) \)。 更新 \( \pi(v) := \pi(v) + d(v) \)（或 \( \pi(v) := \pi(v) - d(v) \) 取决于符号定义，确保简化费用非负）。 这样至少会使一条边的简化费用变为 0，可继续增广。 如果本 \( \Delta \) 阶段无法再增广，则令 \( \Delta := \Delta / 2 \)，进入下一缩放轮。 5.3 终止 当 \( \Delta < 1 \) 时，算法终止。此时流量 \( F = F^* \)，且满足所有互补松弛条件，因此 \( f \) 是最小费用最大流。 6. 算法正确性分析 势函数的保持 ：每次更新势后，剩余网络中所有边的简化费用保持非负，这保证了算法不会产生负费用循环，从而确保最终流是最小费用的。 容量缩放的作用 ：在 \( \Delta \) 阶段，我们只沿大容量边增广，这减少了对势的更新次数，提高了效率。每轮 \( \Delta \) 阶段推送的流量至少为 \( \Delta \)，因此总增广次数为 \( O(\log C) \) 乘以每阶段的增广次数，而每阶段的增广次数受 \( O(|V||E|) \) 限制，因此总复杂度为 \( O(|V||E| \log C) \)（如果使用 Dijkstra 更新势）。 最优性 ：最终满足互补松弛条件，由线性规划对偶理论，流是最小费用的，并且流量为 \( F_ {\max} \)。 7. 举例说明 考虑简单有向图： 顶点 \( s, a, b, t \)。 边与（容量，费用）： \( s \to a: (3, 1) \) \( s \to b: (2, 2) \) \( a \to b: (2, 1) \) \( a \to t: (2, 3) \) \( b \to t: (3, 1) \) 最大流量 \( F_ {\max} = 4 \)（可验证）。 用容量缩放原始-对偶算法： 初始化 \( f = 0, \pi=0, \Delta = 4 \)（因为最大容量 3，取 2 的幂 4）。 \( \Delta = 4 \) 时，没有剩余容量 ≥4 的边，所以直接 \( \Delta=2 \)。 \( \Delta=2 \) 时，考虑剩余容量 ≥2 的边，初始可接受图为空（简化费用非 0）。更新势后，找到路径 \( s \to a \to t \)（简化费用 0），推 2 单位流量。更新流。 继续在 \( \Delta=2 \) 阶段找其他路径，最终在多个缩放轮后得到最大流 4，费用最小。 最终流： \( s \to a: 3 \) \( s \to b: 1 \) \( a \to b: 1 \) \( a \to t: 2 \) \( b \to t: 2 \) 总费用 = \( 3\times1 + 1\times2 + 1\times1 + 2\times3 + 2\times1 = 3+2+1+6+2=14 \)。 8. 总结 最小费用最大流问题是线性规划在网络流中的重要应用。 容量缩放原始-对偶算法结合了对偶理论（势函数）和容量缩放技巧，实现高效求解。 其核心思想是在保持简化费用非负的前提下，沿 0 费用边增广，缩放容量以减少迭代次数。 该算法复杂度优于一般单纯形法，是求解大规模最小费用最大流问题的实用方法之一。