强制运量改变了哪些决定可以撤销。若路线现有五单位流量,但合约要求最少三单位,反向残量路线只能撤销两单位。本节连接下界可行性转换与固定平衡网络中的成本改良环,推导最优性判据及可独立核对的数值下界。
模型与剩余操作
设 是有限有向图,没有自环,允许分别标记的平行及反向弧。每条弧 有有限实成本 及界限 。可行流 满足各弧界限,并在每个节点有指定的流出减流入 。假设至少有一个可行流,因此 。成本是 。
定义 18.1.1
(具有强制运量的残量网络)
每条原弧 的两个剩余方向均保留其标签:正向 的容量为 、成本为 ;反向 的容量为 、成本为 。只保留容量严格为正的残量弧。势函数 给原弧的约化成本为 。
沿正容量残量环增广 时,正向弧上的原流量增加,反向弧上的减少。只要 不超过瓶颈容量,所有界限都保持成立;每个节点增加的剩余流入与流出相等,因此平衡不变。总成本改变等于 乘以残量环成本之和,反向成本必须带负号。若简单环同时使用同一原弧的两个方向,两者互相抵消,该环不可能是负成本环。
最优性与可核对的下界
定理 18.1.2
(有界流的最优性与价格)
对可行流 ,以下三者等价:
- 在所有可行流中成本最低。
- 其正容量残量网络没有负成本有向环。
- 存在势函数 ,使每条正容量残量弧的约化成本非负。等价地,对每条原弧,
- 蕴含 ;
- 蕴含 。
不论 是否最优,任何势函数都给每个可行流以下成本下界:
若某可行流达到 ,它便是最优流。
概念视角结构
下界即松弛平衡方程所得
设 为顶点—弧矩阵,使 是 处的流出减流入。由于 ,下界可写成
平衡方程以乘子 移入目标函数,只剩下逐弧分离的上下界约束。每个可行的 都使附加项为零,这就再次得到下界。定理进一步说明,最佳的乘子能消除差距:存在 使 等于最小成本。
证明
(环分解、最短路价格与弱对偶恒等式)
若存在负残量环,沿该环增广正的瓶颈量便得到成本更低的可行流,故最优流不可能有负环。反过来,对任意另一可行流 ,若 ,把差额放在正向残量弧;若差额为负,则把 放在反向残量弧。界限保证所需残量容量足够。两流平衡相同,故得到非负残量循环流。沿正流量的弧走至节点重复,取出有向环并减去环上最小流量;平衡维持,而至少一条正流量弧消失。重复此过程可在有限步内分解成非负权重的有向环。成本差 是各环成本的加权和;若没有负环,差额便非负。
若所有剩余约化成本非负,则势函数差在环上相消,每个环成本都非负。反之,若没有负环,加入一个以零成本弧连至所有节点的临时源点,令 为其最短路距离。任何重复环均可移除而不增加路径成本,所以只需考虑有限条简单路,距离有限。距离不等式 使每条残量弧约化成本非负。反向弧的约化成本是 ,由此得到两条原弧符号条件。固定弧没有剩余方向,不受符号限制。
最后,对任何可行 ,由平衡方程得
每个 均不小于它在 上的最小值,故得到下界。若可行 达到此下界,便没有更便宜的可行流。特别是上述符号条件令每个 都使 在其区间内最小,因此最优价格能使等号成立。
证明透视
上下界各自的作用
下界只在证明的一处进入:把 写成剩余分配。减少量 放在反向弧上,而因 ,它不超过反向容量 ;同理,增加量不超过 。正因如此,残量网络必须使用 而非 。由“没有负环”推到价格只需要有限性:路径可缩短为简单路,所以最短距离存在。最后的恒等式需要两流平衡相同,区间最小值便读出符号条件:正约化成本偏好下端点,负约化成本偏好上端点;内部流量同时有两个剩余方向,迫使约化成本为零;固定弧则不受限制。遗漏势函数项会改变下界的数值,剩下的和一般不是有效下界。
例子
例题 18.1.3
(合约阻止看似可行的撤销)
弧为 、、,上界均为 ,下界依次为 ,成本依次为 。令 、、。守恒迫使流量为 ,界限给出 。成本为 ,故 最优,成本为 。
不枚举 也可验证:取 ,原弧约化成本为 。因此
常见错误
(撤销至合约下限以下)
在 ,第一条路线恰好处于下界,其反向残量容量为 。若错误地用 作反向容量,便会虚构成本为 的负残量环 。沿此环增广会令 低于合约下限,故并非合法操作。
例题 18.1.4
(增广至另一端点)
保持网络和界限,但将成本改为 。在 ,残量环 的成本为 ,瓶颈为 :其中 的反向容量为 。增广一次得到 ,成本由 降至 。取 ,约化成本为 ,而 ,故新流最优。 的正约化成本与其流量处于零下界相容;并非所有原弧的约化成本都要为零。
反例模式
只检查一个方向并不足够
在第二个例子中,于 取 ,所有原弧成本都是正数,但反向残量弧成本为负。只测试原弧正向会错判为最优;上面的负环明确给出更便宜的可行流。
第三个例子专门处理一条弧完全没有剩余方向的边界情况。
例题 18.1.5
(固定弧的约化成本可为任意符号)
取弧 ,、成本 ;以及 、,界限 、成本 。令 、、。 的守恒给出 , 的守恒给出 ,所以 是唯一可行流,成本为 。
与 的流量都在区间内部,故证书要求 。取 ,便迫使 ,再得 ;固定弧的约化成本是 。于是
即使正约化成本出现在上界,证书仍然准确。若第一条弧的界限改为 ,同一符号便违反条件 ;事实上,此时把三单位全部改经 运送,成本只有 。
算法与限制
消环法由可行流开始,在整个残量网络搜索负环,增广至瓶颈后重复。若界限、平衡及起始流均为整数,每次瓶颈及随后流量均为整数。有限容量只容许有限多个整数可行流,而每次负环增广都严格降低成本,即使成本为实数亦然。因此此整数起始版本终止,定理证明终点最优。整数数据若通过下界可行性测试,便存在整数可行起点。这个有限状态证明没有给出多项式时间界,也没有证明任意实数起点必定有限步终止。
所有节点的势函数同加一个常数,不会改变约化成本或 ,因为总平衡为零。价格证书须涵盖每个剩余连通部分,而非只涵盖某供应节点可到达之处。实际数值运算须另行处理舍入;此处使用精确的严格符号及等式。
习题与解答
快速检查
(在第一个例子取 。求成本,并计算沿 增广至瓶颈时的成本变化。)
解答 · 答案
流量为 ,成本为 。环成本为 ;瓶颈为 ,因为 的反向容量为 。成本下降 至 。
快速检查
(若 、、,哪个端点使 最小?若这个势函数为某可行流提供最优性证书,该流在此弧上必须如何?)
解答 · 答案
最小值 在 达到。证书取等要求 ;等价地,在此证书下,负约化成本不容许正的正向残量容量。
快速检查
(一条弧有 及 。最优证书是否要求其约化成本为零?它对区间最小值的贡献是多少?)
解答 · 答案
不需要。两个方向都没有正残量容量。区间只有 ,最小值为 。
快速检查
(在第二个例子中把 换为 。重算 并解释为何不变。)
解答 · 答案
约化成本仍为 。平衡项是 ,区间项总和为零,所以 。所有势同加常数时, 的变化是该常数乘以 。