一条运输路线可能既有最低承运量,也有最大容量。例如,配送合同要求某条路线至少运输两个单位,另一条路线却最多只能运输三个单位。这些要求直接限制决策变量的取值。把一条路线的成本调低,并不能强制它达到最低承运量;把成本调高,也不能强制它遵守容量上限。
前面的允许路线判据把每条允许使用的路线视为能够承载全部货物。本节保留有限容量,并加入流量下界。核心问题仍然很容易表述:所有节点的平衡要求与所有路线的承运要求,能否同时满足?我们最终会得到一个可行流,或者明确指出一组节点,说明其要求为何相互冲突。
动机
假设从 到 的路线必须至少运输三个单位。一种看似自然的做法是先在该路线上安排三个单位,把容量减去三,再保持网络的其余部分不变,求解剩余问题。但是,这批预先安排的货物已经使 流出了三个单位,也使 流入了三个单位。剩余流量必须根据这些变化,重新满足各节点尚未完成的平衡要求。
因此,有效的转换必须同时改变两件事:每条路线的剩余容量,以及每个节点的剩余平衡量。完成这一步之后,原问题就变成普通的最大流可行性检验。辅助网络中的割,还能转换成关于原有上下界的精确条件。
定义
设 是不含自环的有限有向图;允许存在分别标记的平行弧,也允许同时存在方向相反的弧。对每条弧 ,给定有限实数界限 。对每个节点 ,给定实数平衡量 。本节采用流出量减流入量的约定:
其中,第一个求和遍历离开 的弧,第二个求和遍历进入 的弧。因此, 表示净供给, 表示净需求。将所有节点的等式相加,每条弧的流量都会抵消,所以 是必要条件。以下始终假设该等式成立。若每个节点都满足 ,则称这样的流为循环流;循环流不一定是零流。
定义 16.1.1
(边界记号与剩余问题)
对 ,用 表示离开 的弧集,用 表示进入 的弧集。两端都在 内的弧不属于这两个边界。记 ;对弧集上的界限或流量,也采用同样的求和记法。
令 、,并令
那么,原问题等价于:求满足 ,且在节点 的净流出量为 的流。同时有 。
这个等价关系来自对每个等式进行变量代换,而且两个方向都成立:从可行的 中减去 ,就得到可行的 ;向可行的 加回 ,就得到可行的 。仅由下界组成的流量,本身未必满足节点平衡。向量 精确记录了预先安排这些下界流量以后,尚待完成的平衡任务。
定理 / 命题
定理 16.1.2
(带上下界流量的可行性)
在上述图有限、上下界有限、节点平衡量总和为零的假设下,可行流 存在,当且仅当每个 都满足
等价地,每个 都满足以下双边边界条件:
如果所有 都是整数,而且上述条件成立,那么至少存在一个各弧流量均为整数的可行流。
条件 (1) 表示,一组节点所要求的净输出量,不能超过其最多能够向外运出的总量减去必须从外部运入的总量。组内弧的承运要求不计入这一差值,因为这些弧只是在组内转移物资。对循环流,条件变为 :必须进入这组节点的物资,必须能够再从这组节点流出。
将 (1) 应用于 ,再利用 ,就得到 (2) 中的下侧不等式。双边写法有助于理解,但并不需要另外检验一族独立条件。
证明思路
证明
(以求和证明必要性,以辅助最大流证明充分性)
必要性。 将 内所有节点的平衡等式相加。内部流量抵消,剩下
充分性。 先进行上述下界代换。加入两个新节点 。保留每条原有弧,将其容量设为 、下界设为零。若 ,加入容量为 的弧 ;若 ,加入容量为 的弧 ;若 ,则不必加入新弧。定义
值为 的流会使所有离开 的弧以及所有进入 的弧饱和。此时,任一原有节点的流量守恒等式表明:只计算原有弧时,该节点的净流出量恰为 。反过来,任一可行的 都可以通过令这些新增弧饱和,扩展为值为 的辅助流。新增弧的方向十分关键:尚需正净输出量的节点,先从 接收物资,再通过原有网络将这些物资送出。
任一 – 割的源点侧都可以写成 ,其中 。该割的容量为
另一方面,将 的定义在 上求和,得到
因此,条件 (1) 恰好就是 。由此,(3) 中每个割的容量都至少为 。
下面补充最大流步骤背后的存在性论证,其中也包括容量为任意实数的情形。辅助网络的可行流集合非空、闭且有界,所以流值可以取得最大值。在一个最大流的残量网络中,不可能存在从 到 的路径:否则,沿这条有限路径,按各弧正残量容量的最小值进行增广,就会增大流值。令 为从 出发,在残量网络中可达的节点集合。由于 ,它是某个割的源点侧。每条离开 的辅助图弧都已饱和,每条进入 的辅助图弧都具有零流量;否则,就会有残量弧离开 ,与可达集合的定义矛盾。将 内的守恒等式相加,可知流值等于这个割的容量。割容量的下界说明该流值至少为 ,而离开 的总容量又恰为 。因此,最大流值正好是 ,加回 就得到所需的 。
若原始数据均为整数,则所有辅助容量都是非负整数。从零辅助流出发,沿残量路径逐次增广。每次的正瓶颈容量都是整数,所以流量始终为整数,流值每次至少增加一。至多进行 次增广后,要么已不存在增广路径,要么已经达到流值 。由残量割论证,在条件 (1) 成立时,算法停止时的流值必为 。恢复出的 因而是整数流。这里的次数界以容量单位计量,并不是关于二进制输入长度的多项式界。对任意实数数据,紧致性论证保证最大流存在,却没有断言任意选择增广路径的规则都能在有限步内终止。
证明透视
一次归约中的三项不同任务
减去下界是严格的代数等价变换,本身不依赖流定理。随后,割容量的计算说明:辅助图中每一种可能的障碍,在原图中都有明确含义。最大流的存在性再将“没有这类障碍”转化为可行流的存在。整数性还需要单独利用整数瓶颈容量来证明,不能仅从实数数据的存在性论证中直接推出。
若辅助网络的最大流值为 ,则其残量割给出一个集合 ,满足
这就是一个数值化的不可行证书:这组节点所要求的净输出量,超过其允许最大值,差额正是上式的正数。若想通过把某条路线的容量增加这个差额来消除当前障碍,该路线必须离开这组节点;即使如此,其他割的约束仍然需要满足。直接给出修复后的可行流,比仅仅消除一条已经失败的不等式,能证明更多。
例题详解
例题 16.1.3
(先安排必需流量,再求剩余平衡)
取三个节点 ,平衡量为 ,弧及其标记如下:
| 弧 | 下界 | 上界 | 剩余容量 |
|---|---|---|---|
| 2 | 4 | 2 | |
| 1 | 4 | 3 | |
| 0 | 2 | 2 | |
| 0 | 1 | 1 |
下界流量产生的净流出量为 ,所以 ,而不是原来的平衡向量。于是 。加入容量均为一的 和 ,再加入容量为二的 。沿 运输一个单位,沿 再运输一个单位。
按表中弧的顺序,这给出原有弧上的剩余流量 ,因此 。节点 的净流出量为 ;节点 的净流出量为 ;节点 的净流出量为 。每条路线的上下界也都满足。虽然 没有分配到剩余流量,但它所要求的两个单位已经在下界流量中安排好了。
在这个 处, 的反向残量容量为 ,而不是二。只要撤销任何正量的流,就会违反最低承运要求。 的反向残量容量则为 。
例题 16.1.4
(必需流入量可能使循环流不存在)
假设仅有两条弧: 的界限为 , 的界限为 ,并要求两个节点的平衡量都为零。两个区间分别都非空,但对 ,必需流入量为三,而可能流出量至多为二。条件 (1) 成为 ,显然不成立。
下界流量的净流出量为 ,所以 ,且 。辅助图含有 和 ,两者容量均为三。从 到 最多只能运输两个单位。源点侧为 的割,其容量为二,公式 (4) 给出的缺口为一。将 的上界提高到三后,可以取 ;这个具体流直接证明修复后的问题可行。
例题 16.1.5
(运输配额与完整的成本计算)
两个供给点的供给量为 ,两个需求点的需求量为 ,四条路线全部存在。它们的下界、上界及单位成本分别为
减去 后,供给点的剩余供给量为 ,需求点的剩余需求量也为 ;剩余路线容量为 。剩余运输方案 满足这些容量与平衡要求。加回 ,得到 。
要进一步证明这个方案的成本最低,可以直接求解四个平衡等式。令 ,则每个满足平衡的方案都可写为
四条路线的区间约束合并后,恰好得到 。成本为 ,在 处取得最小值 。也可以分开计算:预先安排的下界流量成本为 ,最优剩余流量成本为 。遗漏常数八不会改变最优决策,却会把原问题的目标值算错。仅有可行性并不能证明成本最优;这里的单参数论证才证明了这一点。
命题 16.1.6
(有容量限制的运输准则)
设供给点集合 与需求点集合 均有限,供给量与需求量满足 ,且 。每条允许路线的界限均有限,并满足 。在路线图上,将供给点的平衡量设为 ,需求点的平衡量设为 。对包含供给点集合 和需求点集合 的节点组应用 (1),可知可行运输方案存在,当且仅当
证明
(读出起点—目的地节点组的边界)
路线图的每个节点集合都可写成 ,其中 、;而平衡总和为 ,所以可行性定理适用。 的平衡是 。每条路线都由起点通往目的地,因此一条路线离开 ,当且仅当它由 通往 ;进入 ,当且仅当它由 通往 。于是 的条件 (1) 是
移项即得 (5)。由于对所有 的 (5) 就是对所有 的 (1),它是充分必要条件。
例如, 表示在端点属于这两个集合的所有允许路线上,将上界求和;不允许使用的路线可以直接不放入图中,也可以等价地把其上下界都设为零。公式同时考虑了组内的需求点,以及跨越组边界的路线容量。仅凭邻点集合,已经不足以描述这些限制。
概念视角组合
从邻点障碍到容量障碍
令 为总运输量。若所有下界均为零,且每条允许路线的容量都等于 ,在 (5) 中取 。此时没有路线从 通向 ,于是恢复出 。若 ,则 ,得到的条件更弱。其余情形下,至少有一条允许路线从 通向 ;这条路线的容量 就使 (5) 自动成立,因为 且 。因此,前面的邻点判据被包含为一个特例。有限路线容量与必需流入量,正是那个较简单的公式省略的信息。
常见错误
反例模式
所有邻点检验都通过,容量仍可能不足
设供给量和需求量均为 ,四条路线全部允许使用,下界全部为零。将通向需求点一的每条路线容量设为 ,通向需求点二的每条路线容量设为二。任一非空供给点组的邻点都包含两个需求点,因此所有不考虑容量的邻点不等式都成立。然而,需求点一总共最多只能收到一个单位,低于其需求量二。
在 (5) 中,取 、。不等式将要求 。用图上的判据表述,这组节点要求净输出两个单位,向外的容量却只有一。障碍来自容量不足,而不是路线不存在。
常见错误
(撤销必须运量的残量弧)
在带下界的残量图中,正向容量为 ,反向容量为 。反向弧只能撤销超过最低承运量的那部分流。方向相反的原有弧仍须分别标记;存在一条反向残量弧,并不意味着可以把另一条原有弧的流量混为一谈或直接改写。
常见错误
(过度解读整数性与证书结论)
整数数据保证存在一个整数可行流,但同一个问题中也可能同时存在分数可行流。同样,数值算法留下的一点未满足平衡量,并不是精确的不可行证书。必须实际给出割,并通过运算验证它违反了 (1)。若允许无穷上界,就需要另外论证如何用有限数值替代,或者采用不同的存在性论证;本节的紧致性证明明确使用了界限有限这一假设。
小结
先从每条路线的流量中减去下界,再从所需节点平衡量中减去下界流量的净流出量。通过使辅助源点的所有出弧饱和,求解转化后的零下界问题。若无法全部饱和,就存在割证书 。对整数数据,整数增广法给出至少一个整数可行流。这些都是可行性结论;若问题还包含成本目标,就仍需另外证明最优性。
练习
快速检查
(有两条弧: 的界限为 , 的界限为 。所需平衡量为 。计算 ,用一个参数描述全部可行流,并在 处计算每条弧的正向和反向残量容量。)
解答 · 答案
下界流量的净流出量为 ,已经等于所需平衡量,所以 ,辅助问题不需要添加源点弧或汇点弧。令 ,由平衡等式得到 ;两条弧的界限合起来恰为 。在 处, 的正向、反向残量容量分别为 和 ; 的正向、反向残量容量分别为 和 。
快速检查
(对第一个例题的三节点网络,有人提出:减去下界后,仍保留平衡量 。解释为什么给这个错误剩余问题的一个可行解加回下界后,不能满足原平衡要求。写出正确的辅助弧,并给出一个使它们饱和的流。)
解答 · 答案
下界流量的净流出量为 。将它加到错误的剩余平衡量上,会得到 ,而不是 。正确的剩余平衡量为 。加入容量为一的 和 ,以及容量为二的 。沿 和 各发送一个单位,就能使这些辅助弧饱和,恢复出原有弧流量 。
快速检查
(一个零平衡网络仅有以下弧: 的界限为 , 为 , 为 。给出一个被违反的割不等式,计算辅助最大流值,并只修改 的上界,以尽可能小的改变量修复问题。)
解答 · 答案
对 ,(1) 右侧为 ,小于 。下界流量的净流出量为 ,所以 ,且 。辅助图中每条 – 路径都必须经过 ,而该弧的剩余容量为二。沿 发送两个单位可以达到此上界,所以最大流值为二。由这个被违反的割可知,必须将 的上界至少提高到三;这也已经足够,因为原网络中的循环流 此时满足全部界限。因此,最小改变量为一。
快速检查
(在运输成本例题中,仅将路线 的下界从一提高到二。求出所有可行方案及最小成本。解释为什么通过改变该路线的成本来施加配额,并不能得到等价的模型。)
解答 · 答案
每个满足平衡的方案仍为 。新配额要求 ,而原有上界要求 。因此,唯一可行方案是 ,成本为 。有限的优惠成本可以鼓励使用某条路线,却不会把 的可行方案从可行域中排除。改变目标函数与施加约束是两种不同的建模操作。
快速检查
(两条分别标记的平行弧都从 指向 ,各自界限均为 ,平衡量为 。给出一个整数可行流和一个分数可行流。定理确立的是哪一种整数性结论?如果第二条弧的下界变为 ,定理的整数数据结论是否适用?在这个具体例子中,是否仍存在整数可行流?)
解答 · 答案
弧流量向量 和 分别是整数与分数可行流。定理保证的是至少存在一个整数可行流,而不是每个可行点的坐标都必须为整数。第二条弧的下界改为 后,并非全部数据都是整数,所以不能使用这一充分假设。不过, 在这里仍是整数可行流。一个定理的充分假设不成立,并不能证明它的结论不成立。