网络单纯形法 | Codeboy's Blog

形式陈述

最小费用流基

沿用最小费用流的有限有向网络模型，每条有身份的弧 $(i,j)$ 有有限实费用 $c_{ij}$ 与有限界 $0\le\ell_{ij}\le u_{ij}$ ，节点有供需 $b_i$ 。可行流满足容量界与流量平衡，并最小化

\sum_{(i,j)}c_{ij}x_{ij}.

先消去固定界 $\ell_{ij}=u_{ij}$ 的弧，把其固定流量计入需求和费用；它没有残量方向，不需要约化费用为零。自环也可单独处理：正费用取下界，负费用取上界，零费用任选合法值。随后只对非自环且上下界不同的弧维护基。

网络单纯形法把有界变量单纯形法的一个基具体化为生成树。工作分量在上述预处理之后确定：若剩余网络弱连通，删去一条冗余平衡等式，关联矩阵秩为节点数减一；若剩余网络有 $n$ 个节点、 $c$ 个弱连通分量，秩为 $n-c$ ，可逐分量使用生成森林，或加入人工根形成连通工作网络。原图中连接两个部分的固定界弧一旦消去，这两个部分就可能成为不同的工作分量，需分别检查调整后的供需平衡。

每个分量选出的基弧覆盖其全部节点，忽略方向和弧身份后恰给出普通简单生成树；树的每条边再附上被选中的那条原弧身份及方向，便恢复网络基。平行或反向候选弧始终各有身份，同一基树不会同时选择同端点的两条弧。加入一条非基平行弧时，仍以它和原树弧的两个不同身份构成两边基本环，不能先把这些候选合并成一条边。

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

势与约化费用

给每个节点势 $\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$ 时沿反方向减流。把它加入无向基树得到唯一基本环，沿相应正反方向调整流量。步长要同时检查全部树弧的剩余余量和这条非树弧到另一侧界的余量。若某条树弧先到界，可让它离基、让所选弧入基；若所选非树弧自己先到另一侧界，它只在上下界状态之间翻转，基树保持不变。这称为 bound flip。

约化费用计入了维持平衡所需的整环变化，原费用 $c_{ij}$ 则只描述单条弧。

直觉

生成树给出一组恰好能由节点平衡确定的基弧；加入一条非树弧会形成唯一基本环，因此所有维持守恒的流量变化都沿这条环发生。约化费用判断该方向是否改善目标，ratio test 决定能沿这个方向走多远，以及随后是换树边还是只翻转一个非基弧的边界状态。

例子与边界

一个完整 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。

入选弧自己先到界

只把上例的 $vt$ 容量改为一，其余数据不变。沿同一基本环最多推一单位，得到 $x_{st}=3,x_{sv}=1,x_{vt}=1$ 。此时两条树弧都仍在界内，只有非树弧 $vt$ 到达上界，所以基树仍是 $st,sv$ ，势仍为 $(\pi_s,\pi_v,\pi_t)=(0,1,5)$ 。 $\bar c_{vt}=-3$ 满足上界弧应有的非正条件，当前方案已最优，总费用为 $3\cdot5+1+1=17$ 。若强行要求每个改进步骤都删掉一条树弧，就无法正确描述这一步。

状态更新不变量

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

Ratio test 包含入选非基弧自身：沿环各弧离其即将碰到的界还有多少余量，取最小值。最小者为树弧时选择它离基；最小者仅为入选弧时执行 bound flip。多条弧同时到界时发生退化， $\theta$ 甚至可能为 0；仍需按防循环规则选择一条离基，否则算法可能在多个等价树基之间循环。

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

entering arc 规则

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

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

推论与应用

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

逐次最短路每轮按剩余网络最短路增广，cost scaling 通过 $\varepsilon$ -最优性逐步收紧；网络单纯形维护基树，沿基本环调整流量，必要时换边。三者共享势和约化费用语言，状态演化却不同。

费用缩放的局部版本把误差减半后先饱和负约化费用记录，再通过Push/Relabel清除正负超额；其许可图无环和相对阶段起点的价格降幅支付操作次数。阶段中不维护生成树基，也不使用本页的bound flip条件。

供需不平衡会使可行性失败，应先检查各分量的净需求。在本页有限容量模型中，负残量费用环表示仍可改进，目标仍有有限下界；扩展到无穷容量时，完全无容量阻挡的负环才可能使费用无界。整数输入下基树 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.
NetworkX，network_simplex 源码，2026年10月查阅：主循环仅在入选与离开弧不同的时候改动基树；固定零容量弧与自环另行处理。其势符号与本页相反。
James B. Orlin, A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows, Mathematical Programming, 1997.

形式陈述 ​

最小费用流基 ​

势与约化费用 ​

一个完整 pivot ​

入选弧自己先到界 ​

状态更新不变量 ​

entering arc 规则 ​

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

反向链接