最小费用最大流问题的网络单纯形算法
一、问题描述
我们有一个有向图，图中每条边有两个属性：
- 容量 \(c(u,v)\)，表示该边允许通过的最大流量。
- 单位费用 \(a(u,v)\)，表示每单位流量通过该边所需的成本。
同时，图中每个节点有供应/需求值 \(b(v)\)：
- 如果 \(b(v) > 0\)，表示节点是供应点（源），可以提供流量。
- 如果 \(b(v) < 0\)，表示节点是需求点（汇），需要接收流量。
- 如果 \(b(v) = 0\)，表示节点是转运点。
目标：在所有节点供应/需求平衡（即总供应 = 总需求，且每个节点净流出 = \(b(v)\)）的前提下，找到一种流量分配方案，使得总运输费用最小。
这个问题称为最小费用流问题（Min-Cost Flow）。
网络单纯形算法是求解此问题的一种高效算法，特别适用于稀疏图，它是线性规划单纯形法在图上的具体实现。
二、基本概念与数学模型
1. 形式化模型
设流量变量为 \(x_{uv}\)，满足：
- 容量约束：
\[ 0 \le x_{uv} \le c_{uv} \]
- 流量平衡（守恒）：
对每个节点 \(v\)：
\[ \sum_{(u,v) \in E} x_{uv} - \sum_{(v,w) \in E} x_{vw} = b(v) \]
- 目标函数：
\[ \min \sum_{(u,v) \in E} a_{uv} \cdot x_{uv} \]
2. 基解与生成树
在单纯形法中，基解对应图中一棵生成树（忽略边的方向），树边称为基边，非树边称为非基边。
- 基边的流量可以取边界值（0 或容量上界）或中间值（由平衡方程决定）。
- 在最小费用流问题中，我们常用可行生成树：将每条边的流量固定为 0 或容量上界，然后解树上的平衡方程得到唯一解。
三、算法步骤（网络单纯形）
1. 初始可行生成树的构造
常用方法：添加人工边（大费用法）或利用已知可行解。
一种简单构造：
- 增加一个虚拟节点 \(w\)，对每个节点 \(v\)：
- 如果 \(b(v) > 0\)，加边 \((v, w)\)，容量 \(b(v)\)，费用 0。
- 如果 \(b(v) < 0\)，加边 \((w, v)\)，容量 \(-b(v)\)，费用 0。
- 虚拟节点 \(w\) 的 \(b(w) = -\sum b(v)\) 使整体平衡。
- 以虚拟节点为根，与所有其他节点的边构成初始生成树，并设定合理流量使之可行。
2. 最优性条件（负费用有向圈条件）
对生成树 \(T\)，可以定义每个节点的势 \(\pi(v)\)，使得对每条树边 \((u,v)\) 满足：
\[a_{uv} + \pi(u) - \pi(v) = 0 \]
（即树边的简化费用为 0）
对非树边 \((u,v)\)，计算简化费用：
\[\bar{a}_{uv} = a_{uv} + \pi(u) - \pi(v) \]
最优性定理：如果对所有非树边满足：
- 如果 \(x_{uv} = 0\)，则 \(\bar{a}_{uv} \ge 0\)（不能通过增加流量减少费用）。
- 如果 \(x_{uv} = c_{uv}\)，则 \(\bar{a}_{uv} \le 0\)（不能通过减少流量减少费用）。
则当前解是最优的。
3. 迭代改进
如果存在非树边不满足上述条件：
- 情况 A：非树边 \(e=(u,v)\)，当前流量 \(x_e = 0\)，且 \(\bar{a}_{uv} < 0\)。
加入 \(e\) 会与树形成唯一圈（方向与 \(e\) 相同）。沿圈增加流量，可降低总费用，直到某条正向边达到容量上界或某条反向边达到 0 流量。 - 情况 B：非树边 \(e=(u,v)\)，当前流量 \(x_e = c_{uv}\)，且 \(\bar{a}_{uv} > 0\)。
加入反向边 \((v,u)\)（简化费用为 \(-\bar{a}_{uv} < 0\)）到树中形成圈，沿圈减少 \(e\) 的流量（即增加反向边的流量），直到某条边达到边界。
然后，将达到边界的边移出树，将新边加入树，更新势 \(\pi\)，得到新的生成树解。
4. 更新势的高效方法
换边后，只有新树所在连通分量的节点势会变化。设移除的边是 \((p,q)\)，加入的边是 \((u,v)\)，断开树后得到两个子树 \(T_u\)（含 \(u\)）和 \(T_v\)（含 \(v\)）。
如果新边是 \((u,v)\)，则更新：
\[\Delta = \bar{a}_{uv} \quad \text{（如果加入的是正向非饱和边）} \]
或
\[\Delta = -\bar{a}_{uv} \quad \text{（如果加入的是反向非零流量边）} \]
然后对 \(T_v\) 中所有节点 \(w\)：
\[\pi'(w) = \pi(w) + \Delta \]
这样树边的简化费用仍保持为 0。
四、举例说明
考虑简单网络：
节点 1：\(b(1)=2\)（供应）
节点 2：\(b(2)=-2\)（需求）
边：
(1,2)：容量 3，费用 4
(1,2) 只有一条边。
初始树：加入虚拟节点 0，边 (1,0)：容量 2 费用 0；边 (0,2)：容量 2 费用 0。
初始解：
x(1,0)=2, x(0,2)=2，x(1,2)=0。
计算势：设 π(0)=0，则树边 (1,0)：a=0+π(1)-0=0 → π(1)=0；
树边 (0,2)：0+0-π(2)=0 → π(2)=0。
非树边 (1,2)：简化费用 = 4+0-0=4>0，且流量为 0，满足最优性条件，不需调整。
但显然直接走 (1,2) 费用 4×2=8，比虚拟边方案费用 0 更差，所以虚拟解不是真正可行（因为有虚拟边）。
实际我们要去掉虚拟边，引入真实边。
重新构造：初始解取 x(1,2)=2，则平衡：节点1流出2，节点2流入2，可行。
树只有一条边 (1,2)，计算势：设 π(1)=0，树边满足 a+π(1)-π(2)=0 → 4+0-π(2)=0 → π(2)=4。
无其他非树边，已是最优。费用=8。
五、算法复杂度与特点
- 理论上可能指数时间（单纯形法特性），但在实践中对网络流问题非常快。
- 适合稀疏图，实现时需维护树的父子关系、深度、子树节点集合，以快速找圈和更新势。
- 可处理负费用边，但需避免负费用圈循环流。
六、总结步骤
- 构造初始可行生成树解（可用虚拟节点法）。
- 计算节点势，使所有树边简化费用为 0。
- 检查非树边简化费用，若存在可改进边，则：
- 找到改进圈，确定调整流量 Δ。
- 更新圈上流量，将达到边界的边换出树，新边加入。
- 更新势。
- 重复步骤 3 直到所有非树边满足最优性条件。
- 去掉可能的虚拟边，得到原问题最小费用流。