有用的界不一定是可行解
對最大化問題,一個可行選擇提供最優值的下界;要證明其最優,還需要每個可行選擇都不能超過的上界。放鬆一個困難約束可令餘下優化更容易,但必須以正確符號為違反約束定價。
有限個物品的選擇 ,重量 、價值 及容量 均為整數。原問題在 下最大化 。空集可行,以下使用精確運算。
為容量定價
定義 3.3.1
(Lagrange 函數與對偶函數)
對乘數 及二元向量 ,容量約束的 Lagrange 函數為
對偶函數是 ,即在所有二元向量(不論是否可行)上取最大值。只有 的乘數用於求界。
定理 3.3.2
(背包約束的 Lagrange 弱對偶)
對每個 ,
而每個可行 都滿足 。特別地,原問題的最優值不超過 。
證明
(移除約束,保留其價格)
把 寫成 。這樣 的各分量可以獨立選取:係數 為正時選第 件,為負時不選,為零時兩種選擇的值相同。由此得到所示的 公式。
對可行 ,因子 非負且 ,所以加入項非負,。由於 是 取最大值時所考慮的二元向量之一,。兩個不等式合起來便證明了上界,而且對所有 同時成立。
證明透視
上界方向從何而來
證明中每個條件只用了一次。符號條件 只出現在第一個不等式,令未用容量的價格非負;二元限制在兩邊都保留;第二個不等式成立,只因移除容量約束擴大了取最大值的集合。負乘數會反轉第一個不等式,未必給出上界。例如只有一件 、 且 時,放鬆最大值是 ;這個數碰巧仍是上界,但論證已失效。若同一物品改為 ,則得到 ,低於可行價值一。
證明中的獨立選擇可能超過容量。這不妨礙上界成立,因為我們用了更大的選擇集合;但 的最大解不自動是原背包問題的可行解。只有當某個可行選擇達到該界時,界才成為最優性的證明。
推論 3.3.3
(整數取整證書)
設每個 都是整數, 可行且價值為 ,並且存在 使 。則 是最優解。
證明
(低於下一個整數的整數目標值)
由於 和 都是整數,每個可行目標值都是整數;由弱對偶,它不超過 。小於 的整數至多為 ,而 取得 。
數值證書
例題 3.3.4
(為兩件物品的最優解作證)
兩件物品重量 、價值 、容量 。單選第二件可行,價值四。取 ,
因此每個可行價值不大於 。所有價值均為整數,故每個可行目標值都是整數,最多為 。單選第二件達到四,故最優;用推論的說法,就是 。
反例模式
放鬆問題的最大解未必可行
在 時,第一件調整後價值為正的 ,第二件為零。兩件同選可使 最大,但總重量五超過容量三。上界仍然成立;此放鬆解本身不能作為可行下界的證據。
向下取整依賴目標值的整數性,不能只憑決策變量是整數。
常見錯誤
(價值不是整數時仍把界取整)
把例子中第二件的價值改為 。單選第二件仍然可行,價值為 ;取 ,
若向下取整,就會聲稱每個可行價值不超過 ,與可行價值 矛盾。價值為實數時,只能照原樣使用界 。
選擇乘數
每個非負乘數都給出有效上界。較小上界較強,但找到一個好乘數不等於證明它使 最小。此式作為 的函數是分段線性的;在用目標值取整等額外論證前,其最小值仍可能與整數最優值有差距。此方法可用於證書或分枝定界,但必須寫清模型、乘數符號和保留的約束。
例題 3.3.5
(最佳乘數仍可能留下差距)
對兩件物品的例子,,轉折點在 與 。各段上
第一段遞減,其餘兩段遞增,所以在 上的最小值是 。即使是最佳的 Lagrange 界,也比最優值四多出 。上一例的證書需要取整一步;任何乘數都不能省去它。
例題 3.3.6
(能消除差距的乘數)
取兩件 的物品及 ,最優值為一。此時 ,在 上等於 ,在 時等於 。最小值 等於最優值,所以單選一件可以不經取整便得到證明。在 時兩件的調整後價值都是零,每個二元向量都使 最大;在這些最大解中,每個單件集合剛好可行。
練習
快速檢查
(對兩件物品例子計算 ,與可行價值四比較。)
解答 · 答案
,高於可行價值四。
快速檢查
(當 ,計算 的 ,並解釋為何它不是原問題的可行選擇。)
解答 · 答案
原價值七、重量五,故 ;重量五違反容量三。
快速檢查
(若 ,只有一件重量一、價值二的物品,求 和 。)
解答 · 答案
、。唯一可行選擇是價值零的空集,第二個界恰好等於最優值。
快速檢查
(為何例子可把 向下取整,而任意實數價值不能照做?)
解答 · 答案
所有 和 為整數時,每個原目標值均為整數;實數目標值則可以嚴格介於四和 ,向下取整可能排除有效值。