【正文】 M M MMMMMM M MM M MM M M???????????（累計減 26——新下界） （情況 2）不?。?14）（簡記為（ 14） 2022003040022?????????????????MMMMMMMMMMMMM（累計減 26—— 新下界） 情況 1中位于第四行第二列的元素改為 M是因為此時不能取 4→ 2,否則將含子圈（ 1， 4， 2）。 兩種情況又可分別變換為 （情況 1）取（ 14） ????????????????MMMMMMMMMMMMMMMMM00000000求得（ 1， 4， 5， 3， 2） （情況 2）（ 14） ????????????????MMMMMMMMMMMM2220003000000求得（ 1， 4， 5， 3， 2） 兩個旅行圈的費用均為 26（指在原問題中）。 （ 2）不取 2→ 1，將矩陣 A1改寫為 ????????????????????????????MMMMMMMMMMMM0242005004246404240202420053042786242403 累計減 25 求得（ 1， 2， 3， 5， 4） 比較各分枝，求得原問題的最優(yōu)解（ 1， 2， 3， 5， 4），最優(yōu)目標值為 25，如圖 。 需要指出的是，雖然在上面的實例中計算量并不是很大，但對于 n較大的實例，用以上介紹的分枝定界法求解旅行商問題效果并不理想，如何構造實用效果更好的分枝定界算法仍然是一個值得進一步研究的問題。 二、隱枚舉法 現考察 01規(guī)劃的一個實例： 例： 試求解 01規(guī)劃： 約束條件（ 1） 約束條件（ 2） 約束條件（ 3） 或 1 321 523max xxx ??22 321 ??? xxx44 321 ??? xxx321 ?? xx04 321 ?? x，x，x解： 本例中有三個變量，共有 8種可能取值。這里，我們將采用節(jié)省部分非必要運算的所謂隱枚舉法來求解它。在逐次選優(yōu)中，僅當發(fā)現目標值有所改進時才依次檢驗該取值是否滿足所有約束條件。求解的全過程見表 所示，例如，點（ 0， 0， 1）的目標為 5且滿足所有約束，故此后僅當目標值大于 5時才檢驗是否滿足各約束，此類條件在隱舉枚法中被稱為過濾條件。 表 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組不同取值，上述方法仍無法實際應用，因為根本無法檢驗全部 2n個點，甚至列出全部 2n個點也是不可能的。這時，可從目標值最大的點試起，只要發(fā)現使目標值最大的可行解，搜索立即停止。為此，首先需變換目標函數，使其各項系數均為非負。例如在本例中， x2的系數為 2，用（ ）代替 x2，將目標函數改寫 取 0當且僅當 x2取 1，而 取 1僅當 x2取 0。搜索從所有 xi和 取 1開始（ min問題從 xi均取 0開始）。約束條件中的 x2用 代替，搜索時先檢驗系數大找量取 1的點。在本例中，先檢查（ 1， 1， 1），即x1=1, =1, x3=1,由于此點為可行點，不再檢驗其他點，終止搜索，原問題最優(yōu)解為（ 1， 0， 1），最優(yōu)目標值為 8，如表 。 ??21 x?? ???232 ,2523 xxxx?2x?ix?2x?2x當然，由于 01規(guī)劃是 NP完全的，上述算法能否真正求得最優(yōu)解仍然是沒有保證的，全靠碰運氣。但在求解實例時如能獲得成功，至少對此實例我們求得了其最優(yōu)解，這也就是為什么人們對各類隱枚舉法依然存在著濃厚舉的原因。如果一個隱枚舉法能對絕大多數實例在較快時間內求出最優(yōu)解，它仍不失為一個好算法，至少從實用角度上講，它一定會被人們廣泛地接受。 在上一節(jié)中我們已經證明過，圖的頂點復蓋、圖的獨立集問題都是 NP完全的。下面將介紹求解復蓋問題的隱枚舉法。在此之前，我們先來推廣圖的復蓋問題，使之成為一個適用面更為廣泛的離散模型。 圖 G=（ V， E）的頂點與邊 ei稱為相關聯的，若 是邊 ei的兩個頂點之一。 與 ei相關連簡記為 。在引入關聯關系后，圖 G可以用一個被稱為關聯矩陣的 m n階矩陣代數地表示，其中 m=│ V│, n=│ E│ 。 i?i? ji Re?定義 圖 G的關聯矩陣是指如下的 m n陣矩 R=（ rij） ,其中 ?10?ijr 若 ji Re?否則 不難看出， V的一個子集構成圖 G的一個頂點復蓋，當且僅當頂點對應的關聯矩陣的行中每列至少存在著一個 1。 至此，關于復蓋的定義仍然是基于圖的概念給出的，事實上，我們還可以給出更一般的定義。 定義 給定兩個有限集合 和 ,稱 A中的元素為“格”，而稱 B中的元素為“點”。 A、 B中的元素之間可以存在某種關系（關系可根據需要自行規(guī)定），記為 R，并稱之為關聯關系。作矩陣 ,當 時，取 rij=1，否則取 rij=0，最后，對 A中的每一格 ai還以某種方式給出一個值 P（ ai），規(guī)定 A的一個子集 C對應的值 P（ C）為其包含的元素之值的總和。 ? ?maaA ,1 ?? ? ?nbbB ,1 ??? ?ijrR ? jia Re（ I）設 C= 為 A的一個子集，若對 B中的任一元素 bj，總有 ，使得 ，則稱子集 C復蓋 B，記為 CRB。 ? ?kii aa ,?? ?skCaki ??? 1 ji Rbak（ II）若 CRB且對 A任一復蓋 B的子集 C’有 P（ C） ≤P(C’)，則稱 C為最小復蓋。 例 假設我們正在餐廳點菜，希望所點的菜能包含我們所關心的某幾種營養(yǎng)成分，同時又價格最低，例如，餐廳共有六種菜，記為 A={a、 b、c、 d、 e、 f}，我們希望菜中包含的營養(yǎng)成分為 B=（蛋白質、淀粉、維生素、礦物質），引入關聯矩陣 R=（ rij）， rij=1當且僅當菜 i含營養(yǎng)成分 j。此外，每一種菜 i有一個菜價 P（ i） ,見表 。 不難看出，例 01規(guī)劃問題的實例。例如，對餐廳點菜問題，引入 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 表 菜單 單價 蛋白質 淀粉 維生素 礦物質 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ī)劃沒有求解的好算法。 現介紹根據關聯信息，利用代數方法在計算機上求解復蓋問題的直接解法。 定義 稱格 a在復蓋問題（ A， R， B）中對于點 b的復蓋是本質的，若 a是復蓋 b的唯一格。 定義 （控制關系）（ i）若對所有的 j，由 rkj=1且 P（ ai） ≤P（ ak）， 則稱格 ai控制格 ak簡記 aiak.。 (ii)若對所有 i，由 rik=1必可得出 rij=1,則稱 點 bj控制點 bk，簡記 bjbk。 易見，若存在兩個格 ai、 ak、 ai ak，則 ak在尋找最小復蓋時可以不必考慮，因為 ak必可用 ai代替，且 ai的價格不會高于 ak的價格。類似地，若存在兩點 bj、 bk，且 bjbk則 bj的復蓋可以不必考慮，因為只要復蓋住 bk必可復蓋住 bj。此外，若 A中存在著復蓋某點的本質格，則此格必出現在任一復蓋中，否則，該點將無法被復蓋。據此，求最小復蓋集可依次使用下列法則在關聯矩陣上實現。 法則一 刪去所有本質行（格）及一切在相應行中已有 1的列（這些點已被復蓋）。在解刪去后剩余的復蓋問題后，將這些本質格添入，即得到原問題的一個最小復蓋。 法則二 若只要求求出一個最小復蓋，則可刪去一切控制列（點），因為它們必會被復蓋。 法則三 刪去所有被控制行（格）。 例 求解復蓋問題，其關聯矩陣及價格表為 ? ?iaP ai b1 b2 b3 b4 b5 b6 ????????????????????000100100100000001010011101000111000231432654321aaaaaa解： 步 1 a3是復蓋 b2的本質格。刪去 a3行及已復蓋的列 b b b5，記錄下本質格 { 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均為本資格，從而得到最小復蓋集 { a a a6}。 上述方法有時也會失效（從而引出復蓋問題的 NP完全性），例如復蓋問題 1 2 3 4() iiP a a b b b b12341 1 0 0 11 0 0 1 11 0 1 1 01 1 1 0 0aaaa????????????其中既無控制列或控制行，又無本質行，這樣的關系矩陣常被稱為循環(huán)矩陣，此時要求解復蓋問題只好采用分枝辦法。 （分枝 1） 如選取 a1，則 b b4已被復蓋，問題化為 23iiP a a b b2341 0 11 1 11 1 0aaa??????????現在， a3 a2, a3 a4,求得復蓋 { a a3}。 （分枝 2） 如不取 a1，問題化為 1 2 3 4()iiP a a b b b b