假设团队要选择服务地点,令每个社区至少有一个所选地点提供服务。一个地点可能服务多个社区,若逐个社区选最便宜的地点,便可能把同一决策重复计算。建模的关键是:每个可选地点只设一个变量,然后为每个社区写一条要求。测试方案选择、设施覆盖及任务集合选择也有相同结构。
从覆盖要求到整数模型
定义 27.1.1
(加权集合覆盖)
设有限集合 包含所有要求,而 是选项 能覆盖的要求,。选项成本为 ;当 时令 ,否则为 0。二元变量 表示选用选项 。加权集合覆盖问题为
覆盖方案是可行的 ,即并集等于 的一组集合。
不等式要求的是至少一个,因此容许重叠。若某项要求不属于任何集合,其约束便是 ,问题不可行;反之,若每项要求都属于某个集合,选取全部集合便可行。成本非负时,不覆盖任何要求的集合可删去。若每行都改成等号,就禁止重叠,成为另一问题:集合分割。改成 则是意义不同的集合打包约束。
常见错误
(按要求逐项付费,而非按集合付费)
为每项要求选最便宜的集合再把成本相加,会把一个集合按它服务的要求数目重复计算。在下面第一个例题中,要求 的最便宜集合各需 ,合计 ;而作出同样选择的覆盖方案 只需 。模型通过单一变量 只付一次 ,不论它出现在多少行。
去掉整数限制得到线性规划 、。
命题 27.1.2
(上界对松弛最优值是多余的)
若 ,线性规划 与 有相同的最优值。
证明
(把大于一的分量截成一)
第二个规划的可行点较少,所以其值不低于第一个。反过来,对第一个规划的可行 ,把每个 换成 。含有该分量的覆盖行,单靠截后的分量仍至少得到 ,其他行不变,所以截后的向量对第二个规划可行。由于 ,截断不会增加成本。
这个截断论证不表示所有松弛可行向量都小于等于 1;若容许负成本,也不能照搬,正如第二个例题所示。
用价格证明下界
给每项要求分配非负价格 ,并要求
每个选项所覆盖要求的总价格,不得超过其成本。这些约束构成上述线性松弛的对偶;即使不求解对偶,任何满足条件的价格也能证明下界。
定理 27.1.3
(可行价格限制所有覆盖方案)
若 满足 ,而 满足价格约束,则 。特别地, 是每个覆盖方案成本的下界;成本等于 的覆盖方案是最优的。
证明
(以价格为行加权,以方案为列加权)
把每条覆盖不等式乘以 并相加,再利用 ,把每条价格约束乘以 相加,得到
每个二元覆盖方案也是松弛的可行解,所以下界同样适用于整数问题。若某个具体覆盖方案的成本恰等于 ,这两者便证明它最优,无须逐一枚举其他方案。
证明透视
可行价格为何限制所有覆盖方案
这条不等式链有两个不等号,各用一个不同的符号条件。第一个用 :它乘的是覆盖行 ,差额为 ,度量有价要求被过度覆盖的程度。第二个用 :它乘的是价格约束,差额为 ,度量所选集合的松弛量。
关键一步:中间的等式只是交换求和次序,把关于行的陈述变成关于列的陈述。
证明从未用到的:整数性。所以这个下界对松弛成立,却不能单靠它消除与整数最优值的差距。当线性规划可行且最优值有限时,强对偶保证最佳价格下界等于松弛最优值;但这个共同值未必等于整数最优值。下面的反例显示了差距。
例题 27.1.4
(配对的覆盖方案与价格证书)
取 ,选项与成本分别是 、2;、2;、2;、3。选 可覆盖全部要求,成本为 4。令各个 ,每个两元素集合的价格和都是 2,不超过其成本,所以价格可行,总和也为 4。上下界相等,故线性松弛及整数问题的最优值均为 4;这个证明不需要最优方案唯一。
例题 27.1.5
(负成本破坏截断论证)
在上述数据中加入成本为 的集合 ,例如一个可领取补贴的地点。没有上界时,松弛向量 对每个 都覆盖全部要求,成本为 ,趋向 :松弛向下无界。加上 后松弛有界, 的成本为 。两个规划的值此时不同,所以命题确实需要 。
对整数问题,补救很简单:负成本的集合总值得选,故固定 ,再以余下的非负成本为其余要求求解覆盖问题。
反例模式
线性松弛最优解未必是覆盖方案
对三项要求,选项为三个二元素集合 、、,每个成本都是 1。令所有 ,每行覆盖量均为 1,成本为 。价格 全部可行,总和也为 ,证明这是松弛最优值。然而任何一个集合都漏掉一项要求,所以整数方案至少选两个;任意两个已足够,整数最优值为 2。把各个 向下取整会完全失去覆盖,全部向上取整则成本为 3。两种取整都不会自动得到最优整数解。
如何阅读证书
证明透视中找出的两个差额,给出相等的精确检验。
推论 27.1.6
(目标值相等迫使取等号)
设 是覆盖方案, 是可行价格。则 当且仅当每个被选集合的价格约束取等号,而价格为正的每项要求恰好被覆盖一次。
证明
(两个非负差额都必须为零)
由定理的证明, 是两个差额 与 之和,每个都是非负项之和。差为零当且仅当每项为零: 迫使 , 迫使 。
反过来使用时,可行性和所需的等号条件都不可缺;单有一条约束取等号并不足以证明最优。若覆盖成本与价格总和仍有差距,前者是整数最优值的上界,后者是下界;单独任何一界都未必确定最优值。
例题 27.1.7
(取等号条件缩小搜索范围)
回到第一个例题,价格为 。各集合的价格和为 ,成本为 ,所以 取等号而 松弛。由推论,成本为 的覆盖方案只能用 ;又因每个价格都为正,它必须恰好覆盖每项要求一次。
在取等号的集合中,要求 只属于 ,要求 只属于 ,所以两者都必须选。它们已各覆盖 和 一次,再加 便会覆盖两次。因此 是这组价格唯一能证明的覆盖方案,而它的成本确实是 。
常见错误
(把“至少一个”换成“恰好一个”)
把覆盖行写成等式,覆盖问题便变成分割问题,而后者可能根本无解。对要求 及集合 、,覆盖问题以成本 可行;但等式迫使两个集合都要选,于是要求 被覆盖两次,不存在分割。只有在确实禁止重叠时才用等式。
练习
快速检查
(,选项 、、 的成本分别为 2、3、3。求一个最优覆盖方案并证明,再比较一个可行价格下界。)
解答 · 答案
选集合 1 和 2,成本为 5;集合 1 和 3 的成本同样是 5,集合 2 和 3 则是 6。任何方案至少选两个集合,最便宜的两个成本之和为 5,因此已最优。价格 的三组和为 2、3、3,故可行,总和为 4。各选一半集合得到成本为 4 的松弛解,因此松弛最优值为 4;不可能有总价为 5 的可行价格证书。
快速检查
(要求为 ,集合为 和 ,各成本 1。覆盖问题可行吗?若每项要求的覆盖不等式均改为等式,又会怎样?)
解答 · 答案
可行:选两个集合,成本为 2。若改成等式,覆盖要求 1 和 3 分别迫使两个变量都等于 1,但要求 2 的覆盖量便为 2,故分割模型不可行。
快速检查
(对三角形反例,直接证明整数最优值,并计算它与线性松弛最优值的差距。)
解答 · 答案
一个二元素集合只含两项要求;任选两个都覆盖全部三项,故整数最优值为 2。线性松弛最优值为 ,加法差距为 ,整数值与松弛值之比为 。
快速检查
(某项要求的价格 ,而所提议覆盖方案覆盖它两次。这两个可行对象的目标值能否相等?解释原因。)
解答 · 答案
不能。差额 中,该项严格为正;可行性及非负性使其他项不能抵消它,所以覆盖成本必然大于价格总和。