当某些路线禁止使用时,总供应等于总需求并不保证运输计划存在。即使整体货物足够,一组工厂可以到达的客户也可能无法接收这组工厂的全部供应。在最小化运费或构造运输基之前,我们先要知道允许的路线能否实现供需平衡。
子集判据
定义 14.1.1
(允许路线计划与邻域)
设 分别为有限的出发地及目的地集合,供应量 、需求量 均为非负实数,允许路线集合为 。可行计划是在 上给出非负运量 ,并满足
对 , 的邻域是 ,即 可到达的目的地集合;空集没有邻点。
禁运路线根本没有变量。假设 。可行性的必要条件是
因为 的所有供应都必须送往 ,其目的地的总需求便限制了可接收量。这些不等式其实也足以保证可行。
定理 14.1.2
(允许路线的可行性判据)
对有限的 ,若供应和需求非负且总量同为 ,则存在只使用 的可行计划,当且仅当每个 均满足 。
证明
(流网络、割与残量割)
必要性可由 内的行平衡式求和得出:送入 的运量不超过该集合的列需求总和。证明充分性时,构造有向网络:源点 到出发地 的弧容量为 ;每条允许路线 的容量为 ;目的地 到汇点 的弧容量为 。值为 的流会饱和所有源点及汇点的弧,故其路线流量就是可行计划;反过来,可行计划亦给出值为 的流。路线容量取 已足够,因为任何路线都不需要运送超过总供应。
现在证明每个 – 割的容量至少为 ;割容量只计算从源点侧指向汇点侧的原弧。设割的源点侧包含出发地 及目的地 ,其容量为
若至少一条允许路线跨越割,最后一项已至少是 。否则 ,由假设得 ,故前两项之和已至少为 。
为什么割的下界保证存在值为 的流?最大流存在:有限维弧流向量处于闭且有界的集合,而流值连续。若最大流的残量网络有 – 路径,就可沿正向残量弧增加流量、沿反向残量弧减少流量,步长取路径上的最小残量容量,从而增大流值,矛盾。令 为残量网络中从 可到达的顶点,则 ;所有离开 的原弧均饱和,所有进入 的原弧均为零流量。在 上对流量守恒式求和,得到流值等于此割容量。由割下界知流值至少为 ,源点弧的容量又给出上界 ,所以流值等于 ,可行计划存在。
证明分两半:每个割的容量下界,以及一个容量等于流值的割。子集不等式在前一半使用。
证明透视
子集条件究竟控制什么?
关键一步是每条路线弧都取容量 。这个容量大到从不限制可行计划,但任何让允许路线由源点侧跨到汇点侧的割,容量已至少为 。这类割因此无害,需要检查的只有 的割。此时容量为 ,最小的选择是 ;这正是不等式要对一组出发地 连同其全部邻点一起检查、而非逐个出发地检查的原因。
各假设在不同位置使用。共同总量 使值为 的流同时饱和源点弧与汇点弧,于是行方程与列方程都成立。有限性使弧流向量组成闭且有界的集合,最大流因而存在。收尾一步用到反向残量弧:可到达集 之所以是容量等于流值的割,是因为每条进入 的弧都是零流量;若有正流量的弧进入 ,它会给出一条离开 的反向残量弧,其起点便也可到达。若总量为零,所有供应和需求均为零,即使没有允许路线,零计划也可行。
例题 14.1.3
(群组瓶颈与修补)
设供应为 、需求为 ;出发地 只能运往目的地 ,出发地 能运往 。总量都是 ,每个出发地和目的地都有路线,每个出发地单独的邻接需求也足够。然而 的供应为 ,而 的需求只有 。不等式不成立,故没有可行计划。在流网络中,源点侧取 ( 表示网络中目的地 的顶点),所得割容量为 :其中 来自 至出发地 ,另有 来自两个目的地至 。
若开放路线 ,以下计划满足所有平衡式:
其行和为 ,列和为 。新路线消除了上述特定障碍;真正证明可行的是列出的计划,而非单凭开放路线。
用残量路径修正早前选择
例题 14.1.4
(残量路径撤销贪心运量)
设供应与需求均为 ,路线为 。若先在 运送两单位,出发地 唯一的路线通往已满的目的地 ,因此不能只靠正向路线增广。残量路径 的瓶颈为 :中间的反向弧撤销 的早前运量。增广后得到 、、。行和为 、列和为 ,且只用允许路线,所以这是可行计划。
整数计划
增广路径论证也控制所得计划的算术性质。
推论 14.1.5
(整数数据给出整数计划)
若所有供应与需求都是整数,且子集判据成立,则存在只使用 、所有运量均为整数的可行计划。
证明
(以整数单位增广)
若供应与需求均为整数,所有容量都是整数。从零流开始,每次的残量容量和正瓶颈都是整数,因此增广保持整数性,并使流值至少增加一。流值不超过 ,所以至多 次增广后便再没有增广路径。当判据成立时,上述残量割论证给出流值 ,所得可行计划便是整数计划。
这是存在性陈述,并非说每个可行计划都是整数。成本与可行性判据无关;求得计划后,最小成本仍需另外的最优性论证。
例题 14.1.6
(检查每个子集,包括没有路线的出发地)
设供应为 、需求为 ,路线为 、,而出发地 完全没有允许路线。总量为 。各非空子集给出
七个不等式全部成立,所以计划存在;数据是整数,因此也存在整数计划。出发地 必须经 运出一单位;目的地 还欠一单位,只能来自出发地 ,出发地 余下的一单位则运往目的地 :
行和为 ,列和为 。边界情形是出发地 :没有路线的出发地恰在供应为零时无害,而单元素不等式 正记录了这一点。
常见错误
最诱人的捷径是每次只检查一个出发地。
反例模式
只检查单一出发地并不足够
声称:若总量平衡、每个顶点都有允许路线,而且每个单一出发地都满足 ,则可行计划存在。设供应 、需求 ,路线为 、、。每个出发地和目的地都有路线,单一出发地不等式为 、、。然而出发地 与 各只有一条路线,故 、 是被迫的,目的地 至少收到 单位,需求却只有 。没有可行计划。子集 检测到这一点:。修正后的陈述就是判据本身:检查出发地的每个子集。
常见错误
(以高成本代替禁运路线)
禁运路线没有变量。给它一个很高但有限的成本,仍容许货物经过,因此含这种路线的成本模型可能给出不被允许的计划。相对于 的可行性,应在任何成本进场之前判定。
常见错误
(把贪心死路当作不可行)
正向增广停顿时,目前的计划可能只是早前选择欠佳,正如残量路径例子所示。贪心法遇到死路不能证明不可行;只有容量小于 的有效割或违反的子集不等式才是证书。
练习
快速检查
(供应为 ,需求为 ,路线为 、、。找出违反的子集不等式或一个可行计划。)
解答 · 答案
的供应为 ,邻接需求为 ,故不可行。所有单一出发地的不等式都成立,因此群组测试很有用。
快速检查
(供应和需求均为 ,只允许对角线路线。 是否可行?给出允许的计划或不可行证书。)
解答 · 答案
不可行:这两个运量使用了禁运路线。对角计划 可行。
快速检查
(供应为 ,需求为 ,路线为 、。找出容量低于总供应的割,并指出目的地 至少需要增加多少需求,才能消除该特定不等式的违反。)
解答 · 答案
对 ,。将 、出发地 、目的地 放在源点侧,割容量为 。将该邻点的需求至少增加 ,可消除这个不等式的违反;但改变需求也会改变总平衡,必须适当调整模型后才能判断可行性。