本节接续流笔记。供需已指定流量平衡,现在要最小化输送费用;内容涵盖消负环、运输交换及原始—对偶指派法。
动机
两个流可送达相同数量,却使用不同资源。调度器在处理器网络分配工作时,传送成本可以不同。每个顶点供出或收取的量已固定,因此不再追求更多源流值,而是重新安排现有可行流,直到没有更便宜方案。
固定供需下,两个可行流之差在每点净平衡为零,所以改善对象是环,不是额外源汇路。反向残量弧仍表示取消旧决策,其费用必须是原费用的负数。若漏掉此负号,便不能把环解释成真正的成本交换。
顶点势能把全局负环问题转成局部不等式。弧成本加上顶点价格差,沿环会抵消,因此环成本不变。非负约化成本遂证明没有改善循环。指派问题把这想法化成行列标签,零约化成本边构成寻找最佳配对的图。
定义
定义 6.1.1
(固定平衡的最小费用流)
有限有向网络有有限容量 ,顶点 的净流出指定为 ,且 。最小化 ;除非明确检查不可行,先假设有可行流。
原弧 的正向残量容量为 、成本为 ;反向残量容量为 、成本为 。势能 定义剩余约化成本
平行及反向原弧保留各自标签。残量有向环可含反向弧,瓶颈是沿环最小残量容量。按瓶颈增广保持各顶点指定平衡;若环成本负,总目标便严格下降。
运输模型有非负供给 、需求 ,总量相等; 的行和为供给、列和为需求,目标 。指派是行列数相同且各总量为一的特例。完美匹配在每行每列各选一边;完整指派模型假设每个配对都有有限成本。
定理/命题
定理 6.1.2
(负环及势能刻画最优性)
固定平衡的可行容量流为最小费用,当且仅当其残量网络没有负成本有向环。这又等价于存在势能,使每条正残量容量弧的约化成本非负。
定理 6.1.3
(紧边匹配证明指派最优)
若行标签 、列标签 满足 ,每个可行指派成本至少为 。全由紧边构成的完美匹配取得此界,故最优。下述交替树标签更新法对有限完整成本矩阵有限步找到它。
证书不要求成本整数。整数供需及容量则支持整数流;成本也整数时,更可用每次至少下降一来估计步数。首先仍须取得可行流,例如另作容量可行性计算;没有实际可行决策,单有势能不算最优证书。
证明思路
负残量环容许正瓶颈增广,平衡不变,费用改变是瓶颈乘环成本,故最优流不能有负环。
反过来,比较现流与任一竞争流。某原弧增加的差额放在正向残量弧,减少的差额放在反向弧,均以非负量表示;容量界保证改动合法。由于两流供需相同,这些差额形成非负残量循环流。
任何有限非负循环流都可分解成非负倍数的有向环。由一条正流弧出发,守恒容许沿正弧继续,直到顶点重复;抽出环,减去其最小弧量,至少一条正弧消失。反复有限次便完成。成本差等于各环成本乘其非负权重;无负环便无更便宜竞争者。
势能差沿环抵消,所以全弧非负约化成本排除负环。反向存在性则加临时顶点,以零成本弧通往所有原顶点。没有负环时,每个游走可删环而不增长度,最短距离可从有限个简单路径取得且有限。其标签满足 ,恰是所需约化不等式。临时源避免漏掉与某个原源不连通的分量。
证明透视
全局比较如何化为环的总和
反方向的证明从不逐一检查竞争流,而是改写它与现流的差。容量界使这个差成为残量弧上的非负分配;反向弧在此不可缺少:某弧上的减少以成本 记录。供需相同使这个差在每个顶点守恒,分解中的游走因此总能继续。有限性令分解终止,因为每次抽出环都删去一条弧。收尾一步是线性:成本差是各环成本的非负组合。势能只在其后出场,作为“没有负环”的最短路径证书。
指派下界把每个标签不等式乘以非负指派量后相加。行列和都一,便留下标签总和;紧完美匹配取等号。只有紧边但未能完美匹配仍不足够,因多行可能争用同一列。
有限原始—对偶指派法
初设 、。也可把每列剩余约化成本的最小值加到该列标签,这保持全部对偶不等式,就是下例额外的列缩减。再在紧边图找匹配。从未匹配行开始交替搜索:行沿紧边到列,已匹配列沿匹配边回其行。到未匹配列便得到增广路,翻转边的匹配状态使匹配数加一。
若尚无增广路,令到达行集为 、列集为 。每个到达列都配到到达行,加上未匹配根,故 。匹配未完整,所以至少一列不在 。取
内行标签加 , 内列标签减 。由 到外列的余量减少但不负;外行到 的余量增加;其余不变。匹配边及现有交替树仍紧,至少一条新紧边离开 。
继续搜索,新边不是到自由列而增广,就是到已配列并带来新行,令树增大。同次增广之前到达集只增不减,所以更新有限次;增广最多等于行数,故算法有限且以紧匹配证最优。若有禁止配对,必须另行处理不可行性,不可任意塞入一个未证足够大的成本。
运输消环算法
完整平衡运输可先逐行逐列尽量分配,每步耗尽一个尚余供给或需求,然后移往下一行或列;零供需跳过,有限步得到可行起点。每个矩形交换是增加与减少单元交替的残量环。
找到负环就增广至瓶颈再重复。整数供需配整数起点时,每次保持整数。每项运量都受总运量限制,故整数可行表只有有限个;严格成本下降不会重访,因此即使成本为实数也有限终止。成本若也整数,每次至少降一,再有目标范围步数界。但这些推理尚未证明多项式时间。
例题详解
例题 6.1.4
(一次运输交换降低五)
供给 、需求 ,成本
起始 成本十一。增加 ,减少 ;环成本 ,瓶颈一。新表 成本六。
取行标签 、列标签 ,逐项和不超成本,全部正运量单元都紧。下界 ,因此已最优,而不只是有所改善。
例题 6.1.5
(Hungarian 更新补出匹配边)
取
行最小值给 ,再扣列最小值给 ,约化矩阵
先配第一行至第二列、第三行至第一列。未配第二行的搜索到 ,跨界余量为 ,故 。更新成 ,下界五。新紧边由第二行到第一列,再沿原匹配到第三行,最后到未匹配第三列;沿这条增广路翻转边,得到紧匹配 ,其成本 ,证明最优。负列标签合法,无须额外非负限制。
例题 6.1.6
(负原成本仍可有非负约化成本)
两点 各平衡零,双向容量一,成本 。零流的唯一两弧环成本一,无法改善。取 , 的约化成本为 , 的为 ,故零流最优。
若逆向成本改为一,环成本负一,两弧各送一便得总成本负一。此时两个剩余方向都反转,环成本正一,证明新最小值。阻碍最优的是负环,不是某条负原弧。
概念视角组合
价格更新修补匹配障碍
更新前,到达行沿紧边只能到达已到达列,而且行多一个。零成本图缺少足够选择;最小跨界余量正是暴露新选择所需价格变化,同时保留既有树边。数值标签更新于是对应一个明确组合障碍,而非任意调价。
常见错误
固定供需时,任意源汇增广路会改平衡,不是合法改善;残量环才保平衡。反向成本永远取原成本的负数,不能只检查未使用正向弧。势能必须涵盖全部正残量弧及所有分量。
紧边存在不等于紧完美匹配存在。行列标签也不必非负,只有其和受成本上界限制。把多余符号限制加上去,可破坏正确对偶更新。整数供需给整数决策的存在及算法不变量,不代表任意实数最优表每项都整数。
总结
固定平衡下,所有改善都可分解为残量环;非负约化成本等价于无负环。运输以此交换运量,指派把对偶逻辑化为紧边及有限交替树更新。整数性、终止性与多项式复杂度仍是分开的结论。
练习
快速检查
(核验运输例四个标签不等式,找未用单元并解释为何可不紧。)
解答 · 答案
标签和为 ,逐项不超 。未用 有正余量,但乘零运量后仍零,所以不影响原始对偶同值。
快速检查
(对成本 ,找紧完美匹配及证书标签。)
解答 · 答案
选 成本三。行标签 、列标签 给和 ,不超 ;选边都紧,总下界三,证最优。
快速检查
(残量环成本有 ,负环瓶颈半。费用改变多少?零成本环是否证明不唯一?)
解答 · 答案
费用改变 。正瓶颈零成本环给不同而同值可行流;原流若最优,便证不唯一。若未证原最优,只能得到另一个同样可能次优的流。
快速检查
(与主要供给顶点不连通的负残量环,为何仍影响固定平衡最小费用?)
解答 · 答案
循环流在每点净平衡零,包括没有供需的点。任何分量的负环都能降低总成本而不动其他交付。只从一个原源求势能可能漏掉它,证明中临时全可达源正是为避免此问题。