第六章離散優化模 na1a2an，要求將它整理成由小到大排列（或由大到小排列）的順序：b1,b2,…,bn，b1≤b2≤…≤bn。（1）a1,a2,…,anb1a1,a2,…,anb1n—1b2，…，一直進行b1,b2,…,bn。b1b2bn2（步0

n(n2

步1 設已排好b1,…,bk(1≤k<n)，將按兩分法比較的方式把ak+1排入ak+1,bi+1,…,bkk+1<nk←k+11。我們來分析一下算法2b1,b2,b3,b4,b5,b6,b7，下一步將a8。先比較a8和b4若a8小于b4，則下一步比a8與b2，等等，a8共需作3次ak+12r－，1≤k＜2rrak+1安排r≤log2k+1，算法的總比較次數不超過：

k(n1)log2klog2kk

k

a

nn1nlog

f(nn(n1f(nn

nC 12a1a2ant1

t2

f2(n)n=100萬，C=100萬次/t1≈5.8t2≈20秒。可見在解較大21。一般模型中女兒數和求婚者人數可以不同A、B、C愿意 X Y

（矩陣中的元素cij為求婚者i娶j愿付的財禮數Z 7xijmaxcij3s.txij

33xijj

—11（根據這一方法將有：CY，BX，AZ，酋長得到的總財禮數34。分析：1的最大缺點是它沒有求出最好的結果，事實上，只要將CX，將AY，將BZ，則酋長可以得到的總財禮數將增加57。2（57，顯然，題的標準形式為酋n個女兒（含參數n，n個求婚者前來求婚cij,......,n；j （）maxcijns,txij

nnxijjx0或（6.2）n和矩陣Cnnn及Cnncij0有一些特殊的性質，存在著由匈牙利數學家Konig簡便解法——匈B（bijB為系數矩陣的指派問題具有相同的最優指派。6.3

18C 17 16解15，同樣，第二行元素減去171716，得 B

7 131

B 0 0* 4

由等價性，它也是例2的最優指派。 求解系數矩陣為C的指派問題 9 6 C 6 6 n=5，最優指派還無法看出。此時等價變換還可進行下去，步驟如0（2做0（未覆蓋元素中的最小采用，直到能選出足夠的0元素為至。例如，對例6.4變換后的矩陣再作變換，第三行、第五行元素減去2，第一列元素加上2，得到02030083580041400 現在已可看出，最優指派為24135一步的。3（an(其中a1指數算法（顯2n!大于2n可以證明，匈牙利算法的計算量為O(n3，即使n100，利用計算)M次運算的計算機，An的實例約需n2B2nA在一小時MM

100An=60000B28n1，B1Bn=50的實357年多。100（A10倍，而算法Bo2100<7表6- 量nN§6.2PNP式時間可以求解的問題。P?類.M，問NP問題，如果對它的每一個答案為“是”的實例可以在多項式時間里被驗NP也組成一個集合，此集合被稱為??類，不難證明???（多項式時間可NP題注：NP問題與NP難問題有專門的專業定義，本處從略。所謂的NP算機科學中亟待解決的重大理論問題之一：?=??嗎？這一問題極其困1972年，數學家Cook在其后來獲得圖靈（Turing）獎的著名Cook將這類問題稱為NP完全問題（簡稱問題式的次數越低越好。但對問題，既然全世界那么多人都找不到求解它有多難，它是P問題呢還是NP難的？就像醫生在發現患有腫瘤后，首多加。這里，我們只想粗略描述一下計算復雜性理論中的幾個重要概念。在§6.3中，介紹幾個會經常遇到又比較簡單的P問題并介紹開闊我們的眼界，也能大大增強我們解決實際問題的能力。在§6.4我們還將介紹幾個NP難的問題，目的是想說明當我們遇到NP難問題時，我們還有哪些事情可以做。通過這兩節來比較一下兩類問題的不同§6.3PPPPDantzig單純型算法（我們已在第五章中作了介紹。1972，Klee達7年的時間里，沒有人能回答這一問題。直到1979年，前格勒數學研究中的重要工作之一。可見，P與是相對而言的，相對于那些我們竭盡全力還找不到多項式時間算法NP以下，再舉一些經常會遇到而又較為簡單的P問題。6.5（最小生成樹問題）給定通圖G(V，E)，其中V為圖的頂點集合，E為圖的邊集。先最小生成樹（MinimumSpanningTreeMST）問題應當說是最簡PMST給定一個有8個頂點14條邊的圖，見圖6-1。要求求出該圖的一個最6-1.6.1步2.從最短邊開始，依次加入剩余邊中的最短邊，在產生子圈時去除該1。6.6（兩分圖的最大權匹配問題）（兩分圖）一個圖的頂點集合V如果可以被剖分成為兩個非空子集V1和V2，V1V2V且V1V2，位于同一子集中的頂點之間沒有邊（兩分圖最大權匹配問題）（直接算法從略。例6.7（最大流與最小費用最大流問題圖 16因為由35的邊已客滿，增大的流到了3處將無法流出。其實上述理由原網絡（6.2）中分析，而是按以下方法另行構筑了一個網絡，新網i容量（即原圖中的邊容量減去當前的實際流量原圖中由i到j的實0，則引入一條反方向的虛線邊，稱之為增廣邊，邊容量即為6.3。13256，故當前的流并非最大流。由于增廣最多可通（平衡條件，例如，在我們的例子中，要求頂點1只流出不流入、頂點6只最少，這就是最少費用最大流問題。這里希望流量能達到最大，又目標都達到最佳，要求出使所有目標都最佳的結果也常常非常（經常1從空網絡起步，空網絡是流量為02從當前流的增廣網絡中找出所有可能的增廣路，比較在每一條增廣增加一單位的流需要支付多少費用，找出費用最省的增廣路，在這條增廣增加流。依次按此方法增大流，在無法增大時，你求得的最6.8（最短路徑問題最短路徑問題也是P問題，可以用基于動態規劃的Dijkstrra算法求上PE的最短路徑必定整個地包含在AE的最短路徑上。由于動AE的最短路徑。圖 對圖中的網絡從起點A開始標號（E開始標號，但兩者作用不同先在A0。再找A最近的點B3，標上AB3的最短A點（A而來。一般，在標新頂點時，先找出離已圖6.6，A到E的最短路徑為A→B2→C1→D1→E，最短距離為19。例6.9（郵遞線路與一筆畫問題本問題與歐拉圈有關，于哥尼斯堡七橋問題。在哥尼斯堡的普列 6.（b（b即此圖可以一筆畫出）？（1（20（即無奇頂點如果一個圖的奇頂點數為2，26.（b4PNP6.8（216.5—例6.9了幾個P問題的簡單例P事實上有無窮多§6.4NP問題舉問題也有無窮多個，在本節中，介紹其中的幾個，以便說明對問題又該如何開展研究。6.10（哈密頓圈問題）GGV,EP問題；但問是否能不重復地走過每一個頂點卻很難回答，是問題6.11（旅行商問題）旅行商問題（TravelingSalesmanProblemTSP）的標準形式最短哈密頓圈。例如，你想游玩n個確定的城市，這n個城市之間兩兩都6年，Cook已經在其著名的中證明了哈密頓圈問題是問題。6.12（多旅行商問題）設有n個城n城市中任意兩個城市多旅行商問題（Multi-TSP，MTSP）又被稱為有女朋友的旅行商問題（TSPwithagirlfriend，因為你也可以假設只有一個旅行商，但將行程剖分成了m子圈。MTSP顯然也是NP難的，因為求解MTSP包含以1n個城市劃分成m（需求出最佳分組方法）2對每一組求解一個TSP其中步2要解的問題已經是NP難的了，不可能有多項式算法，除非?=??1999年大學生數學建模競賽的賽題A（災情巡視問題）就是一個旅行商問題雖然是NP難的，但對于災情巡視這樣MTSP的實例，我們仍可6.13（集裝箱問題——Bin—C的箱子（足夠數量n—ackng問題當我們一三夾以便鋸出n塊已知長n—pckng問n-ackgn—ackgP（10n—pckngP（P難的。Scheduling是一類應用面極廣的離散問題，其實它不是一個問題，而得出的模型是不同的。按目前流行的做法，人們常用三個參數α，β，描述一個特定的排序問題并記為α/β/排序問α描述機器情況標9000多個不12%P12%NP完全的。有關排序問題，目前已有數十本專著及成千如果我們的目的是要設計一個NP（?。既然如此，我們就不應當將自己的研究方向定為去尋找多項式算法，除非我們是想證明?=??（注：?=??不是一般性的難題，即使你化費畢生的精力也一般不會獲得成功！因此，我們應當非常，以免掉（NP難問題的近似算法舉例OPT（I）AII的最優目標函數rr≥1I∈D，總有A(I)≤則稱A為求解問題D的具有情況比r的近似算法或稱為啟發式算法（r（<<1AI)≥OTI)I成立）ADr1r（求最大的r盡可能大。6.15（TSPTSP是NP難的，有人證明，對于一般的TSP問題，即便連近似算法也（NP，但情況卻要好得多，此時存在著近似算法。1ITI中找不出連接所有頂點的最小生I是非連通的（注：求最小生成樹算法見§6.32（doubling）將求得的最小生成樹的每邊重復取次，得到一個經3Shortcuts（走捷徑）I的一個旅行圈。即從2得到的圈作環游。當遇到下一頂點已到過時，跳過Folklore給出的算法主要應用了求最小生成樹的算法和三角不MSTMST（I）IMST6.1；6.1TSPIMST(I)證明設τ*I的最優圈，e為τ*中的任意一邊，則τ*－{e}顯然是I1Tl必小于最優圈τ*的長度OPT（I。又因為I滿足三角不等式，故步3Shortucts求得的近MS（≤2OPI（，順便，對MST算法比2是不能被更小的數替代的。因為可2r，總可以找到一個滿足三角不TSPIMST（I）＞rOPT（I（舉例從略。，r2必須改進，因為所有邊加倍是造成旅行1IT2TT的所有奇頂點（必有偶數個）間的距離，并求奇定點間的一個最小匹配M。將M中的邊加入T，得到一個包3利用Shortcuts等人的算法）近似算法2是由Christofide，為了敘述上的方便，用C(I)表示用此算法求得的近似最優圈的長度。3定理6.2對任一滿足三角不等式的TSP的實例I2證明2M（6.8中的粗線）M’T的奇頂點間的另6.8中的波浪線。

l(Ml(M’) M是最小權匹配。l(M)l(M’)1l(M)

2l(T)OPT(I)3C(I)≤l(T)+l(M)2

6.16（一維裝箱問題的近似算法off-line問題。（一）on-lineNF（NextFit）1P1B12Pi,(i=2,…,n)BjPi可繼BjPiBj1中，即裝入下一空箱中（前面NF（L6.3NF(L)2OPT(L)2是緊的，即不能被減小。定理證明十分容易，留作習題（12FF（Fit）算法步1 將P1裝入B1中。步2 裝Pi,i=2,…,n)。找出最小的j使Pi可裝入Bj中，將Pi裝入其6.4FF(L)FF算法將LFF(L)1.7OPT(L)+1，且1.7是緊的，即1.7不能被減小證明有較度，從BF（BestFit）算法步1 裝P1裝入B1中。步2 裝Pi,i=2,…,n。在能夠裝下Pi的箱中找出已裝得最多（即剩余空間最小）的一只Bj，將Pi裝入Bj。6.5BF(L)BFL≤1.7OPT(L)+1，且1.7是緊的證明同樣，從略證明。事實上，Ullman1971FF（L）1.7OPT(L3；接著，Johnson1974FF（L）≤1.7OPT(L)+2；最后，Garey（二）off-lineFFD（FitDecreasing）算1Ll(Pi)l(P1)≥l(P2)l(Pn)2FFLBFD（BestFitDecreasing）步1 將L先整理成l(Pi)不增的順序。步2 對L中的物品用BF算法裝箱。6.6FFD（L）BFD（L）FFDBFD算法L中的物品裝箱所使用的箱法，則有

OPT(L)+9 OPT(L1

1973

OPT(L419919

OPT(L19 ，

OPT(L)+1中的 是 6.171（標準形式1, 1i6m 2 6mil(P)1 1 12mi11 2 18miFFD(L)11 NF、FF、FFD算法，它們裝箱效果一個比一個好，但這并不表NF、FF就失去的存在的價值。FF，FFD算法都要求等所有物品全部裝NF算法無此限制，對箱子必須一箱一箱NF算法；FFD算法還要求所有物品全部NF、FF算法在給某批物品裝箱時，可以不知道下一個物packingNP完全問題，有時設計某些尋找近似最優解的壞情況分析或平均情況分析）的近似算法就像一件鑒定的新產品或一種臨床試用的新藥品一樣，是不會們普遍接受的。研究近似算法的主要就在于：一方面，我們希望構造出r更小的近似算法；另一方（NP難問題實例的求解NP難的問題，雖然我們無法在合理的時間內求出該問題每一個氣。例如，在解答大學生數學建模競賽1999年的A題（災情巡視）NP難的而去設計近似算法，并在算法有的某些性質或哪些結果不可能是最優解，用這些條件（被稱為消去（分支定界法例 某房屋出租單位有活動91萬元，擬購房出租，現有2000元，第二種房的月收入為3000元。問此單位應購兩種房各多少建模記x1、x2分別為兩種房的套數，顯然x1、x2必須為整數，故要求求解的問題為整數規劃（ILP（NP難的） 0.2x1+ 13x1+18.2x2≤914x1+40x2≤140x1、x2≥0Z=1.466萬元。（2,3（2,4（3,3（3,4Z=1.3萬元，并非最優解（x1=4，x2=2，Z*=1.4萬元。求解松馳線性規劃雖無法找出最優整數解，但卻能該實例目標函數值的一個下界（指min問題。在本實例中，由于問題是求目標數最遠的分離，例如我們選取x1，兩個新的松馳線性規劃。 0.2x1+ 13x1+4x1+x1、x2≥0 0.2x1+ 13x1+4x1+x1、x2≥0（ILP（2.44,3.26）已不在（LP1）與（LP2）的可行域中（這正是分枝（2，3.3（LP2）（3,2.861.458萬元。（LP3x2≥3作子問題（LP4（LP3）2（LP2（UB）Z=1.4Z=1.4，