假設團隊要選擇服務地點,令每個社區至少有一個所選地點提供服務。一個地點可能服務多個社區,若逐個社區選最便宜的地點,便可能把同一決策重複計算。建模的關鍵是:每個可選地點只設一個變量,然後為每個社區寫一條要求。測試方案選擇、設施覆蓋及任務集合選擇亦有相同結構。
從覆蓋要求到整數模型
定義 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。線性鬆弛最優值為 ,加法差距為 ,整數值與鬆弛值之比為 。
快速檢查
(某項要求的價格 ,而所提議覆蓋方案覆蓋它兩次。這兩個可行對象的目標值能否相等?解釋原因。)
解答 · 答案
不能。差額 中,該項嚴格為正;可行性及非負性使其他項不能抵銷它,所以覆蓋成本必然大於價格總和。