网络单纯形法

生成树给出一组恰好能由节点平衡确定的基弧；加入一条非树弧会形成唯一基本环，因此所有维持守恒的流量变化都沿这条环发生。约化费用判断该方向是否改善目标，ratio test 则找到第一条触碰容量界并离基的弧。

一个完整 pivot ​

设节点 $s$ 供给 4，$t$ 需求 4，$v$ 平衡为 0。三条弧容量都为 4，费用为

初始可行流为 $x_{st}=4,x_{sv}=0,x_{vt}=0$。取树弧 $st,sv$，其中 $sv$ 是位于下界的退化树弧；非树弧 $vt$ 位于下界。

令 ${\pi }_s=0$。由树弧约化费用为 0，得到 ${\pi }_t=5,{\pi }_v=1$。于是

非树弧 $vt$ 违反下界最优性条件，选择它入基。

把 $vt$ 加入无向基树形成基本环

沿 $v\to t$ 增加 $\theta$，为保持节点平衡，同时沿 $s\to v$ 增加 $\theta$，沿 $s\to t$ 减少 $\theta$。三个容量约束共同给出 $\theta =4$。

增广后

$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；理论最坏界与工程表现应分开陈述。

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

逐次最短路公理库最小费用流Minimum-cost flow在满足流量守恒与容量限制下最小化边费用总和的网络优化问题。每轮按剩余网络最短路增广，cost scaling 通过 $\epsilon$-最优性逐步收紧；网络单纯形始终维护一棵基树并沿基本环换边。三者共享势和约化费用语言，状态演化却不同。

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