數(shù)學(xué)建模離散優(yōu)化模型與算法設(shè)計(jì).ppt

《數(shù)學(xué)建模離散優(yōu)化模型與算法設(shè)計(jì).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)建模離散優(yōu)化模型與算法設(shè)計(jì).ppt（156頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)學(xué)建模離散優(yōu)化模型及算法設(shè)計(jì) 第 9章： 某些 P問題及其算法 之前 ,我們介紹了與計(jì)算復(fù)雜性有關(guān)的一些基本概念 .人們發(fā)現(xiàn) ,在離散 問題中存在著兩個(gè)互不相交的類： P類與 NP完全類（若 P NP）。前者具 有求解的有效算法而后者不可能有這種算法。從這一點(diǎn)上講， P問題可 以看成是一類具有良好性質(zhì)而又較容易求解的問題，而 NP完全問題則是 固有地難解的。 在 8.4中看到，有著廣泛應(yīng)用背景的線性規(guī)劃問題是一個(gè) P問題。這樣， 作為線性規(guī)劃子問題的運(yùn)輸問題及作為運(yùn)輸問題子問題的指派問題自然 更是 P問題。雖然從平均的角度講，人們似乎更常遇到 NP完全問題，但 P 仍不失為一個(gè)十分重要的問題

2、類。一方面，很多 P問題象線性規(guī)劃一樣有 著極廣泛的應(yīng)用前景，且它們本身又是十分有趣的；另一方面，它們也 是研究一些更為復(fù)雜、難解的問題時(shí)經(jīng)常被采用的研究工具。在本章中， 將再介紹一些經(jīng)常遇到的 P問題并給出求解它們的有效算法。 一、擬陣問題及貪婪算法 在 P類中又存在著一個(gè)被稱為擬陣的具有更為良好性質(zhì)的問題類，其中的 任一問題均可用一種被稱為貪婪法的方法來求解，而這一性質(zhì)并不是所有 的 P問題都具有的。 例 9.1 （最小生成樹問題 MST） 給定一連通圖 G=（ V， E）， ， 有一表示邊長的權(quán) C（ e）（表示頂點(diǎn)間的距離或費(fèi)用），求此圖的具有 最小總權(quán)的生成樹。 e 此問題的標(biāo)準(zhǔn)形式

3、為給定一完全圖 G，其每邊賦有一權(quán)數(shù)，求此完全圖的 最小生成樹。所謂樹是指連通而無圈的圖，單獨(dú)的一個(gè)點(diǎn)也可看成一顆 樹。樹用 (U， T)表示， U為樹的頂點(diǎn)， T為樹的邊集。不相交的樹的集合 被稱為森林。一個(gè)連通圖的生成樹是指圖中具有最多邊數(shù)的一棵樹。容 易證明，對(duì)于一個(gè)連通圖 G， G 的任一生成樹必有 V -1條邊。 求解最小生成樹的算法主要依據(jù)下面的定理： 定理 9.1 設(shè) （ V1， T1）， （ Vk ,Tk） 為連通圖 G中的森林， V1 U V2U Vk=V。 k,若僅有一個(gè)頂點(diǎn)在 Vi中的具有最小權(quán)的邊為（ ,u）， 則必有一棵 G的最小生成樹包含邊（ ,u）。 ,1i 根據(jù)

4、定 1可以作了如下算法：任選一點(diǎn) ，令 若 V1=V，停；否則，找出僅有一個(gè)頂點(diǎn)在 V1中的邊里具有最小權(quán)的邊 （ ,u），設(shè)，將 u加入 V1（ ,u）加入 T。重復(fù)上述步驟，直到 V1=V。 1 11: , : .VT 證明 ：設(shè) G的一棵最小生成樹（ V， T）不含（ ,u）。將（ ,u）加入 T， 由于（ V， T）是生成樹， T U（ ,u）中含有過（ ,u）的唯一的圈。不 妨設(shè) ，則 ，此圈中的點(diǎn)不全由 Vi中的點(diǎn)組成 ,因此必存在 圈中的另一邊 。刪去邊 得到一新的生成樹（ V， T1）， T1= ，須其總權(quán)不超過（ V， T）的權(quán) ,即（ V， T） 是包含邊（ ,u）的最小生

5、成樹。 iV iV , iiuu u , uu 例 9.2 求圖 9.1中圖 G的最小生成樹。 解 ： 不妨從頂點(diǎn)開始尋找。 標(biāo)號(hào) 1，先加入 （因?yàn)檫厵?quán) 最?。?， 標(biāo)號(hào) 2。再加入 標(biāo)號(hào) 3。 ，每次加入一條一頂點(diǎn)已標(biāo) 號(hào)加一頂點(diǎn)未標(biāo)號(hào)而又具有最小權(quán)的邊，直到所有頂點(diǎn)均標(biāo)號(hào)為止。找 到的最小生成樹已用又線標(biāo)在圖 9.2中。 1 1 1,V 2 12 2 44 容易看出算法的計(jì)算量為 O (V)2 ，所以此算法是有效算法，若 G具有 O（ ）條邊，其中 n= V ，計(jì)算量的界還是不能改進(jìn)的，因?yàn)槊織l 邊至少應(yīng)被檢查一次。 2nC 由例 9.2可以看出，算法執(zhí)行的每一步均加入一條可以加入的（即不

6、生成 圈的）具有最小權(quán)的邊，而不去考慮它對(duì)以后選取的影響，這種算法被 稱為貪婪算法。 例 9.3 (入樹問題 ) 給出一個(gè)有向圖 G=（ V， A），對(duì) A中的每一條孤 e，給 出一個(gè)權(quán) C（ e），求 A的一個(gè)具有最大權(quán)（或最小權(quán)）的子集 B，要求 B 中任意兩條孤都沒有公共的終點(diǎn)。 考察下面的入樹問題實(shí)例： 例 9.4 給出有向圖 G=（ V， A） （圖 9.3） ，孤上標(biāo)出的數(shù)字為該邊的 權(quán)，求此圖具有最大權(quán)的入樹。 解：由于入樹不能包含具有公共終點(diǎn)的孤，故對(duì)每一頂點(diǎn) 只能選 取一條入孤。為使選出的弧具有最大權(quán)，只需要對(duì)每一頂點(diǎn)選取權(quán)最大 的入孤，可用計(jì)算量為 O（ V E ）的貪婪法

7、求解，具有最大權(quán)的 入樹為 。 i 1 2 2 1 2 4 4 5 5 3, , , , , , , , , 類似地，出樹問題也可以用貪婪法求解。 例 9.5 (矩陣擬陣問題 )給出一個(gè)矩陣 Amxn，記其 n個(gè)列向量為 e1, ， en。 設(shè)對(duì)每一列向量 en已指定一權(quán) C（ en）求 的一個(gè)線性無 關(guān)的子集，它具有最大的權(quán)和。 1, ,i in 易見，這一問題也可以用貪婪法求解。集合 的線性無關(guān)的 子集被稱為獨(dú)立子集，利用貪婪法必可求得具有最大權(quán)的獨(dú)立子集，可用 線性代數(shù)知識(shí)加以證明 （見習(xí)題 1） 。 1, ,i in 例 9.6 求矩陣 A的列向量具有最大權(quán)和的獨(dú)立子集 7*45762

8、101 5431000 1273121 4531011 A C(ei) 8 4 7 5 2 6 4 解： 采用貪婪法，先取權(quán)最大的列 e1，同時(shí)對(duì) A作高斯消去，逐次加入 線性無關(guān)的向量： A的列向量中具有最大權(quán)的獨(dú)立子集為 。 1 3 5 4 取 e6 取 e4 取 e3 4 5 1 1 0 2 0 5 4 3 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 1 2 3 1 1 1 0 5 4 3 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 A 4 / 9 0 4 / 19 4 / 9 0 2 0 4 / 5 1 4 / 3 4 / 1 0

9、 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 定義 9.1 (擬陣 ) 設(shè) E是一個(gè)有限集， 為 E的部分子集構(gòu)成的封閉系統(tǒng)（即 若 ，則必有 ）。若 M=（ E， ）上的離散優(yōu)化問題的每一 實(shí)例均可用貪婪算法求出最優(yōu)解，則稱 M為一擬陣。（注： 被稱為獨(dú)立系 統(tǒng)）。 ,AA A 現(xiàn)以矩陣擬陣為例，對(duì)定義 9.1作一說明。 對(duì)矩陣擬陣的每一實(shí)例， E=e1, en為矩陣列向量的集合， 為 E的線性無 關(guān)子集構(gòu)成的系統(tǒng)，稱為獨(dú)立系統(tǒng)，其元素被稱為獨(dú)立子集。由于 E的任一 線性無關(guān)子集的子集也是 E的線性無關(guān)子集，故獨(dú)立系統(tǒng) 是封閉的。又由 于這一離散優(yōu)化問題的任一實(shí)例都可用貪

10、婪法求解，故構(gòu)成一擬陣，被稱 為矩陣擬陣。例 9.1被稱為圖擬陣，例 9.3被稱為劃分?jǐn)M陣。 擬陣問題（或稱擬陣結(jié)構(gòu)） 有一個(gè)明顯而又本質(zhì)的特性，其任一極大獨(dú)立 子集中包含著相同個(gè)數(shù)的元素，從而可以引入基的概念。例如，矩陣列向 量的所有線性無關(guān)極大組均具有相同的向量個(gè)數(shù)，這就導(dǎo)出了基 即矩 陣列秩的概念。對(duì)于圖擬陣，每一極大獨(dú)立集均為一生成樹，其邊數(shù)均為 |V|-1。對(duì)于劃分?jǐn)M陣，孤集被劃分成個(gè) |V|個(gè)子集，每一子集由指向同一 頂點(diǎn)的孤組成。顯然，任一極大獨(dú)立集應(yīng)在每一子集中取一條孤，故其基 數(shù)為頂點(diǎn)個(gè)數(shù)。 我們不加證明地引入下面的定理，雖然其證明并不十分困難。 定理 9.2 E為一有限集合

11、，為 E的部分子集構(gòu)成的封閉獨(dú)立系統(tǒng)。以下 兩個(gè)條件均為 M=(E, y)構(gòu)成擬陣（即其上的優(yōu)化問題可用貪婪法求解） 的充分必要條件： （條件 2） 若 I、 I均為 A的兩個(gè)極大獨(dú)立集，則 |I|=|I|。 AE （條件 1） 若 I、 I |I| M|， G 中至少含一條路，其中 M中的邊多于 M中的邊，不難看出，這條路是 G的 關(guān)于 M的增廣路。 現(xiàn)在可以看出，找最大匹配的關(guān)鍵在于找增廣路。讀者不難用頂點(diǎn)標(biāo)號(hào) 的辦法（由未蓋點(diǎn)出發(fā)），作出一個(gè)求解兩分圖匹配的增廣路算法。此 算法稍加改動(dòng)，還可以用于非兩分圖的情況。 三、網(wǎng)絡(luò)流問題 網(wǎng)絡(luò)流問題是又一類具有廣泛應(yīng)用前景的 P問題，本節(jié)將介紹一

12、些有關(guān) 網(wǎng)絡(luò)流問題的基本理論與算法。 1、最大流問題（ MFP） 邊賦值的有向圖稱為網(wǎng)絡(luò)。給定一個(gè)網(wǎng)絡(luò)，其邊賦值表示該邊的容量。最 大流問題要求在不超過邊容量的前提下求出網(wǎng)絡(luò)中兩個(gè)指定頂點(diǎn)之間的最 大流。例如：當(dāng)網(wǎng)絡(luò)是通訊網(wǎng)時(shí)，我們可能會(huì)去求出網(wǎng)絡(luò)中兩個(gè)指定點(diǎn)間 的最大通話量；當(dāng)網(wǎng)絡(luò)是城市的街道時(shí)，我們又可能會(huì)去求兩地間的最大 交通流，即單位時(shí)間內(nèi)允許通過的車輛數(shù)等等。 建模： 給定一有向圖 G=（ V， A）， A的每一條孤（邊）（ i,j）上已賦一 表示邊容量的非負(fù)整數(shù) C（ i,j）。并已指定 V中的兩個(gè)頂點(diǎn) s、 t，分別稱 它們?yōu)榘l(fā)點(diǎn)和收點(diǎn)。 設(shè)網(wǎng)絡(luò)中已存在一個(gè)流（不一定是最大流），

13、記孤（ i,j）上的流量為 （ i,j），記 s發(fā)出的總流量（即 t收到的總流量）為 ，根據(jù)平衡條件，可 得如下的約束條件， ，有 i 其中是 指 A中以頂點(diǎn) i為起點(diǎn)的孤集， 是指 A中以 i為終點(diǎn)的孤集 , ( .1)式表示 s發(fā)出流為 ， t收入的流為 ，其余各點(diǎn)只起中轉(zhuǎn)作用， 既不增加也不消耗流量。根據(jù)邊容量限止，還應(yīng)有 iA iA , , , ,i j C i j i j A 而我們的愿望是使總流量盡可能地大。 即在（ 9.1）、 (9.2)式約束下 使達(dá)到最大，易見，這是一個(gè)線性規(guī)劃問題的子問題，故 類。 P tiv tsi siv jiji Aiji Aiji 若 若 若 .0)

14、,(),( ),( ),( 對(duì)于一個(gè)較為復(fù)雜的網(wǎng)絡(luò)，要想直接找出最大流是不太可能的。為了簡 化問題，我們先引入一些符號(hào)。 記 、 為 的兩個(gè)不相交的子集， s ，用（，）表示發(fā) 點(diǎn)在，收點(diǎn)在的邊集， 記 ，并定義如下的切割概念： ,P t Q , , , , , , i P j Q i P j Q P Q i j C P Q C i j 定義 9.5 （切割） 設(shè) 是 的頂點(diǎn)集合 的一個(gè)真子集， 為 關(guān)于 的補(bǔ)集。若 、 滿足 且 則稱 和 為的一個(gè)切割。 P P SP tP P 根據(jù)切割的定義可以看出，當(dāng)和 為一切割時(shí)，如果去掉連接 和的 邊集（ ， ），就切斷了由通往 t的所有通路。所以，

15、對(duì)網(wǎng)絡(luò)的任一 切割（ ， ）， （ ， ）必為最大流的一個(gè)上界， 而 。 P P P P ,P P P P 例 9.9 網(wǎng)絡(luò)如圖 9.6所示，邊（弧）上的兩數(shù)字分別表示邊容量及實(shí)際流 量。取，則，顯然 、 是網(wǎng)絡(luò) 的一個(gè)切割。對(duì)于這一切割容易算出 而網(wǎng)絡(luò)的流量 。 P , 6 , , 9P P C P P 為了盡可能地增大網(wǎng)絡(luò)上的流量，按如下方法作出一個(gè)和 具有相同頂 點(diǎn)并具有相同發(fā)點(diǎn)和收點(diǎn)的增廣網(wǎng)絡(luò) （ ） （簡記 ）。 包含 兩類邊，對(duì)中每一條邊（ i， j） ： A （ 1）若 ，作正向邊（ i， j） , 規(guī)定容量 ，即剩余容量。 ,i j C j i , , ,C j i C j i

16、 j i （ 2）若 ，作反向邊（ j,i）， 規(guī)定容量 事實(shí)上是邊（ j,i）上最多可減少的容量。 ,0ij , , ,C j i j i C j i 第一類邊稱為正規(guī)邊，第二類邊則稱為增廣邊。例如由圖 9.6中的流可以 作出其相應(yīng)的增廣網(wǎng)絡(luò)圖 9.7，其中實(shí)箭線為正規(guī)定，虛箭線為增廣邊， 邊上的數(shù)字為邊容量。 如果增廣網(wǎng)絡(luò)上存在著由 s t的通路 p（稱為原網(wǎng)絡(luò)的一條增廣路）， 記 ，則只要在 P中的一切正規(guī)邊上增加流量 a，而在對(duì)應(yīng) 增廣邊（ j, i）， G的邊（ i, j）上減少流量 a，就得到 G的一個(gè)由 s t的增 大了流量 a的更大的流。例如，從圖 9.7上可以找出增廣路 ，

17、a=2。于是，圖 9.6中的流可改進(jìn)增大為圖 9.8(a)中的流，總流 量為 7。由于其增廣網(wǎng)絡(luò)圖 9.8(b)中不再存在增廣路，無法再繼續(xù)增大。 容易看出，若取 s出發(fā)（在增廣網(wǎng)絡(luò)上）可到達(dá)的點(diǎn)的集合為 P，則 P= , ， = , , , ， C（ P， ） =7，而流量已達(dá)到 7，故此 流已是最大流。 ( , )m i n ( , )i j Pa C i j P P （ 1） ( , ) ( , ) , ( , ) ( , )i j C i j i j P P （ 2） ( , ) 0 , ( , ) ( , )i j i j P P 故 ， 已不能再增大，（注：這是線性規(guī)劃的補(bǔ)松馳定理

18、）。 ( , ) ( , )P P C P P 綜上所述，有下面的有關(guān)網(wǎng)絡(luò)流問題的定理。 定理 9.5 （ Ford和 Fulkerson最大流最小切割定理） 任一由 s到 t的流， 其流量不大于任一切割的容量 C（ P， ），而最大流的流量則等于最小 切割的容量。進(jìn)而 為最大流且（ P， ）為最小切割當(dāng)且僅當(dāng)： （ 1） 有 （ 2） 有 。 P P ( , ) ( , )i j P P ( , ) ( , )i j C i j ( , ) ( , )i j P P ( , ) 0ij 增廣路可以通過對(duì)頂點(diǎn)標(biāo)號(hào)的方法來尋找。由于邊容量均為整數(shù)，而每次 經(jīng)改進(jìn)，流量至少增加一，故算法總能很快求

19、得最大流。 定理 9.4 網(wǎng)絡(luò) G上的流是最大流的充要條件為其增廣網(wǎng)絡(luò)上不存在由 s到 t 的通路。 證明： 若增廣網(wǎng)絡(luò)上存在由 s到 t的通路 P，則對(duì) P上的正規(guī)邊（ i, j）增加流 量 a，對(duì) P的增廣邊（ j, i）對(duì)應(yīng) G的邊（ i, j）減少流量 a，即可得到一個(gè)更 大的可行流。若增廣網(wǎng)絡(luò)上不存在由 s到 t的路，記增廣圖上 s可達(dá)到的點(diǎn)組 成的集合為 P，則對(duì)切割（ P, ）必有： P 2、最小費(fèi)用最大流問題 對(duì)于一個(gè)給定的網(wǎng)絡(luò)，由發(fā)點(diǎn) s到收點(diǎn) t常常存在著多個(gè)具有相同流量的最 大流。如圖 9.9所示，圖中的（ a）、（ b）、（ c）均是流量為 7的最大流， 邊上的兩個(gè)數(shù)字

20、依次為容量和邊上的實(shí)際流量。有時(shí)候，當(dāng)流流經(jīng)一條邊 時(shí)需支付一定的費(fèi)用，我們不僅希望找出一個(gè)最大流，而且希望找出的最 大流在具有相同流量的流中具有最小的總費(fèi)用，這時(shí)問題可描述為：對(duì)有 向圖 G=（ V， A）的每條邊（?。?i, j）給定一個(gè)邊容量 C（ i, j）及一個(gè) 單位流量費(fèi)用 l(i, j)。希望求出由 s到 t的最大流，使得總費(fèi)用最少，即求最 大流 *，使 * ( , ) ( ) m in ( , ) ( , ) i j A L l i j i j 最大流 例如，在交通網(wǎng)絡(luò)中， l(i, j)可以是 i, j之間的距離或運(yùn)費(fèi)。自然，在運(yùn)送 相同數(shù)量貨物時(shí)，我們希望總距離或總運(yùn)費(fèi)最

21、小?，F(xiàn)在，我們將以最大 流問題的增廣路算法為基礎(chǔ)，導(dǎo)出求解最小費(fèi)用最大流問題的算法。 對(duì)于網(wǎng)絡(luò)上的一個(gè)現(xiàn)行流 ，作出其增廣網(wǎng)絡(luò) G( )，對(duì) G中的正規(guī)邊 賦值 l(i, j)，對(duì) G中的增廣邊 (i, j)則賦值 l(i, j)。 定義 9.6 增廣網(wǎng)絡(luò) G上由 s到 t的流量為零但邊流量不全為零的流稱為一個(gè)循環(huán)流。 最小費(fèi)用最大流問題可以變換成為一個(gè)線性規(guī)劃問題，根據(jù)線性規(guī)劃理 論可以證明下面的定理： 定理 9.6 網(wǎng)絡(luò)中的流 是最小費(fèi)用的，當(dāng)且僅當(dāng)其增廣網(wǎng)絡(luò) G中不存在 負(fù)費(fèi)用的循環(huán)流（證明略）。 例 9.10 圖 9.10（ a）給出了有向圖 G上的一個(gè)可行流，其中弧上的三個(gè)數(shù) 字分別

22、為容量、單位流費(fèi)用及實(shí)際流量。圖 9.10（ b）為相應(yīng)的增廣網(wǎng)絡(luò)， 其中邊（弧）上的兩個(gè)數(shù)字分別為容量及單位流費(fèi)用。求此網(wǎng)絡(luò)的一個(gè)更 小費(fèi)用流。 從圖 9.10（ b）中可以找出一個(gè)負(fù)費(fèi)用循環(huán)流 s 2 1 s（其余邊流量 為 0），每單位流量的總費(fèi)用為 5。調(diào)整此循環(huán)流上的流量，得到圖 9.11（ a）中的流。原先的流總費(fèi)用為 17，調(diào)整后的總費(fèi)用為 12，減少值 為負(fù)費(fèi)用循環(huán)流的總費(fèi)用。 圖 9.11（ a）中流的增廣網(wǎng)絡(luò)（ b）中已不存在負(fù)費(fèi)用循環(huán)流，它是一個(gè)最小 費(fèi)用的流。 定理 9.7 設(shè) 1是網(wǎng)絡(luò)上流量為 的最小費(fèi)用流， 2是其增廣網(wǎng)絡(luò)上由 s到 t的 最小費(fèi)用單位流增廣路，則

23、1+2是此網(wǎng)絡(luò)流量為 +1的最小費(fèi)用流。 證明： 設(shè) 1+2不是流量為 +1的最小費(fèi)用流，由定理 6，在 1+ 2的增廣網(wǎng) 絡(luò)中必存在一負(fù)圈 C。記構(gòu)造 2的增廣路為 P。由于 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è)矛盾，見圖 9.12），但這又說明 P （ C（ i, j）是 S到 t的更小費(fèi)用單位流增廣路，與 P是最小費(fèi)用單位流增廣路的假設(shè)矛盾。 根據(jù)定理 9.7及定理 9.6，求最大流的算法只需稍作 變動(dòng)即可用來求解最小費(fèi)用

24、最大流。算法可以用 歸納方式給出，當(dāng) =0時(shí)，可取 =0，這顯然是 =0 的最小費(fèi)用流。在以后逐次增大流量時(shí)，若增廣 網(wǎng)絡(luò)中存在著多于一條增廣路時(shí)，每次均選用其 中單位流費(fèi)用最小的一條。這樣，每次得到的均 為相同流量的流中費(fèi)用最小的，而最后得到的即 為最小費(fèi)用最大流。 網(wǎng)絡(luò)流問題的算法在解決實(shí)際問題時(shí)常常被用到。它可用來求解運(yùn)輸問 題、指派問題及賦權(quán)兩分圖匹配問題（等價(jià)于指派問題），也可用來尋 找網(wǎng)絡(luò)的瓶頸 即最小切割（ P， ）確定的邊。作為一個(gè)網(wǎng)絡(luò)流問題 的應(yīng)用實(shí)例，我們來求解例 9.7中的婚姻姻問題：增加發(fā)點(diǎn) s和收點(diǎn) t，將 原圖的邊改為有向邊，所有邊的容量為 1。找出最大財(cái)禮數(shù) 28

25、，以此數(shù) 減每邊原有的財(cái)禮費(fèi)，并用此差為各邊的費(fèi)用，得一最小費(fèi)用最大流問 題（未注數(shù)字的邊費(fèi)用均為零），其網(wǎng)絡(luò)圖見圖 9.13。此問題在使用三 次增廣路后可求得最佳結(jié)果。 P 四、最短路徑問題 最短路徑問題是又一個(gè)經(jīng)常遇到的 P問題，它在工藝流程的安排、管道或 網(wǎng)絡(luò)的鋪設(shè)、設(shè)備更新等實(shí)際生產(chǎn)中常被用到，是網(wǎng)絡(luò)規(guī)劃的基本問題 之一。顧名思義，最短路徑求的是以下問題：給定一個(gè)網(wǎng)絡(luò)，如何求出 網(wǎng)絡(luò)中指定兩點(diǎn)間總距離（或總費(fèi)用）最小的路徑。 例 9.11 給定圖 9.14中的網(wǎng)絡(luò)，邊上的數(shù)字為兩頂點(diǎn)間的距離（或費(fèi)用）， 求由 A到 E的最短路徑。 求解最短路徑問題的 Dijkstra算法體現(xiàn)了動(dòng)態(tài)規(guī)劃

26、算法的基本思想。若點(diǎn) P在 A到 E的最短路上，則 P到 E的最短路徑必整個(gè)地包含在 A到 E的最短路 徑上。因?yàn)椋舨蝗?，將?P到 E的最短路徑導(dǎo)出 A到 E的更短路徑，從而 導(dǎo)出矛盾。算法既可以通過對(duì)頂點(diǎn)逐次標(biāo)號(hào)來實(shí)現(xiàn)，也可以通過矩陣運(yùn) 算進(jìn)行。在使用標(biāo)號(hào)法時(shí)，既可以從起點(diǎn)開始標(biāo)，也可以從終點(diǎn)開始標(biāo)。 （兩者目的略有不同）對(duì)例 9.11中的網(wǎng)絡(luò)，如從起點(diǎn) A開始標(biāo)導(dǎo)，先在 A 點(diǎn)標(biāo)上 0。再找出離 A最近的點(diǎn) B3，標(biāo)上 A到 B3的最短矩離 1并記錄下 A點(diǎn) （表明由 A而來）。一般，在標(biāo)新頂點(diǎn)時(shí)，先找出離已標(biāo)號(hào)頂點(diǎn)最近的頂 點(diǎn)。比較各已標(biāo)號(hào)頂點(diǎn)（與擬標(biāo)號(hào)頂點(diǎn)有邊相連）的標(biāo)號(hào)與它到擬標(biāo)

27、號(hào) 頂點(diǎn)距離之和，找出各種中最小者作為新頂點(diǎn)的標(biāo)號(hào)，并記錄下其前的 已標(biāo)號(hào)頂點(diǎn)。直到擬到達(dá)的終點(diǎn)已標(biāo)號(hào)為止。例如，圖 9.15指出， A到 E 的最短路徑為 A B2 C1 D1 E，最短距離為 19。 容易看出，算法是多項(xiàng)式時(shí)間的。在標(biāo)每一頂點(diǎn)時(shí)，最多作了 | V |次運(yùn)算。 算法進(jìn)行中，事實(shí)上在構(gòu)造一棵由已標(biāo)號(hào)頂點(diǎn)及它們與其前行點(diǎn)間的邊 組成的樹。每一頂點(diǎn)均不可能重復(fù)標(biāo)號(hào)，故總計(jì)算量的一個(gè)上界為 O （ |V|2）。 按一般習(xí)慣，動(dòng)態(tài)規(guī)劃算法常按逆順序進(jìn)行。圖 9.16給出了按向前標(biāo)號(hào)的 結(jié)果，最短路徑已用雙線劃出。 從圖 9.15中可看出 A到各點(diǎn)的距離及最短路徑，而從圖 9.16中則可

28、看出由 各點(diǎn)到 E點(diǎn)的距離及最短路徑，這是兩者的區(qū)別。 讀者不難給出一般問題的計(jì)算步驟，也不難推廣得到能求出任意兩點(diǎn)間最 短路徑的算法。 作為最短路徑問題的一個(gè)應(yīng)用實(shí)例，我們來研究下面的設(shè)備更新問題： 例 9.12 某單位使用一種設(shè)備。該設(shè)備在 5年內(nèi)的預(yù)期價(jià)格見表 9.1，使用 不同年數(shù)的設(shè)備的年維修費(fèi)用見表 9.2 ?，F(xiàn)準(zhǔn)備制訂一個(gè)五年內(nèi)的設(shè)備 更新計(jì)劃，使五年內(nèi)支付的設(shè)備購置費(fèi)用及總維修費(fèi)用最少。 這顯然是一個(gè)十分有意義的實(shí)際問題，即使作為個(gè)人，也會(huì)經(jīng)常遇到更 換交通工具、家用電器等設(shè)備更新問題的實(shí)例。當(dāng)然，作為一般情況， 還可能要考慮殘值，如購買了新車，舊車可以折價(jià)處理，回收資金與已

29、使用年數(shù)有關(guān)。 解： 作有向圖圖 9.17，圖中點(diǎn) i表示第 i年初（或第 i 1）年末），?。?i, j） 上的數(shù)字表示第 i年初購買設(shè)備到第 j年初更換，在該段時(shí)間內(nèi)的總費(fèi)用。 例如，?。?， ）上的數(shù) 68表示第一年初購買設(shè)備到 5年后的第六年 初更換，需支付購設(shè)備費(fèi) 10萬元及各年維修費(fèi) 58 萬元，共計(jì) 68萬元。 問題化為求由頂點(diǎn) 到頂點(diǎn) 的最短路。 容易看出，作出 n年設(shè)備更新問題的有向圖將問題化為最短路徑問題大約 需要 O(n2)計(jì)算量，其后要求求解的最短路徑問題的計(jì)算量也是 O(n2)，故 設(shè)備更新問題可在 O(n2)時(shí)間內(nèi)求解。 表 9.1 表 9.2 第 i年 1 2 3

30、 4 5 價(jià)格（萬年） 10 10 11 12 13 已使用年數(shù) 0 1 2 3 4 （萬年） 4 8 11 15 20 五、歐拉圈與最短郵路問題 歐拉圈問題起源于著名的七橋問題。給定一個(gè)無向圖 G=（ V， E），問能 否由一個(gè)頂點(diǎn)出發(fā)，經(jīng)且僅經(jīng)過每條邊一次并返回原出發(fā)頂點(diǎn)。如果能夠， 則每一個(gè)這樣的圈被稱為圖 G的歐拉圈，而圖 G則被稱為是一個(gè)歐拉圖。 顯然，圖 G為歐拉圖的充要條件是它可以被一筆畫出且首尾相連（當(dāng)首尾 不能相連時(shí)則被稱為歐拉路）。由此，立即可得出下面的定理： 定理 9.8 G為 歐拉圖的充要條件是： G是連通的且 G的每一個(gè)頂點(diǎn)都與偶 數(shù)條件相關(guān)聯(lián)。 把關(guān)聯(lián)偶數(shù)條邊的頂點(diǎn)

31、稱為偶頂點(diǎn)，把關(guān)聯(lián)奇數(shù)條邊的頂點(diǎn)稱為奇頂點(diǎn)， 則容易看出奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)（因?yàn)槊恳还P畫都產(chǎn)生一個(gè)起點(diǎn)與 一個(gè)終點(diǎn)），又易得出 定理 9.9 G為歐拉路的充要條件為： G是連通的且奇頂點(diǎn)的個(gè)數(shù)為 2。 綜合定理 9.8和定理 9.9可知， G可一筆畫出的充要條件為 G是連通的且奇頂 點(diǎn)的個(gè)數(shù)為 0或 2，當(dāng)奇頂點(diǎn)個(gè)數(shù)為零時(shí)，尚可設(shè)法使起點(diǎn)和終點(diǎn)相重。 下面的圖 9.18（ a）為歐拉圈，而圖 9.18（ b）則為歐拉路，后者雖可一筆 畫出，但必須以一個(gè)奇頂點(diǎn)為起點(diǎn)，以另一個(gè)奇頂為終點(diǎn)。 圖的連通性可以十分容易地用標(biāo)號(hào)算法加以檢驗(yàn)。而圖的奇頂點(diǎn)數(shù)又可 通過對(duì)其頂點(diǎn)一一檢測而求得。容易看出總計(jì)

32、算量是多頂式時(shí)間的，故 歐拉圈問題和歐拉路問題均是十分簡單的 P問題，從而，等價(jià)地，一筆畫 問題也可十分容易地求解：若圖 G是歐拉圖，則從任一頂點(diǎn)出發(fā)均可將它 一筆畫出；若圖 G是歐拉路，則由一奇頂點(diǎn)出發(fā)，一一經(jīng)偶頂點(diǎn)地走過各 條邊，最后到達(dá)另一奇頂點(diǎn)，即可將 G一筆畫出；否則 G不能一筆畫出， （當(dāng)然，如何走法仍需規(guī)劃一下）。 與歐拉圖有較大聯(lián)系的另一有名的 P問題是無向圖上的中國郵路問題。給 定一個(gè)無向圖，它的每一條邊上都賦有一個(gè)表示該邊長度（或費(fèi)用）的權(quán)。 要求從一指定頂點(diǎn)出發(fā)，至少經(jīng)過每一條邊一次最后返回原出發(fā)點(diǎn)，并使 經(jīng)過邊的總長度最小。其中如重復(fù)走過某些邊，則邊長應(yīng)重復(fù)計(jì)算，重復(fù)

33、幾次計(jì)算幾次。一個(gè)由郵局出發(fā)去各街道送信最后返回郵局的郵遞員遇到 的問題就是一個(gè)中國郵路問題。 無向圖上的中國郵路問題也不難解決。若無向圖 G是歐拉圖，則任一歐 拉圖都提供了一條最佳郵路。若 G不是歐拉圖，如前所說，圖中的奇頂 點(diǎn)數(shù)必為偶數(shù)。然后，求出任意兩個(gè)奇頂點(diǎn)之間的最短路徑及最短矩離 最短路徑長度），再解一個(gè)奇頂點(diǎn)之間的最小權(quán)匹配（或指派問題，注 意這里的距離矩陣是對(duì)稱的）。將各匹配奇點(diǎn)間的最短路徑加入 G中， 就得到了最知路問題的解，我們將在 9.5中考察一個(gè)這類問題的實(shí)例。 在本節(jié)中，我們例舉了幾個(gè)較為典型而又時(shí)常遇到的 P問題。由于事實(shí)上 存在著無窮多個(gè) P問題，而且即使某問題是

34、NP完全的，它的許多特殊條 件下的子問題也仍然可以是多項(xiàng)式時(shí)間可解的，因而我們不可能對(duì) P類作 一完整的介紹。如果本章內(nèi)容能起到拋磚引玉的作用，使讀者看到一些 P 問題所具有的某些特征及構(gòu)造算法上的某些技巧，那么，我們的目的也 就達(dá)到了。從上述 P問題（包括第八章中的線性規(guī)劃、運(yùn)輸問題及指派問 題）可以看出，它們都可以用某種逐次改進(jìn)的方法來求解。每次改進(jìn)中 的計(jì)算量是多項(xiàng)式界的，改進(jìn)的次數(shù)也是多項(xiàng)式界的。線性規(guī)劃的單純 形法例外，改進(jìn)次數(shù)可能達(dá)到指數(shù)次。但即使是線性規(guī)劃問題，也已經(jīng) 找到了具有這種特性的算法，如橢球算法、卡馬卡算法，雖然其結(jié)構(gòu)是 相當(dāng)復(fù)雜的，但計(jì)算量卻是多項(xiàng)式時(shí)間的。 最后，我

35、們還想強(qiáng)調(diào)幾點(diǎn)： 1、許多表面有點(diǎn)相象的問題事實(shí)上可能具有完全不同的計(jì)算復(fù)雜性。 這樣的例子舉不勝舉，我們略舉一、二，以提醒讀者注意。 （ 1）最短路徑問題是 P問題，而由一點(diǎn)出發(fā)到達(dá)每一頂點(diǎn)一次（不必返回 原點(diǎn)）的哈密頓路問題及由一頂點(diǎn)出發(fā)經(jīng)所有頂點(diǎn)一次到達(dá)另一頂點(diǎn)的最 短路徑問題 流浪的旅行商問題（ WTSP）均是 NP完全的。這里只增加 了每個(gè)頂點(diǎn)都要去一次的要求，但問題發(fā)生了質(zhì)的變化，由 P問題變成了 NP完全問題。 （ 2）指派問題與 TSP也有相似之處，前者求一置換而使目標(biāo)值最小，后者 求一循環(huán)置換（不包含子圈）而使目標(biāo)值最小。前者是 P問題，而后者則是 NP完全的。 （ 3）歐拉

36、圈問題求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過每邊一次回到原頂點(diǎn)的圈，而 TSP則求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過每個(gè)頂點(diǎn)一次返回原頂點(diǎn)的圈。前者是十 分容易的 P問題，而后者是極其困難的 NP完全問題，迄今還沒有求解它的較 好算法。 （ 4）線性規(guī)劃問題、運(yùn)輸問題及指派問題均為 P問題，但相應(yīng)的整數(shù)線性 規(guī)劃及 01規(guī)劃均為 NP完全的。 （ 5）無向圖中國郵路問題是 P問題，而有向圖中中國郵路問題則是 NP完 全的，（容易看出，會(huì)解有向圖上的某問題必也會(huì)解無向圖上的相同問題， 但反之不真）。 2、求最小的問題是 P問題，求最大的問題可以是 NP完全的，這樣的例子 也不少。例如，最短路徑問題是 P問題，而最長簡單路

37、徑（不含圈的路徑） 問題卻是 NP完全的。如若不然，我們可以利用它的有效算法如下構(gòu)造出 哈密頓問題的有效算：令圖 G=（ V， E）的所有邊的權(quán)均為 1，以一端點(diǎn) 為起點(diǎn)求到其余各頂點(diǎn)的最長簡單路徑。由于簡單路徑不含圈，所有頂 點(diǎn)均不會(huì)重復(fù)到達(dá)，故 G有哈密頓路當(dāng)且僅當(dāng)存在一起點(diǎn)及一終點(diǎn)，其最 長簡單路徑為 | V | 1。由于哈密頓路問題是 NP 完全的，故最長簡單路徑 問題的有效算法不可能存在，除非 P=NP。所以，如果你想設(shè)計(jì)一個(gè)求圖 上兩點(diǎn)間的最長簡單路徑的有效算法，不管你是多么努力，最終必將以 失敗告終。又譬如，網(wǎng)絡(luò)流中的最大流問題是 P問題。相應(yīng)地，最小切割 問題也是 P問題（它是

38、最大流問題的對(duì)偶問題，見線性規(guī)劃的對(duì)偶理論）。 但可以證明，最大切割問題卻是 NP完全的。 總之，在研究離散模型時(shí)應(yīng)當(dāng)極其小心。一方面，我們必須先搞清問題的 計(jì)算復(fù)雜性，而另一方面，條件的微小改變就有可能將一個(gè) P問題轉(zhuǎn)變?yōu)?NP完全的。當(dāng)然，相反的轉(zhuǎn)變也完全是可能的。 9.2 關(guān)于 NP完全性證明的幾個(gè)例子 上節(jié)介紹了幾個(gè) P問題及求解它們的算法。從某種意義上說，可以認(rèn)為這 些問題已被較好地解決了。然而，在研究離散問題時(shí)并非都能遇上這樣 的好運(yùn)。正如第八章所講，存在著大量具有 NP完全性的問題，雖然許多 人作了巨大的努力，仍未找到任何有效算法。其中的許多問題，例如 TSP， 甚至經(jīng)受了兩代數(shù)

39、學(xué)家的頑強(qiáng)攻擊，竟然毫無進(jìn)展。各種跡象使人們來 越來越傾向于相信，對(duì)這些問題根本不存在有效算法，自 1972年 Cook發(fā) 表那篇著名的論文以來，這些問題越來越多地被發(fā)現(xiàn)。因此，當(dāng)我們著 手研究一個(gè)離散問題時(shí)，不得不首先搞清遇到的會(huì)不會(huì)也是這樣一個(gè)問 題。有時(shí)，我們可以從有關(guān)書籍或文獻(xiàn)中查到它，因?yàn)閯e人早已對(duì)它作 過研究。例如可查閱 M.R.Garey和 D.S.Johnoson的著作“計(jì)算機(jī)和難解 性”，其中例舉了大量 NP完全問題。但這類問題事實(shí)上有無限多個(gè)，很 多時(shí)候，我們會(huì)遇到一些對(duì)其計(jì)算機(jī)復(fù)雜性一無所知的問題。這時(shí)，假 如我們?nèi)砸パ芯克?，首?dāng)其沖的問題就是搞清問題的性質(zhì)，以便保證

40、研究工作沿正確的途徑展開。要判定一個(gè)離散問題的性質(zhì)沒有一個(gè)固定 的程式可以沿用（雖然總是用多項(xiàng)式轉(zhuǎn)換的方法），常常要用到較高的 技巧，并要求對(duì)問題的組合結(jié)構(gòu)有相當(dāng)?shù)牧私?。盡管如此，別人的經(jīng)驗(yàn) 對(duì)我們?nèi)匀皇呛苡杏玫?。本?jié)將再分析一些問題，看看別人是如何判定 它們的 NP完全性的。 例 9.13 （獨(dú)立集問題） 給定圖 G=（ V， E），求 G的一個(gè)最大獨(dú)立集。 所謂獨(dú)立集是指 V的一個(gè)子集 ，有 1 , , , 1 ,kii s t k ( , )stii E 例 9.14 （復(fù)蓋問題） 給定圖 G=（ V， E），求 G的頂點(diǎn)的一個(gè)最小復(fù)蓋。 所謂復(fù)蓋是指 V的一個(gè)子集 C， ， u C或

41、C至少有一個(gè)成立。 ( , )uE 對(duì)于例 9.13和例 9.14，我們?yōu)閿⑹龇奖悖捎昧藞D的語言，其實(shí)也完全可 以將它們表達(dá)成其他方式。 定理 9.10 獨(dú)立集問題與點(diǎn)復(fù)蓋問題都是 NP完全的。 證明 稱圖 為圖 G的補(bǔ)集，若 與 G有相同的頂點(diǎn)集，且（ i,j）是 的 邊當(dāng)且僅當(dāng)它不是 G的邊。顯然，求 G的獨(dú)立集即求 的團(tuán)，由 G作出 可 在多項(xiàng)式時(shí)間內(nèi)完成，故獨(dú)立集問題等價(jià)于團(tuán)問題。而團(tuán)問題是 NP完全的 （見第八章六個(gè)基本 NP完全問題），故獨(dú)立集問題是 NP完全的。類似地， 容易證明 K是 G的團(tuán)當(dāng)且僅當(dāng) V K是 的復(fù)蓋，故點(diǎn)復(fù)蓋問題也是 NP完全 的。事實(shí)上，對(duì)任意 中的邊（

42、i,j），有（ i,j）不在 G中，故 i,j不能全 在 G的團(tuán) K中，從而 i與 j中至少有一個(gè)在 V K中，由邊（ i,j）的任意性可 知， V K中，由邊（ i,j）的任意性可知， V K 必為 的一個(gè)復(fù)蓋。 G G G G G G G G 前面已經(jīng)講過，哈密頓圈問題已被證明是 NP完全的，從而可得出 TSP是 NP 完全的，哈密頓問題是 NP完全的，進(jìn)而又可得出有向圖上的哈密頓圈、哈 密頓路和 TSP也是 NP完全的，因?yàn)橛脙蓷l具有相反方向的弧來代替每一條 邊，就可將一個(gè)無向圖上的問題轉(zhuǎn)化為一個(gè)有向圖上的問題，從而任一有 向圖問題的有效算法必能用來求解無向圖問題。 例 9.15 （背包

43、問題） 給定一組整數(shù) C=c1, cn以及一整數(shù) K，問是否存在 C的一個(gè)子集 S，使得 。 i icSCK 不難看出，背包問題是 NP完全的，因?yàn)槿羧?， 問題就化成了劃分問題。 1 1 2 n i i KC 例 9.15之所以被稱為背包問題是因?yàn)樗葍r(jià)于其優(yōu)化形式：以 K為“背包” 的容量，欲將 C中的整數(shù)裝入背包中，使背包中的各數(shù)之和盡可能地大 （求 C的子集 S，使 且盡可能大），即要求求解 0 1（線性）規(guī) 劃問題： i icSCK St xi0， xi1 xi為整數(shù) 1 m a x n ii i cx 1 n ii i c x K 例 9.16 （裝箱問題 Bin packing）

44、有一批待裝箱的物品 J=p1, pn， pj的長度為 l(pj)?，F(xiàn)有一批容量為 C的箱子（足夠數(shù)量）， 要求找到一種裝箱方法，使得所用的箱子數(shù)最少。 例 9.16是一個(gè)一維的裝箱問題。例如，我們有一批具有相同長度的鋼材，如 果想取出幾根已知長度的鋼料生產(chǎn)某種設(shè)備，當(dāng)然會(huì)希望少用幾根原始鋼材 以減少浪費(fèi)。此時(shí)，我們就遇到了一個(gè)一維的 Binpacking問題。當(dāng)我們想 從購買來的三夾板上鋸出 n塊已知長、寬的板來制作家具時(shí)，遇到的是二維 Binpacking問題。而當(dāng)我們真正想把一批已知長、寬、高的物體裝入具有 相同尺寸的箱子時(shí)，又遇到了三維的。下面的定理 告訴我們，即使是一維 的 Binpa

45、cking問題也是 NP完全的，故二維和三維的 Binpacking問題更 不可能是 P問題（它們也是 NP完全的）。 定理 9.11 （一維） Binpacking問題是 NP完全的。 證明： 易見，劃分問題可轉(zhuǎn)化為 Bin packing問題。事實(shí)上， 取 ， J=c1, cn可劃分為兩個(gè)相等的集合的充要條件是 它們可裝入兩只容量為 C的箱中。 1 1 2 n j j Cc 從某種意義上講， 3劃分問題（即分為三個(gè)相等子集的問題）也許比 2 劃分問題更難，因?yàn)橐呀?jīng)找到了求解 2劃分問題的一些較好算法（稱為 偽多項(xiàng)式時(shí)間算法）。但對(duì) 3劃分問題不可能存在類似算法，由于本書 篇幅有限，不再作詳

46、盡的討論。讀者不難發(fā)現(xiàn)， Binpacking問題至少不 會(huì)比 3劃分問題容易。順便指出， Binpackin問題中的臬子容量 C可以 取為 1，這樣的問題與例 9.16是等價(jià)的。 例 9.17 （排序問題 Scheduling） 擬用 m臺(tái)機(jī)器加工 n個(gè)零件，對(duì)零件的加 工可以提出各種不同的附加條件，希望排出一個(gè)加工順序（或時(shí)間表），使 在某種衡量標(biāo)準(zhǔn)下所求得的加工順序?yàn)樽罴选?Scheduling是一類應(yīng)用面極廣的離散問題，可以講它不是一個(gè)問題，而是一 類問題，因?yàn)椴煌臋C(jī)器環(huán)境、不同的加工要求或不同的衡量標(biāo)準(zhǔn)所得出的 模型是不同的。按目前流行的做法，人們常用三個(gè)參數(shù) ， ， 來描述一個(gè)

47、特定的排序問題，并記為 /排序問題，其中 描述機(jī)器情況， 描述加工零 件時(shí)的附加要求或附加條件， 表示衡量排序好壞的標(biāo)準(zhǔn)。按此方法分類， 有人作過統(tǒng)計(jì)，認(rèn)為至少有 9000多個(gè)不同的排序問題已被或多或少地研究過， 其中 76%為 NP完全的 ， 12%的為 P問題 ，余下的 12%目前還未搞清其計(jì)算 復(fù)雜性，但根據(jù)種種跡象 ，大部分可能是 NP完全的。有關(guān)排序問題，目前 已有十多本專著及至少數(shù)千篇論文，這里不準(zhǔn)備細(xì)述專業(yè)知識(shí)，僅以幾個(gè)排 序問題模型為例，來分析其計(jì)算復(fù)雜性。 Jm/ no wait /Cmax問題是 NP完全的。在這一模型中， =Jm， J代表一類被 稱為 Job shop的問

48、題， m表示有 m臺(tái)機(jī)器。 Job shop意指每一工件要在 m臺(tái) 機(jī)器的每一臺(tái)上加工（當(dāng)不需某臺(tái)加工時(shí)可令加工時(shí)間為零），且各工件 使用機(jī)器的順序可以不同。 =no wiat，表示任一工件在開始第一道工序加 工后不允許中間等待，直到它的各道加工均被完成。 =Cmax表示排序優(yōu)劣 的評(píng)價(jià)標(biāo)準(zhǔn)是全系統(tǒng)的加工時(shí)間最短，即由第一臺(tái)機(jī)器開始加工起到最后 一臺(tái)機(jī)器完工為止的時(shí)間跨度最小。第八章例 8.8（軋鋼問題）就是 Jm/no wait/Cmax排序問題的一個(gè)實(shí)例。在那里已經(jīng)證明了這一問題等價(jià)與 TSP， 從而是 NP完全的。 P2/Cmax問題是 NP完全。這里， =P2表示是一個(gè) 2臺(tái)機(jī)器的平行

49、機(jī)問題， 即有兩臺(tái)完全相同的機(jī)器，每一工件只需在其中任意一臺(tái)上加工一次即可。 =，表示工件加工沒有附加要求或條件。 =Cmax的解釋同上。容易看出， 這一問題至少不會(huì)比劃分問題容易，故不可能是 P問題。 在上面的例 9.13到例 9.17中，我們又列舉了幾個(gè) NP完全問題，它們的 NP完 全性證明都非常簡單。但一般地講，事情決非如此簡單，要將某一 NP完 全問題多項(xiàng)式時(shí)間轉(zhuǎn)化為我們要研究的問題，常常需要用到一些巧妙而又 精細(xì)的技巧。下面給出一個(gè)稍難一些的例子，供有興趣的讀者參考。 討論 1/rj, prmp/ 排序問題，我們將證明它是 NP完全的，這是一個(gè) 一臺(tái)機(jī)器的排序問題，待加工的工件 T

50、j有一個(gè)準(zhǔn)備時(shí)間 rj， rj0，僅當(dāng) trj時(shí) 它才能被加工。 prmp表示加工允許中斷以便先加工其他工件，未完成的加 工可在此后的某一時(shí)期補(bǔ)上。各工件的重要程度不同，對(duì)每一 Ti有一權(quán)因 子 wj。評(píng)判排序優(yōu)劣的標(biāo)準(zhǔn)為各工件完工時(shí)間 Cj的加權(quán)和 越小越好。 1 n jj j wC jjwC 這一問題很難直接利用前面提到過的那些 NP完全問題來證明其 NP完全性。 我們將用到下面的已被證明的 NP完全問題。 例 9.18 （三元?jiǎng)澐謫栴}） 給定 3t個(gè)正整數(shù)的集合 a1, a3t，令 ，問是否能將此集合劃分成兩兩不相交的 t個(gè)子集， 使得每一子集恰含總和為 b的三項(xiàng)，（標(biāo)準(zhǔn)型中可設(shè) ）。

51、3 1 1 t i i bat , 42ibbia 現(xiàn)在，我們來證明，對(duì)三元?jiǎng)澐謫栴}的每一實(shí)例，總可構(gòu)造出一個(gè)等價(jià)的 1/1/rj, prmp/ 排序問題的實(shí)例，（因此，會(huì)解后者就必會(huì)解前者）。 jjwC 對(duì)例 9.18給出的三元?jiǎng)澐謫栴}，作如下的 1/rj , prmp/ 排序問題實(shí)例， 該例中共有 4t 1項(xiàng)加工任務(wù)。相應(yīng)數(shù)據(jù)為 1 n jjj wC j=1,3 t，令 rj=0，需加工時(shí)間 Pj=aj, wj=1 j=3t+1,4 t 1，令 rj= (j 3t)(b+1) 1 Pj=1, wj=2 等價(jià)性證明可分以下幾步完成，有興趣的讀者可以自己完成它： （ 1）證明最后 t 1項(xiàng)工件

52、應(yīng)盡早加工，否則必將增大 ，因?yàn)樗鼈?的 wj=2，而前 3t項(xiàng)則有 wj=1。這樣，這 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)加工。除去加工這 t 1項(xiàng) 工件的時(shí)段，整個(gè)加工期還留下長度均為 b的 t個(gè)時(shí)段。 jjwC （ 2）若三元分劃問題有解，可利用每一時(shí)段加工一個(gè)子集中的工件，此 時(shí)不必中斷任何工件的加工，而 若三元分劃問題無解，則必有 Z Z是與排序無關(guān)的一個(gè)常數(shù)，而 =Z當(dāng)且僅當(dāng)三元?jiǎng)澐钟薪狻?13 ( 1 ) 3 / 2 1 )j j j k j K t w C a a t b Z j

53、jwC jjwC 9.3 分枝定界法與隱枚舉法（精確算法） 在上一章中我們已經(jīng)看到，整數(shù)規(guī)劃、 01規(guī)劃都是 NP完全的。事實(shí)上， 僅對(duì)部分變量有非負(fù)約束的線性規(guī)劃（稱為混合整數(shù)規(guī)劃）也是 NP完全 的。這樣，一方面不可能找到求解的有效算法，另一方面枚舉所有可能 情況的辦法對(duì)規(guī)模較大的例子又無法實(shí)現(xiàn)。出于實(shí)際需要，人們不得不 采取一些折中的辦法，即以枚舉為基礎(chǔ)，選用一些減少計(jì)算量的技巧或 規(guī)則，以增大算法的實(shí)用效果。前面已經(jīng)指出，所謂指數(shù)算法實(shí)際上是 指在最壞的情況下可能達(dá)指數(shù)時(shí)間的計(jì)算量，它并不排斥在大多數(shù)情況 下算法表現(xiàn)出好的性態(tài)。例如，求解線性規(guī)劃的單純形法從理論上講是 指數(shù)算法，但在實(shí)

54、際應(yīng)用時(shí)它又一般表現(xiàn)得出奇地好（已經(jīng)證明，其平 均計(jì)算量僅為 O(nlog2n)）。這一實(shí)例鼓舞人們?nèi)?duì)其余問題尋找類似的 算法。雖然迄今為止還沒有一個(gè) NP完全問題被發(fā)現(xiàn)具有類似單純形法那 樣漂亮的指數(shù)算法，這也許是由問題的 NP完全性本身決定的（注意：線 性規(guī)劃問題是 P問題，具有良好的組合結(jié)構(gòu)）。但人們的努力并沒有完全 白費(fèi)，有些 NP完全問題已有了一些在實(shí)際應(yīng)用時(shí)值得一試的求解算法。 我們將在本節(jié)舉幾個(gè)實(shí)例來介紹這類算法。 一、分枝定界法 例 9.19 某房屋出租單位有活動(dòng)資金 91萬元，擬購房出租，現(xiàn)有兩種房屋， 一種每套 13萬元，只有四套；另一種每套 18.2萬元，數(shù)量不限。該單

55、位每月 可用于照料租房的工時(shí)總計(jì)為 140 小時(shí)，第一種房每套每月需照料 4小時(shí)， 第二種房每套每月需照料 40小時(shí)。第一種房月租金收入為 2000元，第二種 房月租金收入為 3000元。問此單位應(yīng)購兩種房各多少套才能使總收入最大 建模 設(shè) x1、 x2分別為購買兩種房的套數(shù)，顯然 x1、 x2必須為整數(shù)，故要求 求解整數(shù)規(guī)劃（ ILP） max 0.2 x1 + 0.3x2 S.t 13x1 + 18.2x291 4 x1 + 40 x2140 x14 x1、 x20且為整數(shù) 解 ： 先不考慮整數(shù)要求，求解與上述整數(shù)規(guī)劃（ ILP）相應(yīng)的線性規(guī)劃 LP0（稱之為與（ ILP）相應(yīng)的松馳線性規(guī)

56、劃），解得 x1=2.44， x2=3.26， maxZ=1.466萬元。 分析： 若將變量四舍五入化整，雖滿足了變量的整數(shù)要求，但一方面得 到的有可能不是可行解，另一方面即使得到的是可行解，也不能保證它 是最優(yōu)解。有人曾構(gòu)造出一個(gè)實(shí)例，其最優(yōu)解有一百多萬種四舍五入的 可能情況，但得到的均非可行解。對(duì)本例，因只有兩個(gè)變量，共有四種 可能，即化整為（ 2,3），（ 2,4），（ 3,3），（ 3,4），其中只有 x1=2， x2=3是可行的，目標(biāo)值為 Z=1.3萬元，并非最優(yōu)解（最優(yōu)解為 x1=4， x2=2， Z*=1.4萬元）。不難看出，對(duì)只有兩個(gè)變量的問題都不能通過化整的辦法 來求得最優(yōu)解

57、，對(duì)變量數(shù)較多的實(shí)例，情況將更為復(fù)雜。 求解松馳線性規(guī)劃雖無法找出最優(yōu)整數(shù)解，但卻指出了該實(shí)例目標(biāo)函數(shù)值 的一個(gè)下界（指標(biāo)準(zhǔn)型 min問題）。在本實(shí)例中，由于問題是求目標(biāo)值最 大的，我們可以看出，既然不考慮整約束時(shí)的最優(yōu)目標(biāo)值為 1.466 萬，則 （ ILP）的最優(yōu)目標(biāo)值不可能超過 1.466萬，從而我們知道了最優(yōu)目標(biāo)值的 一個(gè)上界。 下面介紹一種分枝定界技巧 從（ ILP）的松馳線性規(guī)劃的最優(yōu)解中選取一個(gè)非整分量（通常選離整數(shù) 最遠(yuǎn)的分量），例如我們選取 x1，考察兩個(gè)新的松馳線性規(guī)劃。 （ LP1） max 0.2 x1 + 0.3x2 S.t 13x1 + 18.2x291 4 x1

58、+ 40 x2140 x12 x1、 x20且為整數(shù) （ LP2） max 0.2 x1 + 0.3x2 S.t 13x1 + 18.2x291 4 x1 + 40 x2140 x13 x14 x1、 x20且為整數(shù) 可以看出，（ ILP）的最優(yōu)解必在（ LP1）與（ LP2）的可行域之一中， 但（ LP0）的最優(yōu)解 （ 2.44,3.26）已不在（ LP1）與（ LP2）的可行域中 （這正是分枝的目的）。 （ LP1）的最優(yōu)解為（ 2， 3.3），最優(yōu)目標(biāo)值為 1.39萬元，其可行域中不包 含具有更大目標(biāo)值的可行解，（ LP2）的最優(yōu)解為（ 3,2.86），最優(yōu)目標(biāo)值 為 1.458萬元。

59、由于（ LP1）與（ LP2）的最優(yōu)解均非整數(shù)解，還需繼續(xù)搜索，現(xiàn)選取最優(yōu) 目標(biāo)值最大的（ LP2）進(jìn)行分枝，即增加約束 x22作子問題（ LP3），增加 約束 x23作子問題（ LP4）。 （ LP4）無可行解，（ LP3）有最優(yōu)解（ 4, 2）， 該分枝的最優(yōu)目標(biāo)值 Z=1.4。于是，對(duì) x13的分枝（ LP2），我們已求得最 優(yōu)解（注（ LP1）已不必再求解）目標(biāo)值的一個(gè)上界（ UB） Z=1.4。另一方 面，又同時(shí) 求得一整數(shù)解其目標(biāo)值 Z=1.4，故已有整數(shù)最優(yōu)解目標(biāo)值的一個(gè) 下界（ LB） Z=1.4 至此，我們已運(yùn)用分枝定界法求得了整數(shù)規(guī)劃例 9.19的最優(yōu)解，整個(gè)過程 見圖 9

60、.18所示。讀者不難看出算法的實(shí)質(zhì)，并由此總結(jié)出算法。 為了讓讀者看清在各種不同類型的問題中是如何使用分枝定界法的，下面 我們?cè)倥e一例： 例 9.20 要調(diào)配紅、藍(lán)、白、黑、黃五種顏色的油漆。清洗調(diào)配工具所需花 費(fèi)的時(shí)間既和原來調(diào)配什么顏色有關(guān)又和擬調(diào)配什么顏色有關(guān)，各種情況 下所需的時(shí)間見表 9.3所示。問應(yīng)當(dāng)如何調(diào)配較好（要求先建立模型）。 對(duì)例 9.20我們作如下理解，一個(gè)油漆工每天都要使用上述五種顏料，從而 他應(yīng)當(dāng)在完成工作后清洗好工具，以便第二天開始同樣順序的調(diào)色。如 果該工人只需調(diào)配一次而不必考慮以后的工作，問題可以作類似的討論， （注：此工人只有一塊調(diào)色板）。 表 9.3 現(xiàn)調(diào)

61、原調(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)的費(fèi)用矩陣為 6 18 4 8 7 17 3 7 4 5 4 5 20 19 24 22 8 8 16 6 M M M M M 紅 藍(lán) 白 黑 黃 紅 蘭 白 黑 黃 其中，“ M”表示充分大的正實(shí)數(shù)。 利用求解指派問題的匈牙利算法，對(duì)矩陣逐次變換如下： 6 18 4 8 7 17 3 7 4 5 4 5 20 19 24 22 8 8 16 6

62、M M M M M 4 2 14 0 4 3 4 14 0 4 4 0 1 0 1 19 1 0 5 3 6 2 2 10 0 5 1 M M M M M 2 9 0 3 4 9 0 3 2 0 1 0 0 2 1 0 0 2 2 2 5 0 M M M M M 0 7 0 1 2 7 0 1 0 1 2 0 1 0 0 2 0 0 3 0 M M M M M 在變換過程中， M的值可能改變，它們均表示充分大的正整數(shù)，為簡便 起見，不妨仍用 M表示。從最后一個(gè)矩陣立即可得此調(diào)色問題的一個(gè)最 優(yōu)順序：紅 藍(lán) 黑 白 黃（黃 紅）。 讀者不難發(fā)現(xiàn)，利用指派問題的算法求得調(diào)色問題例 2的解純系巧合。

63、事 實(shí)上，調(diào)色問題可看成旅行商問題的實(shí)例。 TSP是 NP完全的，而求解指 派問題的匈牙利算法是多項(xiàng)式時(shí)間算法，不可能用來求解 TSP的每一實(shí) 例。例如，如果將例 9.20的費(fèi)用矩陣改為 1 2 3 4 5 1 4 8 6 8 4 2 5 7 11 13 5 3 11 6 8 4 4 4 5 7 2 2 2 5 10 9 7 5 5 M M A M M M ____________ 共計(jì)減 20 1 2 3 4 5 1 1 0 4 2 4 2 0 2 6 8 3 7 2 4 0 4 3 5 0 0 5 5 4 2 0 M M A M M M 相應(yīng)的指派 1 2， 3 5 4不構(gòu)成一個(gè)旅行回路（

64、哈密頓圈），它含有兩 個(gè)子圈（ 1,2）和（ 3,5,4）。 一般地，調(diào)色問題（即 TSP的實(shí)例）可試用分枝定界法求解。如對(duì)長陣 A，由 于從其相應(yīng)的等價(jià)問題矩陣 A1中可找到費(fèi)用為 0的最優(yōu)指派，故可知 20是其總 費(fèi)用的一個(gè)下界。現(xiàn)作如下兩個(gè)分枝：（ 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 2 2 0 0 3 2 4 0 0 4 0 4 5 0 0 3 0 0 5 4 2 0 2 2 0 M M M

65、 M M M M M M M M M M M M M M M M M M M M M 2 （累計(jì)減 24新下界） 此時(shí)又可作如下分枝： （情況 1）?。?14） 0 0 00 00 2 2 2 M M M M MMMM M M M M M M M M M （累計(jì)減 26新下界） （情況 2）不取（ 14）（簡記為（ 14） 2 022 003 040 0 22 MM MM MM MMMM MMM （累計(jì)減 26 新下界） 情況 1中位于第四行第二列的元素改為 M是因?yàn)榇藭r(shí)不能取 4 2,否則將含 子圈（ 1， 4， 2）。 兩種情況又可分別變換為 （情況 1）取（ 14） MMM MMM MM

66、M MMMM MMMM 00 00 00 0 0 求得（ 1， 4， 5， 3， 2） （情況 2）（ 14） MM M MMM MMMM MM 222 0003 00 0 000 求得（ 1， 4， 5， 3， 2） 兩個(gè)旅行圈的費(fèi)用均為 26（指在原問題中）。 （ 2）不取 2 1，將矩陣 A1改寫為 M M M MM M M M M MM M 0242 0050 0424 640 4240 2 0242 0053 0427 862 4240 -3 累計(jì)減 25 求得（ 1， 2， 3， 5， 4） 比較各分枝，求得原問題的最優(yōu)解（ 1， 2， 3， 5， 4），最優(yōu)目標(biāo)值為 25， 如圖 9.20所示。 需要指出的是，雖然在上面的實(shí)例中計(jì) 算量并不是很大，但對(duì)于 n較大的實(shí)例， 用以上介紹的分枝定界法求解旅行商問 題效果并不理想，如何構(gòu)造實(shí)用效果更 好的分枝定界算法仍然是一個(gè)值得進(jìn)一 步研究的問題。 二、隱枚舉法 現(xiàn)考察 0-1規(guī)劃的一個(gè)實(shí)例： 例： 9.21 試求解 0-1規(guī)劃： S.t 約束條件（ 1） 約束條件（ 2） 約束條件（ 3） 或 1 321 523m a x x