【正文】 （分枝 1） 如選取 a1，則 b b4已被復(fù)蓋，問題化為 23iiP a a b b2341 0 11 1 11 1 0aaa??????????現(xiàn)在， a3 a2, a3 a4,求得復(fù)蓋 { a a3}。刪去 a3行及已復(fù)蓋的列 b b b5，記錄下本質(zhì)格 { a3}，得到新的矩陣 ? ? 3 4 6124560 1 120 1 130 0 0110131 0 02iib b bP a aaaaaa????????????????????步 2 b6 b4,刪去 b6及被控制格 a4，得 ? ? 341256012013103102iibbP a aaaaa????????????????步 3 a1 a2, a6 a5刪去 a a5，得到 ? ? 34iiP a a b b162 012 10aa??????步 4 a a6均為本資格，從而得到最小復(fù)蓋集 { a a a6}。 法則三 刪去所有被控制行（格）。在解刪去后剩余的復(fù)蓋問題后，將這些本質(zhì)格添入，即得到原問題的一個最小復(fù)蓋。據(jù)此，求最小復(fù)蓋集可依次使用下列法則在關(guān)聯(lián)矩陣上實現(xiàn)。類似地，若存在兩點 bj、 bk，且 bjbk則 bj的復(fù)蓋可以不必考慮，因為只要復(fù)蓋住 bk必可復(fù)蓋住 bj。 (ii)若對所有 i，由 rik=1必可得出 rij=1,則稱 點 bj控制點 bk，簡記 bjbk。 定義 稱格 a在復(fù)蓋問題（ A， R， B）中對于點 b的復(fù)蓋是本質(zhì)的，若 a是復(fù)蓋 b的唯一格。例如，對餐廳點菜問題，引入 01變量 x1， … ， x6，作 01規(guī)劃如下： min + x2+ x3+ x4+ x5+5x6 x1+ x4+ x6≥1 x2+ x5 ≥1 x1+ x3 ≥1 x1+ x2+ x6 ≥1 x1， … ， x6=0或 1 表 菜單 單價 蛋白質(zhì) 淀粉 維生素 礦物質(zhì) a 1 0 1 1 b 0 1 0 1 c 0 0 1 0 d 1 0 0 0 e 0 1 0 0 f 1 0 0 1 若可惜的是 01規(guī)劃沒有求解的好算法。此外，每一種菜 i有一個菜價 P（ i） ,見表 。 ? ?kii aa ,?? ?skCaki ??? 1 ji Rbak（ II）若 CRB且對 A任一復(fù)蓋 B的子集 C’有 P（ C） ≤P(C’)，則稱 C為最小復(fù)蓋。作矩陣 ,當(dāng) 時，取 rij=1，否則取 rij=0，最后，對 A中的每一格 ai還以某種方式給出一個值 P（ ai），規(guī)定 A的一個子集 C對應(yīng)的值 P（ C）為其包含的元素之值的總和。 定義 給定兩個有限集合 和 ,稱 A中的元素為“格”，而稱 B中的元素為“點”。 i?i? ji Re?定義 圖 G的關(guān)聯(lián)矩陣是指如下的 m n陣矩 R=（ rij） ,其中 ?10?ijr 若 ji Re?否則 不難看出， V的一個子集構(gòu)成圖 G的一個頂點復(fù)蓋，當(dāng)且僅當(dāng)頂點對應(yīng)的關(guān)聯(lián)矩陣的行中每列至少存在著一個 1。 與 ei相關(guān)連簡記為 。在此之前，我們先來推廣圖的復(fù)蓋問題，使之成為一個適用面更為廣泛的離散模型。 在上一節(jié)中我們已經(jīng)證明過，圖的頂點復(fù)蓋、圖的獨立集問題都是 NP完全的。但在求解實例時如能獲得成功，至少對此實例我們求得了其最優(yōu)解，這也就是為什么人們對各類隱枚舉法依然存在著濃厚舉的原因。在本例中，先檢查（ 1， 1， 1），即x1=1, =1, x3=1,由于此點為可行點，不再檢驗其他點，終止搜索，原問題最優(yōu)解為（ 1， 0， 1），最優(yōu)目標(biāo)值為 8，如表 。搜索從所有 xi和 取 1開始（ min問題從 xi均取 0開始）。為此，首先需變換目標(biāo)函數(shù)，使其各項系數(shù)均為非負(fù)。 表 0 5 8 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 5 2 3 3 8 1 6 (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) Z值 是否可行 ⑷ ⑶ ⑵ ⑴ (Z) 條件 取值 表 ? ? ? ? ? ? 0 (0,0,0) Z值 是否可行 ⑷ ⑶ ⑵ ⑴ (Z) 條件 取值 對于有 n個變量的一般問題，變量可有 2n組不同取值，上述方法仍無法實際應(yīng)用，因為根本無法檢驗全部 2n個點，甚至列出全部 2n個點也是不可能的。在逐次選優(yōu)中，僅當(dāng)發(fā)現(xiàn)目標(biāo)值有所改進時才依次檢驗該取值是否滿足所有約束條件。 二、隱枚舉法 現(xiàn)考察 01規(guī)劃的一個實例： 例： 試求解 01規(guī)劃： 約束條件（ 1） 約束條件（ 2） 約束條件（ 3） 或 1 321 523max xxx ??22 321 ??? xxx44 321 ??? xxx321 ?? xx04 321 ?? x，x，x解： 本例中有三個變量，共有 8種可能取值。 （ 2）不取 2→ 1，將矩陣 A1改寫為 ????????????????????????????MMMMMMMMMMMM0242005004246404240202420053042786242403 累計減 25 求得（ 1， 2， 3， 5， 4） 比較各分枝，求得原問題的最優(yōu)解（ 1， 2， 3， 5， 4），最優(yōu)目標(biāo)值為 25，如圖 。現(xiàn)作如下兩個分枝：（ 1）取 2→1 ，即 2指派給 1（簡記成（ 21）），則不能再有 1→2 ，將矩陣 A1中位于第一行及第二列的元素 0改寫成M，在不允許（ 12）的限止下兩問題的最優(yōu)指派相同，作變換： 1 2 3 4 5 1 4 2 4 2 2 0 22 0 03 2 4 0 0 4 04 5 0 0 3 0 05 4 2 0 2 2 0M M M MM M M M M M M MM M M MM M M MM M M M?? ? ? ?? ? ? ?? ? ? ?? ? ? ??? ? ? ?? ? ? ?? ? ? ?? ? ? ?－ 2 （累計減 24——新下界） 此時又可作如下分枝： （情況 1）取（ 14） 0000002 2 2M M M MMMMMM M MM M MM M M???????????（累計減 26——新下界） （情況 2）不?。?14）（簡記為（ 14） 2022003040022?????????????????MMMMMMMMMMMMM（累計減 26—— 新下界） 情況 1中位于第四行第二列的元素改為 M是因為此時不能取 4→ 2,否則將含子圈（ 1， 4， 2）。 一般地，調(diào)色問題（即 TSP的實例）可試用分枝定界法求解。 TSP是 NP完全的，而求解指派問題的匈牙利算法是多項式時間算法，不可能用來求解 TSP的每一實例。 讀者不難發(fā)現(xiàn)，利用指派問題的算法求得調(diào)色問題例 2的解純系巧合。 利用求解指派問題的匈牙利算法，對矩陣逐次變換如下： 6 18 4 87 17 3 74 5 4 520 19 24 228 8 16 6MMMMM??????????4 2 14 0 43 4 14 0 44 0 1 0 119 1 0 5 36 2 2 10 0 5 1MMMMM? ?????????? ??? ????2 9 0 34 9 0 320 1 0 021 0 0 22 2 5 0MMMMM????????????0 7 0 12 7 0 10 1 2 01 0 0 20 0 3 0MMMMM???????????在變換過程中， M的值可能改變，它們均表示充分大的正整數(shù)，為簡便起見，不妨仍用 M表示。 表 現(xiàn)調(diào) 原調(diào) 紅 藍(lán) 白 黑 黃 紅 藍(lán) 白 黑 黃 / 7 4 20 8 6 / 5 19 8 18 17 / 24 16 4 3 4 / 6 8 7 5 22 / 考察五種顏色間的指派問題，將甲色指派給乙色理解為“用完甲色清洗工具，其后使用乙色”。 對例 ，一個油漆工每天都要使用上述五種顏料，從而他應(yīng)當(dāng)在完成工作后清洗好工具，以便第二天開始同樣順序的調(diào)色。清洗調(diào)配工具所需花費的時間既和原來調(diào)配什么顏色有關(guān)又和擬調(diào)配什么顏色有關(guān)，各種情況下所需的時間見表 。讀者不難看出算法的實質(zhì)，并由此總結(jié)出算法。于是，對 x1≥3的分枝（ LP2），我們已求得最優(yōu)解（注（ LP1）已不必再求解）目標(biāo)值的一個上界（ UB） Z=。 由于（ LP1）與（ LP2）的最優(yōu)解均非整數(shù)解，還需繼續(xù)搜索，現(xiàn)選取最優(yōu)目標(biāo)值最大的（ LP2）進行分枝，即增加約束 x2≤2作子問題（ LP3），增加約束 x2≥3作子問題（ LP4）。 （ LP1） max x1 + 13x1 + ≤91 4 x1 + 40x2≤140 x1≤2 x x2≥0且為整數(shù) （ LP2） max x1 + 13x1 + ≤91 4 x1 + 40x2≤140 x1≥3 x1≤4 x x2≥0且為整數(shù) 可以看出，（ ILP）的最優(yōu)解必在（ LP1）與（ LP2）的可行域之一中，但（ LP0）的最優(yōu)解 （ ,）已不在（ LP1）與（ LP2）的可行域中（這正是分枝的目的）。在本實例中，由于問題是求目標(biāo)值最大的，我們可以看出，既然不考慮整約束時的最優(yōu)目標(biāo)值為 萬，則（ ILP）的最優(yōu)目標(biāo)值不可能超過 ，從而我們知道了最優(yōu)目標(biāo)值的一個上界。不難看出，對只有兩個變量的問題都不能通過化整的辦法來求得最優(yōu)解，對變量數(shù)較多的實例，情況將更為復(fù)雜。有人曾構(gòu)造出一個實例，其最優(yōu)解有一百多萬種四舍五入的可能情況，但得到的均非可行解。問此單位應(yīng)購兩種房各多少套才能使總收入最大 建模 設(shè) x x2分別為購買兩種房的套數(shù)，顯然 x x2必須為整數(shù)，故要求求解整數(shù)規(guī)劃（ ILP） max x1 + 13x1 + ≤91 4 x1 + 40x2≤140 x1≤4 x x2≥0且為整數(shù) 解 ： 先不考慮整數(shù)要求，求解與上述整數(shù)規(guī)劃（ ILP）相應(yīng)的線性規(guī)劃LP0（稱之為與（ ILP）相應(yīng)的松馳線性規(guī)劃），解得 x1=， x2=，maxZ=。該單位每月可用于照料租房的工時總計為 140 小時，第一種房每套每月需照料 4小時，第二種房每套每月需照料 40小時。我們將在本節(jié)舉幾個實例來介紹這類算法。雖然迄今為止還沒有一個 NP完全問題被發(fā)現(xiàn)具有類似單純形法那樣漂亮的指數(shù)算法，這也許是由問題的 NP完全性本身決定的（注意：線性規(guī)劃問題是