【正文】 ? ? ?39。 從圖 （ b）中可以找出一個(gè)負(fù)費(fèi)用循環(huán)流 s→υ 2→υ 1→ s（其余邊流量為 0），每單位流量的總費(fèi)用為－ 5。此問(wèn)題在使用三次增廣路后可求得最佳結(jié)果。在標(biāo)每一頂點(diǎn)時(shí)，最多作了 | V |次運(yùn)算。 表 表 第 i年 1 2 3 4 5 價(jià)格（萬(wàn)年） 10 10 11 12 13 已使用年數(shù) 0 1 2 3 4 （萬(wàn)年） 4 8 11 15 20 五、歐拉圈與最短郵路問(wèn)題 歐拉圈問(wèn)題起源于著名的七橋問(wèn)題。 無(wú)向圖上的中國(guó)郵路問(wèn)題也不難解決。這里只增加了每個(gè)頂點(diǎn)都要去一次的要求，但問(wèn)題發(fā)生了質(zhì)的變化，由 P問(wèn)題變成了NP完全問(wèn)題。 總之，在研究離散模型時(shí)應(yīng)當(dāng)極其小心。盡管如此，別人的經(jīng)驗(yàn)對(duì)我們?nèi)匀皇呛苡杏玫摹，F(xiàn)有一批容量為 C的箱子（足夠數(shù)量），要求找到一種裝箱方法，使得所用的箱子數(shù)最少。按目前流行的做法，人們常用三個(gè)參數(shù) α， β， υ來(lái)描述一個(gè)特定的排序問(wèn)題，并記為 α/β/υ排序問(wèn)題，其中 α描述機(jī)器情況， β描述加工零件時(shí)的附加要求或附加條件， υ表示衡量排序好壞的標(biāo)準(zhǔn)。但一般地講，事情決非如此簡(jiǎn)單，要將某一 NP完全問(wèn)題多項(xiàng)式時(shí)間轉(zhuǎn)化為我們要研究的問(wèn)題，常常需要用到一些巧妙而又精細(xì)的技巧。 分枝定界法與隱枚舉法（精確算法） 在上一章中我們已經(jīng)看到，整數(shù)規(guī)劃、 0—1規(guī)劃都是 NP完全的。對(duì)本例，因只有兩個(gè)變量，共有四種可能，即化整為（ 2,3），（ 2,4），（ 3,3），（ 3,4），其中只有 x1=2，x2=3是可行的，目標(biāo)值為 Z=，并非最優(yōu)解（最優(yōu)解為 x1=4， x2=2，Z*=）。如果該工人只需調(diào)配一次而不必考慮以后的工作，問(wèn)題可以作類(lèi)似的討論，（注：此工人只有一塊調(diào)色板）。這里，我們將采用節(jié)省部分非必要運(yùn)算的所謂隱枚舉法來(lái)求解它。 圖 G=（ V， E）的頂點(diǎn)與邊 ei稱(chēng)為相關(guān)聯(lián)的，若 是邊 ei的兩個(gè)頂點(diǎn)之一。 定義 （控制關(guān)系）（ i）若對(duì)所有的 j，由 rkj=1且 P（ ai） ≤P（ ak）， 則稱(chēng)格 ai控制格 ak簡(jiǎn)記 aiak.。 上述方法有時(shí)也會(huì)失效（從而引出復(fù)蓋問(wèn)題的 NP完全性），例如復(fù)蓋問(wèn)題 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????????????其中既無(wú)控制列或控制行，又無(wú)本質(zhì)行，這樣的關(guān)系矩陣常被稱(chēng)為循環(huán)矩陣，此時(shí)要求解復(fù)蓋問(wèn)題只好采用分枝辦法。 不難看出，例 01規(guī)劃問(wèn)題的實(shí)例。如果一個(gè)隱枚舉法能對(duì)絕大多數(shù)實(shí)例在較快時(shí)間內(nèi)求出最優(yōu)解，它仍不失為一個(gè)好算法，至少?gòu)膶?shí)用角度上講，它一定會(huì)被人們廣泛地接受。 兩種情況又可分別變換為 （情況 1）?。?14） ????????????????MMMMMMMMMMMMMMMMM00000000求得（ 1， 4， 5， 3， 2） （情況 2）（ 14） ????????????????MMMMMMMMMMMM2220003000000求得（ 1， 4， 5， 3， 2） 兩個(gè)旅行圈的費(fèi)用均為 26（指在原問(wèn)題中）。 為了讓讀者看清在各種不同類(lèi)型的問(wèn)題中是如何使用分枝定界法的，下面 我們?cè)倥e一例： 例 要調(diào)配紅、藍(lán)、白、黑、黃五種顏色的油漆。第一種房月租金收入為 2022元，第二種房月租金收入為 3000元。這樣，這 t－ 1項(xiàng)工件應(yīng)分別在 [ b, b + 1], [2b + 1, 2b + 2],… [ ( t－ 1) b +1－ 2, (t－ 1)b + t－ 1]時(shí)段內(nèi)加工。β=Φ，表示工件加工沒(méi)有附加要求或條件。讀者不難發(fā)現(xiàn)， Bin—packing問(wèn)題至少不會(huì)比 3—?jiǎng)澐謫?wèn)題容易。 G G GG GGGG前面已經(jīng)講過(guò)，哈密頓圈問(wèn)題已被證明是 NP完全的，從而可得出 TSP是 NP完全的，哈密頓問(wèn)題是 NP完全的，進(jìn)而又可得出有向圖上的哈密頓圈、哈密頓路和 TSP也是 NP完全的，因?yàn)橛脙蓷l具有相反方向的弧來(lái)代替每一條邊，就可將一個(gè)無(wú)向圖上的問(wèn)題轉(zhuǎn)化為一個(gè)有向圖上的問(wèn)題，從而任一有向圖問(wèn)題的有效算法必能用來(lái)求解無(wú)向圖問(wèn)題。例如可查閱 “計(jì)算機(jī)和難解性”，其中例舉了大量 NP完全問(wèn)題。所以，如果你想設(shè)計(jì)一個(gè)求圖上兩點(diǎn)間的最長(zhǎng)簡(jiǎn)單路徑的有效算法，不管你是多么努力，最終必將以失敗告終。但即使是線(xiàn)性規(guī)劃問(wèn)題，也已經(jīng)找到了具有這種特性的算法，如橢球算法、卡馬卡算法，雖然其結(jié)構(gòu)是相當(dāng)復(fù)雜的，但計(jì)算量卻是多項(xiàng)式時(shí)間的。給定一個(gè)無(wú)向圖，它的每一條邊上都賦有一個(gè)表示該邊長(zhǎng)度（或費(fèi)用）的權(quán)。 解： 作有向圖圖 ，圖中點(diǎn) i表示第 i年初（或第 i－ 1）年末），?。?i, j）上的數(shù)字表示第 i年初購(gòu)買(mǎi)設(shè)備到第 j年初更換，在該段時(shí)間內(nèi)的總費(fèi)用。比較各已標(biāo)號(hào)頂點(diǎn)（與擬標(biāo)號(hào)頂點(diǎn)有邊相連）的標(biāo)號(hào)與它到擬標(biāo)號(hào)頂點(diǎn)距離之和，找出各種中最小者作為新頂點(diǎn)的標(biāo)號(hào)，并記錄下其前的已標(biāo)號(hào)頂點(diǎn)。 網(wǎng)絡(luò)流問(wèn)題的算法在解決實(shí)際問(wèn)題時(shí)常常被用到。 最小費(fèi)用最大流問(wèn)題可以變換成為一個(gè)線(xiàn)性規(guī)劃問(wèn)題，根據(jù)線(xiàn)性規(guī)劃理論可以證明下面的定理： 定理 網(wǎng)絡(luò)中的流 是最小費(fèi)用的，當(dāng)且僅當(dāng)其增廣網(wǎng)絡(luò) G’中不存在負(fù)費(fèi)用的循環(huán)流（證明略）。 Ｇ ‘ 包含兩類(lèi)邊，對(duì)Ｇ中每一條邊（ i， j） ： ?A?（ 1）若 ，作正向邊（ i， j） , 規(guī)定容量 ，即剩余容量。例如：當(dāng)網(wǎng)絡(luò)是通訊網(wǎng)時(shí)，我們可能會(huì)去求出網(wǎng)絡(luò)中兩個(gè)指定點(diǎn)間的最大通話(huà)量；當(dāng)網(wǎng)絡(luò)是城市的街道時(shí)，我們又可能會(huì)去求兩地間的最大交通流，即單位時(shí)間內(nèi)允許通過(guò)的車(chē)輛數(shù)等等。 例 在圖 （ a）中，用雙線(xiàn)劃出的邊組成該圖的一個(gè)極大匹配。 定義 (匹配 ) 圖 G的一個(gè)匹配是指邊集 E的一個(gè)子集 M， M中的任意兩條邊 均不具有公共的頂點(diǎn)。 我們不加證明地引入下面的定理，雖然其證明并不十分困難。 ? ? ? ?1 , ,i in?例 求矩陣 A的列向量具有最大權(quán)和的獨(dú)立子集 7*45762101543100012731214531011?????????????AC(ei)＝ 8 4 7 5 2 6 4 解： 采用貪婪法，先取權(quán)最大的列 e1，同時(shí)對(duì) A作高斯消去，逐次加入 線(xiàn)性無(wú)關(guān)的向量： A的列向量中具有最大權(quán)的獨(dú)立子集為 。 解 ： 不妨從頂點(diǎn)開(kāi)始尋找。 … k,若僅有一個(gè)頂點(diǎn)在 Vi中的具有最小權(quán)的邊為（ ,u），則必有一棵 G的最小生成樹(shù)包含邊（ ,u）。從這一點(diǎn)上講， P問(wèn)題可以看成是一類(lèi)具有良好性質(zhì)而又較容易求解的問(wèn)題，而 NP完全問(wèn)題則是固有地難解的。 ???e此問(wèn)題的標(biāo)準(zhǔn)形式為給定一完全圖 G，其每邊賦有一權(quán)數(shù)，求此完全圖的最小生成樹(shù)。 39。 解：由于入樹(shù)不能包含具有公共終點(diǎn)的孤，故對(duì)每一頂點(diǎn) 只能選取一條入孤。又由于這一離散優(yōu)化問(wèn)題的任一實(shí)例都可用貪婪法求解，故構(gòu)成一擬陣，被稱(chēng)為矩陣擬陣。假定三個(gè)女兒為 A、 B、 C，三位求婚者為 X、 Y、 Z。 如果所有邊的權(quán)均為 1，則最大權(quán)匹配化成最大匹配問(wèn)題（即求邊數(shù)最多 的匹配）。 現(xiàn)在可以看出，找最大匹配的關(guān)鍵在于找增廣路。若 Ｐ 、 滿(mǎn)足 且 則稱(chēng) Ｐ 和 為Ｖ的一個(gè)切割。如圖 ，圖中的（ a）、（ b）、（ c）均是流量為 7的最大流，邊上的兩個(gè)數(shù)字依次為容量和邊上的實(shí)際流量。 證明： 設(shè) 1+2不是流量為 υ+1的最小費(fèi)用流，由定理 6，在 1+ 2的增廣網(wǎng)絡(luò)中必存在一負(fù)圈 C。若點(diǎn)P在 A到 E的最短路上，則 P到 E的最短路徑必整個(gè)地包含在 A到 E的最短路徑上。 從圖 A到各點(diǎn)的距離及最短路徑，而從圖 各點(diǎn)到 E點(diǎn)的距離及最短路徑，這是兩者的區(qū)別。 把關(guān)聯(lián)偶數(shù)條邊的頂點(diǎn)稱(chēng)為偶頂點(diǎn)，把關(guān)聯(lián)奇數(shù)條邊的頂點(diǎn)稱(chēng)為奇頂點(diǎn)，則容易看出奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)（因?yàn)槊恳还P畫(huà)都產(chǎn)生一個(gè)起點(diǎn)與一個(gè)終點(diǎn)），又易得出 定理 G為歐拉路的充要條件為： G是連通的且奇頂點(diǎn)的個(gè)數(shù)為 2。 。 （ 4）線(xiàn)性規(guī)劃問(wèn)題、運(yùn)輸問(wèn)題及指派問(wèn)題均為 P問(wèn)題，但相應(yīng)的整數(shù)線(xiàn)性規(guī)劃及 0—1規(guī)劃均為 NP完全的。從某種意義上說(shuō)，可以認(rèn)為這些問(wèn)題已被較好地解決了。 ( , )uE???對(duì)于例 ，我們?yōu)閿⑹龇奖?，采用了圖的語(yǔ)言，其實(shí)也完全可以將它們表達(dá)成其他方式。而當(dāng)我們真正想把一批已知長(zhǎng)、寬、高的物體裝入具有相同尺寸的箱子時(shí)，又遇到了三維的。 Job shop意指每一工件要在 m臺(tái)機(jī)器的每一臺(tái)上加工（當(dāng)不需某臺(tái)加工時(shí)可令加工時(shí)間為零），且各工件使用機(jī)器的順序可以不同。評(píng)判排序優(yōu)劣的標(biāo)準(zhǔn)為各工件完工時(shí)間 Cj的加權(quán)和 越小越好。例如，求解線(xiàn)性規(guī)劃的單純形法從理論上講是指數(shù)算法，但在實(shí)際應(yīng)用時(shí)它又一般表現(xiàn)得出奇地好（已經(jīng)證明，其平均計(jì)算量?jī)H為 O(nlog2n)）。 （ 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）的可行域中（這正是分枝的目的）。 讀者不難發(fā)現(xiàn)，利用指派問(wèn)題的算法求得調(diào)色問(wèn)題例 2的解純系巧合。為此，首先需變換目標(biāo)函數(shù)，使其各項(xiàng)系數(shù)均為非負(fù)。 定義 給定兩個(gè)有限集合 和 ,稱(chēng) A中的元素為“格”，而稱(chēng) B中的元素為“點(diǎn)”。據(jù)此，求最小復(fù)蓋集可依次使用下列法則在關(guān)聯(lián)矩陣上實(shí)現(xiàn)。在解刪去后剩余的復(fù)蓋問(wèn)題后，將這些本質(zhì)格添入，即得到原問(wèn)題的一個(gè)最小復(fù)蓋。作矩陣 ,當(dāng) 時(shí)，取 rij=1，否則取 rij=0，最后，對(duì) A中的每一格 ai還以某種方式給出一個(gè)值 P（ ai），規(guī)定 A的一個(gè)子集 C對(duì)應(yīng)的值 P（ C）為其包含的元素之值的總和。搜索從所有 xi和 取 1開(kāi)始（ min問(wèn)題從 xi均取 0開(kāi)始）。 TSP是 NP完全的，而求解指派問(wèn)題的匈牙利算法是多項(xiàng)式時(shí)間算法，不可能用來(lái)求解 TSP的每一實(shí)例。 由于（ LP1）與（ LP2）的最優(yōu)解均非整數(shù)解，還需繼續(xù)搜索，現(xiàn)選取最優(yōu)目標(biāo)值最大的（ LP2）進(jìn)行分枝，即增加約束 x2≤2作子問(wèn)題（ LP3），增加約束 x2≥3作子問(wèn)題（ LP4）。雖然迄今為止還沒(méi)有一個(gè) NP完全問(wèn)題被發(fā)現(xiàn)具有類(lèi)似單純形法那樣漂亮的指數(shù)算法，這也許是由問(wèn)題的 NP完全性本身決定的（注意：線(xiàn)性規(guī)劃問(wèn)題是 P問(wèn)題，具有良好的組合結(jié)構(gòu)）。我們將用到下面的已被證明的 NP完全問(wèn)題。 υ =Cmax表示排序優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)是全系統(tǒng)的加工時(shí)間最短，即由第一臺(tái)機(jī)器開(kāi)始加工起到最后一臺(tái)機(jī)器完工為止的時(shí)間跨度最小。 定理 （一維） Bin—packing問(wèn)題是 NP—完全的。 證明 稱(chēng)圖 為圖 G的補(bǔ)集，若 與 G有相同的頂點(diǎn)集，且（ υi,υj）是 的邊當(dāng)且僅當(dāng)它不是 G的邊。正如第八章所講，存在著大量具有 NP完全性的問(wèn)題，雖然許多人作了巨大的努力，仍未找到任何有效算法。 求最小的問(wèn)題是 P問(wèn)題，求最大的問(wèn)題可以是 NP完全的，這樣的例子也不少。由于事實(shí)上存在著無(wú)窮多個(gè) P問(wèn)題，而且即使某問(wèn)題是 NP完全的，它的許多特殊條件下的子問(wèn)題也仍然可以是多項(xiàng)式時(shí)間可解的，因而我們不可能對(duì) P類(lèi)作一完整的介紹。下面的圖 （ a）為歐拉圈，而圖 （ b）則為歐拉路，后者雖可一筆畫(huà)出，但必須以一個(gè)奇頂點(diǎn)為起點(diǎn)，以另一個(gè)奇頂為終點(diǎn)。 作為最短路徑問(wèn)題的一個(gè)應(yīng)用實(shí)例，我們來(lái)研究下面的設(shè)備更新問(wèn)題： 例 某單位使用一種設(shè)備。算法既可以通過(guò)對(duì)頂點(diǎn)逐次標(biāo)號(hào)來(lái)實(shí)現(xiàn)，也可以通過(guò)矩陣運(yùn)算進(jìn)行。由于 1是最小費(fèi)用流， 1的增廣網(wǎng)絡(luò)中不存在負(fù)圈，故 C中必有一邊（ i, j），其反向邊（ j, i）含在 P中（因?yàn)槿缛舨蝗唬?C不含 P中任意邊，則 C將含在 1的增廣網(wǎng)絡(luò)中，與 1為最小費(fèi)用流的假設(shè)矛盾，見(jiàn)圖 ），但這又說(shuō)明 P∪ （ C－（ i, j））是S到 t的更小費(fèi)用單位流增廣路，與 P是最小費(fèi)用單位流增廣路的假設(shè)矛盾。希望求出由 s到 t的最大流，使得總費(fèi)用最少，即求最大流 φ*，使 *( ,