为什么分散负荷可降低成本
假设固定工作量必须分配到若干站点。把所有工作集中一处可能造成高昂拥塞成本,因此分散负荷可能有利。作为易于处理的模型,设每个站点的成本随其自身工作量二次增长。
定义 8.6.1
(二次资源分配问题)
设 为固定工作量, 为站点数目, 为已知系数。分配是满足 及 的向量 。问题是
记 。 越大,第 站承受负荷的成本越低。
此模型允许分数工作量,不设站点容量、固定启用成本或不确定性;这些是模型假设,不是所有分配问题的性质。
由相等边际成本找候选解
在第 站工作量为正时,其成本导数是 。若两个正工作量站点的边际成本不同,从较高者移少量工作到较低者便能降低总成本。这启发我们令所有 。由总量等式得到 ,候选解为
时各分量均为正; 时候选解为零向量。
常见错误
(把交换论证当作证明)
交换论证只说明:若两个正工作量站点的边际成本不同,该分配可以改进。它预先假设最小解存在,而且没有直接处理含零分量的分配。它提出候选解;要证明没有其他可行分配更好,仍需要下面恒等式这类全局论证。
定理 8.6.2
(按比例分配是最优的)
在二次资源分配问题中, 给出的 是唯一的全局最小解,最小成本为 。更准确地说,每个满足 的实向量 都有
证明
(在候选解周围配方)
对任何满足 的 ,令 。两个向量之和均为 ,故 。由于每个 都有 ,展开 得
又 ,于是得到所示恒等式。所有 严格为正,所以恰在每个 时取等。候选解分量非负且和为 ,故可行,因而是唯一全局最小解。证明包括 ,无须猜测局部极小值或预先假设解存在。
证明透视
各个假设在哪里发挥作用
关键一步是展开点的选择。由于比值 在每个站点都等于同一个数 ,一次项化为 ,总量约束令它消失。若在比值不相等的分配周围展开,一次项对某些容许的 会是负数。每个 严格为正这一假设用了两次:它令每个平方项非负,也令取等时必须 ,这正是唯一性。约束 在恒等式中从未使用;它只在检查 本身可行时才需要,而因 这一点成立。证明不需要存在性定理,因为每个可行点都直接与 比较。
分配例子
例题 8.6.3
(两个站点与平均分配)
令 ,则 、。成本为 ,两站边际成本均为二。相比之下, 的成本是 ,高于六;差额恰是 ,符合恒等式。
反例模式
平均工作量未必成本最低
此例的平均分配 可行但不最优,因为两站的 不同。最优时相等的是边际成本,不一定是工作量;若所有 相等,公式就给出平均工作量。
只要明确搜索修改后的可行集,同一恒等式也可处理修改后的问题。
例题 8.6.4
(容量上界使边际成本不再相等)
保留 、,并加入容量 。比例候选解 此时不可行。每个分配都具有形式 ,故 ,恒等式给出
在 上,它随 增加而递减,所以最优解是 ,成本为 。直接计算也有 。两站边际成本是 和 :受容量限制的站点想承担更多却不能,所以受约束的最优解不满足边际成本相等。
例题 8.6.5
(三个站点与最优值公式)
令 、,则 、。成本为 ,等于 。把 由第 3 站移到第 1 站,得 ,成本改变
与 一致。一次项恰好抵消,因为两站边际成本 与 相等。在退化情形 中,唯一的分配是 ,而公式以 给出同一点。
限制与解读
最优值为 ,在本模型下随 二次改变。若加入个别容量上界 ,比例候选解可能违反上界,不能直接使用;例如 排除 。固定成本、整数工作量或不同目标也会改变问题。达到容量上界与未达上界的站点,其边际成本不一定相等。
练习
快速检查
(对 、,求最优分配及成本。)
解答 · 答案
,故 ,成本为 ,等于 。
快速检查
(对 、,用平方公式求 比最优值多多少。)
解答 · 答案
此时 ,差额为 。
快速检查
( 时唯一可行分配是什么?公式是否给出它?)
解答 · 答案
非负分量之和为零,故全为零;公式也给出零向量。
快速检查
(为什么加入 后, 不再是修改后例子的解?)
解答 · 答案
它违反 。原可行集上的证明不能让一个不可行点成为修改后问题的解。