运输表中第 行是产地 的供给,第 列是目的地 的需求。这里假设所有路线均可用,供给与需求非负且总量相等,单位费用为有限实数。树是记录基本变量的工具;树边上的运量可以为零,这正是处理退化所必需的。
平衡方程与树
令 为由产地 运往目的地 的运量,约束为
行方程总和等于列方程总和;因为总供给等于总需求,任意一条方程可由其余方程推出。把产地与目的地看作完全二部图的两类顶点,每个格 对应一条边。 个产地和 个目的地组成的生成树有 条边。
定义 23.1.1
(运输树及其基本解)
运输树是一组格,其边构成 个产地与 个目的地上完全二部图的生成树:连通、无环、到达每个产地与目的地,并有 个格。这些格称为基格。对应的基本解把所有非基格设为零,再在树格上解平衡方程。若所有运量非负,它就是基本可行解。
下述定理说明树格对应的列线性无关,因此平衡方程的秩恰为 。部分基本运量可以为零,所以单靠数正运量并不能辨认一个基。
定理 23.1.2
(树唯一决定基本运量)
供需平衡时,任意连接全部产地与目的地的生成树,都唯一决定一个仅在树边上可能非零、满足平衡方程的实数运量表。它可行当且仅当这些运量均非负。
证明
(逐一剥去叶顶点)
给每个顶点一个剩余余额,初始值为其供给或需求。多于一个顶点的有限树必有叶,叶的唯一邻边运量必须等于其当前剩余余额。删去叶及其边,并从相邻顶点的剩余余额减去这个运量。剩余供给与需求的总和仍相等。重复此步骤,所有边的数值被唯一决定,最后顶点的余额为零。每个删去的顶点按构造满足原方程,最后顶点也因余额为零而满足方程。因此实数解存在且唯一;它恰在所有运量非负时可行。
剥叶的每一步都是被迫的,这给出唯一性;存在性还需要对最后一个顶点多作一点观察。
证明透视
平衡条件与树形在哪里用到
剥叶一步只用到:叶的方程只含一个未知数,所以该未知数被迫决定。无环保证叶总是存在,删去后仍是一棵较小的树,程序可一直进行到只剩一个顶点。生成性不可少:不在树上的顶点没有任何边,除非其供给或需求为零,否则它的方程不能成立。
平衡假设只在最后用一次。不变量是:剩余供给总和等于剩余需求总和。删去剩余余额为 的叶,一边因叶消失而减少 ,另一边因其邻点被扣减而也减少 ,所以不变量保持。只剩一个顶点时,不变量的一边是空和,故该顶点剩余余额为零,其方程在没有边可调整的情况下仍然成立。若没有平衡条件,同样的剥叶仍迫定每条边的数值,但最后一条方程不成立,于是不存在解。
这个证明也显示,线性无关与树形是同一件事的两种描述。
概念视角组合
基恰好就是生成树
以 记 在平衡系统中的列:在行方程 与列方程 处各有一个一。一组格的列线性无关,当且仅当这组格不含环。若含环,沿环交替加减这些列得零,因为环上每行每列各以正负号出现一次。若不含环,这些格构成森林;对右端为零的系统作剥叶论证,迫使每个系数为零,所以各列无关。由于秩为 ,一个基有 个无关格,而 个顶点上 条边的无环图正是生成树。线性代数要求列无关,图论要求生成树,两者选出的是同一批格。
只有 这个数目并不足够,下面的检验说明这一点。
反例模式
格数正确不一定构成基
声称:任意 个格都唯一决定一个基本运量。取 、,供给 、需求 ,两者平衡。四个格 的数目正是 。对每个 ,
的行和为 、列和为 ,所以在这些格上平衡方程有无穷多个解。声称失败,是因为这些格含有环 ,又没有接触目的地 。若供给为 、需求为 ,同一组格根本无解,因为没有任何格能运到目的地 。正确的假设是这些格构成生成树,而不只是数目为 。
价格与换运
在每条树边上令 。先任选一个价格(例如 ),再沿树传播;树无环,价格不会矛盾,树连通,每个价格都被决定。
定义 23.1.3
(树价格与约化费用)
对一棵运输树,若价格 与 在每个树格上满足 ,则称为树价格。格的约化费用是 ,在树格上为零。
定理 23.1.4
(非负约化费用证明最优)
设运输树的基本解 可行, 为树价格,且每个非基格都有 。则任意可行表 满足
而 达到此下界,所以 最优。
证明
(代入约化费用)
把 代入 的费用,并使用平衡方程:
每个 均非负(树格上为零,其余按假设非负),而每个 ,所以最后一项非负。 只在树格上可能非零,那里 ,故取 时最后一项为零, 达到下界。价格本身可以为负,重要的只是约化费用的不等式。
若某非基格的约化费用为负,把它加进树会形成唯一的环。从该格开始交替加减 ;每个涉及的行与列各有一次加和一次减,所以余额不变。取减号格当前运量的最小值为 ,并删去一个变为零的减号边,便得到新树。费用变化为 ,因为树边上的价格沿环相消。若 ,换基不改变运量或费用,称为退化换基;此时单凭该基的负约化费用不能断言当前运量非最优。重复退化换基可能循环;保证终止需要适当的防循环规则。
例题详解
例题 23.1.5
(一次换基和最优性证书)
供给为 、需求为 ,费用与初始表为
初始费用为 。以四个正格为树,取 ,树方程给出 、、、。格 的约化费用为 。环上 依次取号 ,步长为 。新表为
两个减号格同时变零;保留 为零基格,移除 。新树价格为 、,非基格约化费用 、 均非负。下界为 ,等于实际费用,所以新表最优。保留零边是为了维持生成树,不代表该路线有正运量。
例题 23.1.6
(剥叶产生零值基格)
供给为 、需求为 ,树由格 组成。它有 个格且连通:产地 连到目的地 ,产地 连到目的地 。
目的地 是叶,所以 ,产地 剩余余额为 。目的地 是叶,所以 ,产地 剩余余额为 。此时产地 只剩格 ,成为叶,故 ,目的地 仍剩余 。最后一条边给出 ,产地 与目的地 的余额同时归零。
行和 、列和 均正确。这个解可行而且退化:基格 的运量为零。只有三个格为正,但基有四个格;若去掉 ,产地 便与树的其余部分断开,价格也无法传播。
例题 23.1.7
(基本解不可行的树)
供给为 、需求为 ,树由格 组成。产地 是叶,所以 ,目的地 剩余 。目的地 与 是叶,所以 、,产地 剩余 。最后一条边给出 ,两个剩余余额随即为零。
行和为 、列和为 ,平衡方程成立,正如定理所说。元素 使这个表不可行。任何树都给出基本解,但单纯形法只能使用基本解非负的树;在这里计算的树价格不能证明任何事。
常见错误
常见错误
(以正运量的数目找基)
退化可行解的正运量少于 个。只取正格作为基,得到的是森林而不是树,价格方程便有多于一个自由价格。应加入零值格把森林重新连接,而不形成环,就像第二个例题那样。
常见错误
(把负约化费用当作非最优的证明)
负的 只表示这个基未能证明最优,并不表示运量可以改善:若环上某个减号格的运量已是零,步长 ,费用不变。同一运量的另一棵树可能所有约化费用均非负。
练习
快速检查
(对第一个例题的最优表,用所列价格验证两个非基格的不等式,并直接计算费用。)
解答 · 答案
格 与 的价格和为 、。费用为 ,等于价格下界。
快速检查
(某入基格的约化费用为 ,但一个减号基格的运量为零。容许步长是多少?可以得出什么结论?)
解答 · 答案
瓶颈为零。让该格入基并移除一个运量为零的减号树格;运量表和目标值都不变。此步既不能证明严格改进,也不能证明最优,应继续计算约化费用。
快速检查
(两个产地、两个目的地,供给 、需求 ,费用矩阵为 。找两个不同的最优表,并解释其费用为何相同。)
解答 · 答案
对角表与反对角表的费用都是 。事实上 ,所以沿四格环的任何可行换运费用变化为零。每个可行表都形如 ,,其费用 与 无关,故每个可行表都最优。