最小费用最大流问题的网络单纯形算法
题目描述
给定一个有向图，每条边有容量（最多能通过多少流量）和单位费用（每单位流量通过该边所需的成本）。
有一个源点（source）和一个汇点（sink），问：
在不超过每条边容量的前提下，从源点发送尽可能多的流量到汇点，并且使得总费用最小。
这就是最小费用最大流（Minimum Cost Maximum Flow, MCMF）问题。
网络单纯形算法是求解该问题的一种高效方法，它结合了单纯形法（线性规划）与图的结构特性。
解题思路
网络单纯形算法可以看作单纯形法在最小费用流问题上的特化版本，它直接在图上操作，利用生成树结构来维护一个可行流，并不断进行换基操作（pivot）来降低费用，直到达到最优。
1. 问题形式化
设图 \(G = (V, E)\)，每条边 \(e = (u, v)\) 有：
- 容量 \(cap(e) \geq 0\)
- 单位费用 \(cost(e)\)（可正可负）
- 流量 \(flow(e)\)（待求变量）
我们要最小化总费用：
\[\min \sum_{e \in E} cost(e) \cdot flow(e) \]
约束条件：
- 容量约束：\(0 \leq flow(e) \leq cap(e)\)
- 流量守恒（除源点 \(s\) 和汇点 \(t\)）：
\[ \sum_{e \in \delta^+(v)} flow(e) - \sum_{e \in \delta^-(v)} flow(e) = 0, \quad \forall v \neq s, t \]
- 从 \(s\) 流出的总流量 = 流入 \(t\) 的总流量 = 最大流值 \(F_{\max}\)（我们通常先求最大流，再在最大流中找最小费用；但网络单纯形通常同时进行）。
2. 核心思想
在单纯形法中，我们需要：
- 一个基可行解（对应图中的一个生成树结构的流）
- 一个检验数（reduced cost）来判断是否最优
- 一个换基（pivot）操作来改进解
在最小费用流问题中：
- 基变量对应生成树中的边
- 非基变量对应非树边
- 树边流量可以在其容量范围内自由调整（但通常取边界值：0 或容量上限，这称为可行树结构）
3. 算法步骤（简化版本）
步骤1：构造初始可行树
我们需要一个可行树（spanning tree），包含所有顶点，并且树边的流量满足容量约束和流量守恒。
常用方法：
- 添加一条从汇点 \(t\) 到源点 \(s\) 的“人工边”，容量为无穷大，费用为一个大数 \(M\)（惩罚项），这样初始时所有流量可沿这条边循环，形成一个可行循环流，树由这条边和其它零流边组成。
- 或者，先用最大流算法求一个可行流，然后提取出支撑树。
步骤2：计算节点势（potentials）
对树结构，定义节点势 \(\pi(v)\) 使得对于每条树边 \(e = (u, v)\)：
\[cost(e) = \pi(u) - \pi(v) \]
（因为树是连通的，可以从一个根（如 \(s\)）开始 BFS/DFS 递推计算 \(\pi\)，初始 \(\pi(s)=0\)）
步骤3：计算非树边的检验数（reduced cost）
对非树边 \(e = (u, v)\)，其检验数为：
\[\overline{c}(e) = cost(e) - (\pi(u) - \pi(v)) \]
在单纯形法中，如果所有非基变量（非树边）的检验数满足最优条件，则当前解最优。
最优条件（最小化问题）：
- 如果 \(flow(e) = 0\)（流量在下界），则检验数应 \(\geq 0\)，否则增加流量可减少总费用。
- 如果 \(flow(e) = cap(e)\)（流量在上界），则检验数应 \(\leq 0\)，否则减少流量可减少总费用。
（这是因为单纯法中的 reduced cost 符号规则）
步骤4：选取进基边
找一个不满足最优条件的非树边 \(e\)：
- 若 \(flow(e)=0\) 且 \(\overline{c}(e) < 0\)，则增加流量可改进。
- 若 \(flow(e)=cap(e)\) 且 \(\overline{c}(e) > 0\)，则减少流量可改进。
步骤5：确定离基边
进基边 \(e\) 加入树中会形成一个圈（cycle）。
- 如果要增加流量（对应 \(flow(e)=0\) 且检验数<0）：在圈上沿与 \(e\) 同向的边上可增加流量，反向边上可减少流量。允许增加的最大流量受限于圈上反向边的最小剩余容量。
- 如果要减少流量（对应 \(flow(e)=cap(e)\) 且检验数>0）：在圈上沿与 \(e\) 反向的边上可增加流量，同向边上可减少流量。允许减少的最大流量受限于圈上同向边的最小流量。
确定最大可调整量 \(\delta\)，并找到第一个达到界限的边 \(f\)（即调整 \(\delta\) 后，\(f\) 流量变为 0 或容量上限）。
将 \(f\) 移出树基，将 \(e\) 加入树基，更新树结构。
步骤6：更新流量和势
沿圈调整所有边的流量：同向边流量加 \(\delta\)，反向边流量减 \(\delta\)。
然后因为树结构改变，重新计算节点势 \(\pi\)（可以在原势基础上只更新子树，或完全重算）。
步骤7：重复
重复步骤3~6，直到所有非树边满足最优条件。此时得到最小费用最大流。
4. 算法复杂度与特点
- 理论最坏情况可能是指数时间，但在实践中非常快，尤其适合稠密图和大规模问题。
- 与连续最短路算法（Successive Shortest Path）相比，网络单纯形在每轮迭代中可能调整更多流量，收敛更快。
- 需要仔细实现树结构的维护（可用父指针、深度、子树节点列表等）。
5. 举例说明（示意图思路）
假设有一个简单图：
- 点：\(s, a, b, t\)
- 边：
\((s,a)\): cap=2, cost=1
\((s,b)\): cap=1, cost=3
\((a,b)\): cap=1, cost=1
\((a,t)\): cap=2, cost=2
\((b,t)\): cap=2, cost=1
初始可行树：选边 \((s,a),(a,b),(b,t)\) 和人工边 \((t,s)\) 构成树，初始流量全0。
第一次迭代：发现非树边 \((s,b)\) 检验数为负，加入树，形成圈 \(s \to b \to t \to s\)，调整流量。
多次换基后，得到最大流3，最小费用 = 1*2 + 1*0 + 2*2 + 1*1 = 具体值（需计算）。
6. 总结
网络单纯形算法是求解最小费用最大流的强大工具，它将线性规划的单纯形法适配到网络流结构，通过维护一棵生成树和节点势，用检验数判断最优性，并通过换基改进解。虽然理论最坏复杂度不好，但实际性能优秀，被许多优化库采用（如LEMON、OR-Tools等）。