网络单纯形法 | Codeboy's Blog

最小费用流基

在有向网络上，每条弧 ((i,j)) 有费用 (c_{ij})、下界 (\ell_{ij})、上界 (u_{ij})，节点有供需 (b_i)。可行流满足容量界与流量平衡，并最小化 [ \sum_{(i,j)}c_{ij}x_{ij}. ] 网络单纯形法把单纯形法的一个基具体化为覆盖所有节点的生成树。

树弧的流量由节点平衡和非树弧状态唯一确定。每条非树弧固定在下界或上界；树弧允许位于界内，也可能因退化恰好落在某个界上。工程实现常另加人工根与高费用人工弧来构造初始可行树，找到可行解后再移除其影响。

势与约化费用

给每个节点势 (\pi_i)，令 [ \bar c_{ij}=c_{ij}+\pi_i-\pi_j. ] 沿树从根传播势，使所有树弧的约化费用为 0。对最小化问题，处在下界的非树弧要求 (\bar c_{ij}\ge0)，处在上界的非树弧要求 (\bar c_{ij}\le0)；若全部满足，当前可行树解最优。

违反符号条件的非树弧可以入基。下界弧且 (\bar c<0) 时沿正方向增流会降低费用；上界弧且 (\bar c>0) 时沿反方向减流。只看原费用 (c_{ij}) 会忽略为维持平衡而在树上引起的连锁变化。

一个完整 pivot

设节点 (s) 供给 4，(t) 需求 4，(v) 平衡为 0。三条弧容量都为 4，费用为 [ c_{st}=5,\qquad c_{sv}=1,\qquad c_{vt}=1. ] 初始可行流为 (x_{st}=4,x_{sv}=0,x_{vt}=0)。取树弧 (st,sv)，其中 (sv) 是位于下界的退化树弧；非树弧 (vt) 位于下界。

令 (\pi_s=0)。由树弧约化费用为 0，得到 (\pi_t=5,\pi_v=1)。于是 [ \bar c_{vt}=1+\pi_v-\pi_t=-3, ] 非树弧 (vt) 违反下界最优性条件，选择它入基。

把 (vt) 加入无向基树形成基本环 [ v\to t\to s\to v. ] 沿 (v\to t) 增加 (\theta)，为保持节点平衡，同时沿 (s\to v) 增加 (\theta)，沿 (s\to t) 减少 (\theta)。三个容量约束共同给出 (\theta=4)。

增广后 [ x_{sv}=4,\quad x_{vt}=4,\quad x_{st}=0. ] (st) 首先到达下界，因而离基；新基树为 (sv,vt)。每单位流节省 (5-(1+1)=3)，总费用从 20 降到 8，恰好改善 12。

状态更新不变量

一次 pivot 后必须同时恢复三项条件：流量平衡不变，所有弧仍在上下界内，基弧仍构成生成树。fundamental cycle 上的正负方向由入基弧方向决定；若把整条环都加同一符号，内部节点会产生净流入。

离基弧由 ratio test 决定：沿环各弧离其即将碰到的界还有多少余量，取最小值。多条弧同时到界时发生退化，(\theta) 甚至可能为 0；仍需按防循环规则选择一条离基，否则算法可能在多个等价树基之间循环。

势只需在 pivot 后相对调整新树某一侧，使新入基弧约化费用变为 0。树数据结构要支持找 fundamental cycle、求瓶颈、换边和对子树势加常数；这些接口决定大型实例上的实际效率。

entering arc 规则

Dantzig 规则可选违反最严重的约化费用，first-eligible 规则按扫描顺序选第一条，工程求解器还会组合候选列表、块搜索和退化处理。规则影响每轮扫描成本与 pivot 数。

这些启发式常使网络单纯形在运输、指派和最小费用流实例上很快，但不能据此宣称经典 pivot 规则具有一般多项式轮数。已知构造能让某些规则经历指数级 pivot；理论最坏界与工程表现应分开陈述。

与其他最小费用流算法对照

逐次最短路每轮按剩余网络最短路增广，cost scaling 通过 (\varepsilon)-最优性逐步收紧；网络单纯形始终维护一棵基树并沿基本环换边。三者共享势和约化费用语言，状态演化却不同。

容量无穷、供需不平衡或负费用环会影响可行性与有界性，预处理必须先检查。整数输入下基树 pivot 保持整数流，但浮点费用会让约化费用比较和退化判定需要容差；容差策略不属于抽象精确算术证明。

参考资料

George B. Dantzig, Application of the Simplex Method to a Transportation Problem, in Activity Analysis of Production and Allocation, 1951.
Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
James B. Orlin, A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows, Mathematical Programming, 1997.

最小费用流基 ​

势与约化费用 ​

一个完整 pivot ​

状态更新不变量 ​

entering arc 规则 ​