有用的界不一定是可行解
对最大化问题,一个可行选择提供最优值的下界;要证明其最优,还需要每个可行选择都不能超过的上界。放松一个困难约束可使余下优化更容易,但必须以正确符号为违反约束定价。
有限个物品的选择 ,重量 、价值 及容量 均为整数。原问题在 下最大化 。空集可行,以下使用精确运算。
为容量定价
定义 3.3.1
(Lagrange 函数与对偶函数)
对乘数 及二元向量 ,容量约束的 Lagrange 函数为
对偶函数是 ,即在所有二元向量(不论是否可行)上取最大值。只有 的乘数用于求界。
定理 3.3.2
(背包约束的 Lagrange 弱对偶)
对每个 ,
而每个可行 都满足 。特别地,原问题的最优值不超过 。
证明
(移除约束,保留其价格)
把 写成 。这样 的各分量可以独立选取:系数 为正时选第 件,为负时不选,为零时两种选择的值相同。由此得到所示的 公式。
对可行 ,因子 非负且 ,所以加入项非负,。由于 是 取最大值时所考虑的二元向量之一,。两个不等式合起来便证明了上界,而且对所有 同时成立。
证明透视
上界方向从何而来
证明中每个条件只用了一次。符号条件 只出现在第一个不等式,使未用容量的价格非负;二元限制在两边都保留;第二个不等式成立,只因移除容量约束扩大了取最大值的集合。负乘数会反转第一个不等式,未必给出上界。例如只有一件 、 且 时,放松最大值是 ;这个数碰巧仍是上界,但论证已失效。若同一物品改为 ,则得到 ,低于可行价值一。
证明中的独立选择可能超过容量。这不妨碍上界成立,因为我们用了更大的选择集合;但 的最大解不自动是原背包问题的可行解。只有当某个可行选择达到该界时,界才成为最优性的证明。
推论 3.3.3
(整数取整证书)
设每个 都是整数, 可行且价值为 ,并且存在 使 。则 是最优解。
证明
(低于下一个整数的整数目标值)
由于 和 都是整数,每个可行目标值都是整数;由弱对偶,它不超过 。小于 的整数至多为 ,而 取得 。
数值证书
例题 3.3.4
(为两件物品的最优解作证)
两件物品重量 、价值 、容量 。单选第二件可行,价值四。取 ,
因此每个可行价值不大于 。所有价值均为整数,故每个可行目标值都是整数,最多为 。单选第二件达到四,故最优;用推论的说法,就是 。
反例模式
放松问题的最大解未必可行
在 时,第一件调整后价值为正的 ,第二件为零。两件同选可使 最大,但总重量五超过容量三。上界仍然成立;此放松解本身不能作为可行下界的证据。
向下取整依赖目标值的整数性,不能仅凭决策变量是整数。
常见错误
(价值不是整数时仍把界取整)
把例子中第二件的价值改为 。单选第二件仍然可行,价值为 ;取 ,
若向下取整,就会声称每个可行价值不超过 ,与可行价值 矛盾。价值为实数时,只能照原样使用界 。
选择乘数
每个非负乘数都给出有效上界。较小上界较强,但找到一个好乘数不等于证明它使 最小。此式作为 的函数是分段线性的;在用目标值取整等额外论证前,其最小值仍可能与整数最优值有差距。此方法可用于证书或分支定界,但必须写清模型、乘数符号和保留的约束。
例题 3.3.5
(最佳乘数仍可能留下差距)
对两件物品的例子,,转折点在 与 。各段上
第一段递减,其余两段递增,所以在 上的最小值是 。即使是最佳的 Lagrange 界,也比最优值四多出 。上一例的证书需要取整一步;任何乘数都不能省去它。
例题 3.3.6
(能消除差距的乘数)
取两件 的物品及 ,最优值为一。此时 ,在 上等于 ,在 时等于 。最小值 等于最优值,所以单选一件可以不经取整便得到证明。在 时两件的调整后价值都是零,每个二元向量都使 最大;在这些最大解中,每个单件集合恰好可行。
练习
快速检查
(对两件物品例子计算 ,与可行价值四比较。)
解答 · 答案
,高于可行价值四。
快速检查
(当 ,计算 的 ,并解释为什么它不是原问题的可行选择。)
解答 · 答案
原价值七、重量五,故 ;重量五违反容量三。
快速检查
(若 ,只有一件重量一、价值二的物品,求 和 。)
解答 · 答案
、。唯一可行选择是价值零的空集,第二个界恰好等于最优值。
快速检查
(为什么例子可把 向下取整,而任意实数价值不能照做?)
解答 · 答案
所有 和 为整数时,每个原目标值均为整数;实数目标值则可以严格介于四和 ,向下取整可能排除有效值。