从供应和需求到方案
单独看最便宜的路线,未必能得到整体最便宜的运输方案:该路线会消耗可用于其他地方的供应与需求,我们必须一起决定所有运量。本节研究有限的平衡运输模型。
定义 2.3.1
(平衡运输问题)
设有 个供应点和 个目的地,供应量 、需求量 ,每一对供应点与目的地之间都有有限单位成本 。若 ,称模型为平衡的。方案是矩阵 ,满足 、行和 及列和 ;其总成本为 。
这些是等式要求,而非上界;剩余供应或未满足需求需要另行建模。供应或需求可以为零。成本可为负;固定的有限总运量使本模型不会因此向下无界。
命题 2.3.2
(平衡且路线完整的模型必可行)
若模型平衡,且每一对供应点与目的地均可运输,则存在方案。
证明
(反复运送较小剩余量直至全部用完)
记剩余供应 及剩余需求 ,初值为 和 。只要某个 ,剩余总量相等,便有某个 。由 向 运送 ,并从两个剩余量中减去;其中至少一个变为零。每一步都减少正剩余量的个数,所以最多 步便停止。此时每个 ,由平衡知每个 。运量非负,并具有所需的行和与列和。
证明无论选中哪一对 都用到该路线,完整性正是在这里起作用。
反例模式
仅靠平衡不能保证可行
有禁运路线时,平衡不保证存在方案。取供应 、需求 ,只允许路线 和 。模型平衡,但目的地 的列和是 ,因为两个变量都不存在。有禁运路线或容量限制时,必须另行检查可行性。
价格提供下界
对供应点和目的地分别指定实数 ,使每条路线满足 。这样的 称为可行价格。
定理 2.3.3
(价格下界与紧路线最优性)
设 是方案, 对所有 满足 。则
若还有 只出现在紧路线,即 的路线上,则等号成立,而 是最低成本方案。
证明
(以方案运量为权把价格不等式相加)
把每个不等式 乘以非负的 再求和,得 。行和把第一项化为 ,列和把第二项化为 。差额是
是一系列非负项之和。若所有已用路线都紧,每项均为零,所以 的成本等于下界。其他方案的成本都不低于同一下界,故 最优。
供需是等式约束,因此价格的正负不受限制。此证书是充分条件;论证不必假设有算法能为每个输入找到价格。
证明透视
把可行性和证书分开
假设在哪里用上: 非负,令每个价格不等式乘上去后方向不变;行和与列和的等式把加权价格和化为下界。方案只在这两处起作用,这也是价格可取任何符号的原因: 或 的不等式从未被乘以负数。
关键一步:差额是“运量乘以松弛量”之和。严格松弛的路线若有正运量,差额便为正;所有已用路线都紧,差额便为零。
缺了什么会出错:路线紧不能补救不正确的行和或列和。用下面例子的价格,只有 、 而其余为零的矩阵只用紧路线,成本 ,低于下界 ;它不满足第一行及第三列的和,所以证明中的等式一步不适用。
如何收尾:定理证明的是某一方案的最优性,并不声称每个最优方案都有紧价格。这个逆命题属于对偶定理,本节不予证明。
常见错误
(只检查已用的路线)
若所有已用路线都紧,证明中的恒等式会自动令成本等于下界,不论未用路线如何。所以在检查每条未用路线的不等式之前,这个等式什么也证明不了。在下面的例子中,、 在三条已用路线上都紧,数值也为 ,但 及 ,所以它们不是可行价格,不能作证书。
完整例子
例题 2.3.4
(同值的方案与价格)
供应为 ,需求为 ,成本矩阵和方案为
行和为 ,列和为 ,方案成本是 。取 、,则各 排成 ,逐项不大于 。价格下界为 ,等于方案成本,故方案最优。负的供应点价格是允许的,并不表示运量为负。
常见错误
(因价格为负而否定证书)
供需约束是等式,所以其价格可取任何符号。上面的 完全合法。要求 是 这类不等式约束的规则,属于另一个模型。
概念视角结构
价格并非唯一
对任意实数 ,把每个 加 、每个 减 ,路线上的和不变。由平衡条件,下界变化 等于零。因此同一证书有无数种表示;没有选定规范化时,单个价格没有独立意义。
第一个例子的价格是给定的。它们可以由方案算出,而退化方案需要多一步。
例题 2.3.5
(由退化方案计算价格)
沿用同一数据。每条紧路线给出一个方程 ;五个未知数除上文所说的平移外由这些方程确定,所以设 后需要 条紧路线。方案只用了三条:、、。它们给出 和 ,但 没有把第二行与其余部分连起来。
指定一条未用路线以零运量取紧,例如 :则 、,正是第一个例子的价格。其余两条路线的松弛量是 及 ,均非负,所以价格可行。
改选 ,则 、。此时 的松弛量是 , 的是 ,同样可行,下界为 。退化方案可以有真正不同的证书,而不只是平移;每个选择都要在全部六条路线上检查。
平衡且路线完整的模型之外
供应超过需求时,可以加入虚拟目的地,其需求为剩余量,成本表示所指定的剩余供应处理成本。这是建模选择,并非自动假设浪费免费。短缺也可在明确指定其含义与成本后,用虚拟供应点表示。若某些路线禁运,移去其变量及不等式,并另行检查可行性。路线容量会加入额外约束,对偶证书也要相应修改。
例题 2.3.6
(以虚拟目的地处理剩余供应)
把供应改为 ,需求仍是 ,并假设剩余供应可零成本弃置。加入需求为 的第四个目的地,成本 。把方案延伸为 ,即在 后加一列 ;行和为 ,成本仍是 。
已用路线的紧方程给出 、、、 及 。未用路线的不等式 和 要求 。取 ,则 。八条不等式全部成立:两行的和都是 ,对应成本分别为 和 。下界是 ,故方案最优。零成本弃置路线迫使 :供应点 多出的一单位既可免费弃置,其价值便不能为负。
练习
快速检查
(验证方案的行和、列和,并独立计算成本。)
解答 · 答案
行和为 ,列和为 ;成本为 。
快速检查
(检查六个价格不等式并计算下界。)
解答 · 答案
六个价格和为 ,分别不大于成本 ;下界为 。
快速检查
(只把 从 改为 ,原价格仍可行吗?仅凭这一点能否判断原方案是否最优?)
解答 · 答案
不可行:。此证书失效本身不能证明方案最优或不最优。事实上原方案仍最优:可行价格 、 证明其新成本 。
快速检查
(取 平移价格,计算新价格和下界,解释下界为何不变。)
解答 · 答案
新价格为 、,下界为 ;平衡使平移项相消。