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

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

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

2、類。一方面，很多 P問題象線性規(guī)劃一樣有 著極廣泛的應(yīng)用前景，且它們本身又是十分有趣的；另一方面，它們也 是研究一些更為復(fù)雜、難解的問題時經(jīng)常被采用的研究工具。在本章中， 將再介紹一些經(jīng)常遇到的 P問題并給出求解它們的有效算法。 一、擬陣問題及貪婪算法 在 P類中又存在著一個被稱為擬陣的具有更為良好性質(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ú)的一個點(diǎn)也可看成一顆 樹。樹用 (U， T)表示， U為樹的頂點(diǎn)， T為樹的邊集。不相交的樹的集合 被稱為森林。一個連通圖的生成樹是指圖中具有最多邊數(shù)的一棵樹。容 易證明，對于一個連通圖 G， G 的任一生成樹必有 V -1條邊。 求解最小生成樹的算法主要依據(jù)下面的定理： 定理 9.1 設(shè) （ V1， T1）， （ Vk ,Tk） 為連通圖 G中的森林， V1 U V2U Vk=V。 k,若僅有一個頂點(diǎn)在 Vi中的具有最小權(quán)的邊為（ ,u）， 則必有一棵 G的最小生成樹包含邊（ ,u）。 ,1i 根據(jù)

4、定 1可以作了如下算法：任選一點(diǎn) ，令 若 V1=V，停；否則，找出僅有一個頂點(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)號 1，先加入 （因?yàn)檫厵?quán) 最?。?標(biāo)號 2。再加入 標(biāo)號 3。 ，每次加入一條一頂點(diǎn)已標(biāo) 號加一頂點(diǎn)未標(biāo)號而又具有最小權(quán)的邊，直到所有頂點(diǎn)均標(biāo)號為止。找 到的最小生成樹已用又線標(biāo)在圖 9.2中。 1 1 1,V 2 12 2 44 容易看出算法的計算量為 O (V)2 ，所以此算法是有效算法，若 G具有 O（ ）條邊，其中 n= V ，計算量的界還是不能改進(jìn)的，因?yàn)槊織l 邊至少應(yīng)被檢查一次。 2nC 由例 9.2可以看出，算法執(zhí)行的每一步均加入一條可以加入的（即不

6、生成 圈的）具有最小權(quán)的邊，而不去考慮它對以后選取的影響，這種算法被 稱為貪婪算法。 例 9.3 (入樹問題 ) 給出一個有向圖 G=（ V， A），對 A中的每一條孤 e，給 出一個權(quán) C（ e），求 A的一個具有最大權(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)的孤，故對每一頂點(diǎn) 只能選 取一條入孤。為使選出的弧具有最大權(quán)，只需要對每一頂點(diǎn)選取權(quán)最大 的入孤，可用計算量為 O（ V E ）的貪婪法

7、求解，具有最大權(quán)的 入樹為 。 i 1 2 2 1 2 4 4 5 5 3, , , , , , , , , 類似地，出樹問題也可以用貪婪法求解。 例 9.5 (矩陣擬陣問題 )給出一個矩陣 Amxn，記其 n個列向量為 e1, ， en。 設(shè)對每一列向量 en已指定一權(quán) C（ en）求 的一個線性無 關(guān)的子集，它具有最大的權(quán)和。 1, ,i in 易見，這一問題也可以用貪婪法求解。集合 的線性無關(guān)的 子集被稱為獨(dú)立子集，利用貪婪法必可求得具有最大權(quán)的獨(dú)立子集，可用 線性代數(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，同時對 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是一個有限集， 為 E的部分子集構(gòu)成的封閉系統(tǒng)（即 若 ，則必有 ）。若 M=（ E， ）上的離散優(yōu)化問題的每一 實(shí)例均可用貪婪算法求出最優(yōu)解，則稱 M為一擬陣。（注： 被稱為獨(dú)立系 統(tǒng)）。 ,AA A 現(xiàn)以矩陣擬陣為例，對定義 9.1作一說明。 對矩陣擬陣的每一實(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)） 有一個明顯而又本質(zhì)的特性，其任一極大獨(dú)立 子集中包含著相同個數(shù)的元素，從而可以引入基的概念。例如，矩陣列向 量的所有線性無關(guān)極大組均具有相同的向量個數(shù)，這就導(dǎo)出了基 即矩 陣列秩的概念。對于圖擬陣，每一極大獨(dú)立集均為一生成樹，其邊數(shù)均為 |V|-1。對于劃分?jǐn)M陣，孤集被劃分成個 |V|個子集，每一子集由指向同一 頂點(diǎn)的孤組成。顯然，任一極大獨(dú)立集應(yīng)在每一子集中取一條孤，故其基 數(shù)為頂點(diǎn)個數(shù)。 我們不加證明地引入下面的定理，雖然其證明并不十分困難。 定理 9.2 E為一有限集合

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

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

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á)到最大，易見，這是一個線性規(guī)劃問題的子問題，故 類。 P tiv tsi siv jiji Aiji Aiji 若 若 若 .0)

14、,(),( ),( ),( 對于一個較為復(fù)雜的網(wǎng)絡(luò)，要想直接找出最大流是不太可能的。為了簡 化問題，我們先引入一些符號。 記 、 為 的兩個不相交的子集， 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)集合 的一個真子集， 為 關(guān)于 的補(bǔ)集。若 、 滿足 且 則稱 和 為的一個切割。 P P SP tP P 根據(jù)切割的定義可以看出，當(dāng)和 為一切割時，如果去掉連接 和的 邊集（ ， ），就切斷了由通往 t的所有通路。所以，

15、對網(wǎng)絡(luò)的任一 切割（ ， ）， （ ， ）必為最大流的一個上界， 而 。 P P P P ,P P P P 例 9.9 網(wǎng)絡(luò)如圖 9.6所示，邊（?。┥系膬蓴?shù)字分別表示邊容量及實(shí)際流 量。取，則，顯然 、 是網(wǎng)絡(luò) 的一個切割。對于這一切割容易算出 而網(wǎng)絡(luò)的流量 。 P , 6 , , 9P P C P P 為了盡可能地增大網(wǎng)絡(luò)上的流量，按如下方法作出一個和 具有相同頂 點(diǎn)并具有相同發(fā)點(diǎn)和收點(diǎn)的增廣網(wǎng)絡(luò) （ ） （簡記 ）。 包含 兩類邊，對中每一條邊（ 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，而在對應(yīng) 增廣邊（ j, i）， G的邊（ i, j）上減少流量 a，就得到 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 增廣路可以通過對頂點(diǎn)標(biāo)號的方法來尋找。由于邊容量均為整數(shù)，而每次 經(jīng)改進(jìn)，流量至少增加一，故算法總能很快求

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

20、依次為容量和邊上的實(shí)際流量。有時候，當(dāng)流流經(jīng)一條邊 時需支付一定的費(fèi)用，我們不僅希望找出一個最大流，而且希望找出的最 大流在具有相同流量的流中具有最小的總費(fèi)用，這時問題可描述為：對有 向圖 G=（ V， A）的每條邊（?。?i, j）給定一個邊容量 C（ i, j）及一個 單位流量費(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ù)量貨物時，我們希望總距離或總運(yùn)費(fèi)最

21、小?，F(xiàn)在，我們將以最大 流問題的增廣路算法為基礎(chǔ)，導(dǎo)出求解最小費(fèi)用最大流問題的算法。 對于網(wǎng)絡(luò)上的一個現(xiàn)行流 ，作出其增廣網(wǎng)絡(luò) G( )，對 G中的正規(guī)邊 賦值 l(i, j)，對 G中的增廣邊 (i, j)則賦值 l(i, j)。 定義 9.6 增廣網(wǎng)絡(luò) G上由 s到 t的流量為零但邊流量不全為零的流稱為一個循環(huán)流。 最小費(fèi)用最大流問題可以變換成為一個線性規(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上的一個可行流，其中弧上的三個數(shù) 字分別

22、為容量、單位流費(fèi)用及實(shí)際流量。圖 9.10（ b）為相應(yīng)的增廣網(wǎng)絡(luò)， 其中邊（?。┥系膬蓚€數(shù)字分別為容量及單位流費(fèi)用。求此網(wǎng)絡(luò)的一個更 小費(fèi)用流。 從圖 9.10（ b）中可以找出一個負(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)流，它是一個最小 費(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，求最大流的算法只需稍作 變動即可用來求解最小費(fèi)用

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

25、，以此數(shù) 減每邊原有的財禮費(fèi)，并用此差為各邊的費(fèi)用，得一最小費(fèi)用最大流問 題（未注數(shù)字的邊費(fèi)用均為零），其網(wǎng)絡(luò)圖見圖 9.13。此問題在使用三 次增廣路后可求得最佳結(jié)果。 P 四、最短路徑問題 最短路徑問題是又一個經(jīng)常遇到的 P問題，它在工藝流程的安排、管道或 網(wǎng)絡(luò)的鋪設(shè)、設(shè)備更新等實(shí)際生產(chǎn)中常被用到，是網(wǎng)絡(luò)規(guī)劃的基本問題 之一。顧名思義，最短路徑求的是以下問題：給定一個網(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)了動態(tài)規(guī)劃

26、算法的基本思想。若點(diǎn) P在 A到 E的最短路上，則 P到 E的最短路徑必整個地包含在 A到 E的最短路 徑上。因?yàn)?，若不然，將?P到 E的最短路徑導(dǎo)出 A到 E的更短路徑，從而 導(dǎo)出矛盾。算法既可以通過對頂點(diǎn)逐次標(biāo)號來實(shí)現(xiàn)，也可以通過矩陣運(yùn) 算進(jìn)行。在使用標(biāo)號法時，既可以從起點(diǎn)開始標(biāo)，也可以從終點(diǎn)開始標(biāo)。 （兩者目的略有不同）對例 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)時，先找出離已標(biāo)號頂點(diǎn)最近的頂 點(diǎn)。比較各已標(biāo)號頂點(diǎn)（與擬標(biāo)號頂點(diǎn)有邊相連）的標(biāo)號與它到擬標(biāo)

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

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

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

30、 4 5 價格（萬年） 10 10 11 12 13 已使用年數(shù) 0 1 2 3 4 （萬年） 4 8 11 15 20 五、歐拉圈與最短郵路問題 歐拉圈問題起源于著名的七橋問題。給定一個無向圖 G=（ V， E），問能 否由一個頂點(diǎn)出發(fā)，經(jīng)且僅經(jīng)過每條邊一次并返回原出發(fā)頂點(diǎn)。如果能夠， 則每一個這樣的圈被稱為圖 G的歐拉圈，而圖 G則被稱為是一個歐拉圖。 顯然，圖 G為歐拉圖的充要條件是它可以被一筆畫出且首尾相連（當(dāng)首尾 不能相連時則被稱為歐拉路）。由此，立即可得出下面的定理： 定理 9.8 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)的個數(shù)必為偶數(shù)個（因?yàn)槊恳还P畫都產(chǎn)生一個起點(diǎn)與 一個終點(diǎn)），又易得出 定理 9.9 G為歐拉路的充要條件為： G是連通的且奇頂點(diǎn)的個數(shù)為 2。 綜合定理 9.8和定理 9.9可知， G可一筆畫出的充要條件為 G是連通的且奇頂 點(diǎn)的個數(shù)為 0或 2，當(dāng)奇頂點(diǎn)個數(shù)為零時，尚可設(shè)法使起點(diǎn)和終點(diǎn)相重。 下面的圖 9.18（ a）為歐拉圈，而圖 9.18（ b）則為歐拉路，后者雖可一筆 畫出，但必須以一個奇頂點(diǎn)為起點(diǎn)，以另一個奇頂為終點(diǎn)。 圖的連通性可以十分容易地用標(biāo)號算法加以檢驗(yàn)。而圖的奇頂點(diǎn)數(shù)又可 通過對其頂點(diǎn)一一檢測而求得。容易看出總計

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

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

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

35、們還想強(qiáng)調(diào)幾點(diǎn)： 1、許多表面有點(diǎn)相象的問題事實(shí)上可能具有完全不同的計算復(fù)雜性。 這樣的例子舉不勝舉，我們略舉一、二，以提醒讀者注意。 （ 1）最短路徑問題是 P問題，而由一點(diǎn)出發(fā)到達(dá)每一頂點(diǎn)一次（不必返回 原點(diǎn)）的哈密頓路問題及由一頂點(diǎn)出發(fā)經(jīng)所有頂點(diǎn)一次到達(dá)另一頂點(diǎn)的最 短路徑問題 流浪的旅行商問題（ WTSP）均是 NP完全的。這里只增加 了每個頂點(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)過每個頂點(diǎn)一次返回原頂點(diǎn)的圈。前者是十 分容易的 P問題，而后者是極其困難的 NP完全問題，迄今還沒有求解它的較 好算法。 （ 4）線性規(guī)劃問題、運(yùn)輸問題及指派問題均為 P問題，但相應(yīng)的整數(shù)線性 規(guī)劃及 01規(guī)劃均為 NP完全的。 （ 5）無向圖中國郵路問題是 P問題，而有向圖中中國郵路問題則是 NP完 全的，（容易看出，會解有向圖上的某問題必也會解無向圖上的相同問題， 但反之不真）。 2、求最小的問題是 P問題，求最大的問題可以是 NP完全的，這樣的例子 也不少。例如，最短路徑問題是 P問題，而最長簡單路

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

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

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

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

41、C至少有一個成立。 ( , )uE 對于例 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)式時間內(nèi)完成，故獨(dú)立集問題等價于團(tuán)問題。而團(tuán)問題是 NP完全的 （見第八章六個基本 NP完全問題），故獨(dú)立集問題是 NP完全的。類似地， 容易證明 K是 G的團(tuán)當(dāng)且僅當(dāng) V K是 的復(fù)蓋，故點(diǎn)復(fù)蓋問題也是 NP完全 的。事實(shí)上，對任意 中的邊（

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

43、問題） 給定一組整數(shù) C=c1, cn以及一整數(shù) K，問是否存在 C的一個子集 S，使得 。 i icSCK 不難看出，背包問題是 NP完全的，因?yàn)槿羧?， 問題就化成了劃分問題。 1 1 2 n i i KC 例 9.15之所以被稱為背包問題是因?yàn)樗葍r于其優(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是一個一維的裝箱問題。例如，我們有一批具有相同長度的鋼材，如 果想取出幾根已知長度的鋼料生產(chǎn)某種設(shè)備，當(dāng)然會希望少用幾根原始鋼材 以減少浪費(fèi)。此時，我們就遇到了一個一維的 Binpacking問題。當(dāng)我們想 從購買來的三夾板上鋸出 n塊已知長、寬的板來制作家具時，遇到的是二維 Binpacking問題。而當(dāng)我們真正想把一批已知長、寬、高的物體裝入具有 相同尺寸的箱子時，又遇到了三維的。下面的定理 告訴我們，即使是一維 的 Binpa

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

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

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

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

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

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

51、3 1 1 t i i bat , 42ibbia 現(xiàn)在，我們來證明，對三元劃分問題的每一實(shí)例，總可構(gòu)造出一個等價的 1/1/rj, prmp/ 排序問題的實(shí)例，（因此，會解后者就必會解前者）。 jjwC 對例 9.18給出的三元劃分問題，作如下的 1/rj , prmp/ 排序問題實(shí)例， 該例中共有 4t 1項(xiàng)加工任務(wù)。相應(yīng)數(shù)據(jù)為 1 n jjj wC j=1,3 t，令 rj=0，需加工時間 Pj=aj, wj=1 j=3t+1,4 t 1，令 rj= (j 3t)(b+1) 1 Pj=1, wj=2 等價性證明可分以下幾步完成，有興趣的讀者可以自己完成它： （ 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時段內(nèi)加工。除去加工這 t 1項(xiàng) 工件的時段，整個加工期還留下長度均為 b的 t個時段。 jjwC （ 2）若三元分劃問題有解，可利用每一時段加工一個子集中的工件，此 時不必中斷任何工件的加工，而 若三元分劃問題無解，則必有 Z Z是與排序無關(guān)的一個常數(shù)，而 =Z當(dāng)且僅當(dā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í)上， 僅對部分變量有非負(fù)約束的線性規(guī)劃（稱為混合整數(shù)規(guī)劃）也是 NP完全 的。這樣，一方面不可能找到求解的有效算法，另一方面枚舉所有可能 情況的辦法對規(guī)模較大的例子又無法實(shí)現(xiàn)。出于實(shí)際需要，人們不得不 采取一些折中的辦法，即以枚舉為基礎(chǔ)，選用一些減少計算量的技巧或 規(guī)則，以增大算法的實(shí)用效果。前面已經(jīng)指出，所謂指數(shù)算法實(shí)際上是 指在最壞的情況下可能達(dá)指數(shù)時間的計算量，它并不排斥在大多數(shù)情況 下算法表現(xiàn)出好的性態(tài)。例如，求解線性規(guī)劃的單純形法從理論上講是 指數(shù)算法，但在實(shí)

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

55、位每月 可用于照料租房的工時總計為 140 小時，第一種房每套每月需照料 4小時， 第二種房每套每月需照料 40小時。第一種房月租金收入為 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)造出一個實(shí)例，其最優(yōu)解有一百多萬種四舍五入的 可能情況，但得到的均非可行解。對本例，因只有兩個變量，共有四種 可能，即化整為（ 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萬元）。不難看出，對只有兩個變量的問題都不能通過化整的辦法 來求得最優(yōu)解

57、，對變量數(shù)較多的實(shí)例，情況將更為復(fù)雜。 求解松馳線性規(guī)劃雖無法找出最優(yōu)整數(shù)解，但卻指出了該實(shí)例目標(biāo)函數(shù)值 的一個下界（指標(biāo)準(zhǔn)型 min問題）。在本實(shí)例中，由于問題是求目標(biāo)值最 大的，我們可以看出，既然不考慮整約束時的最優(yōu)目標(biāo)值為 1.466 萬，則 （ ILP）的最優(yōu)目標(biāo)值不可能超過 1.466萬，從而我們知道了最優(yōu)目標(biāo)值的 一個上界。 下面介紹一種分枝定界技巧 從（ ILP）的松馳線性規(guī)劃的最優(yōu)解中選取一個非整分量（通常選離整數(shù) 最遠(yuǎn)的分量），例如我們選取 x1，考察兩個新的松馳線性規(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。于是，對 x13的分枝（ LP2），我們已求得最 優(yōu)解（注（ LP1）已不必再求解）目標(biāo)值的一個上界（ UB） Z=1.4。另一方 面，又同時 求得一整數(shù)解其目標(biāo)值 Z=1.4，故已有整數(shù)最優(yōu)解目標(biāo)值的一個 下界（ LB） Z=1.4 至此，我們已運(yùn)用分枝定界法求得了整數(shù)規(guī)劃例 9.19的最優(yōu)解，整個過程 見圖 9

60、.18所示。讀者不難看出算法的實(shí)質(zhì)，并由此總結(jié)出算法。 為了讓讀者看清在各種不同類型的問題中是如何使用分枝定界法的，下面 我們再舉一例： 例 9.20 要調(diào)配紅、藍(lán)、白、黑、黃五種顏色的油漆。清洗調(diào)配工具所需花 費(fèi)的時間既和原來調(diào)配什么顏色有關(guān)又和擬調(diào)配什么顏色有關(guān)，各種情況 下所需的時間見表 9.3所示。問應(yīng)當(dāng)如何調(diào)配較好（要求先建立模型）。 對例 9.20我們作如下理解，一個油漆工每天都要使用上述五種顏料，從而 他應(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ù)。 利用求解指派問題的匈牙利算法，對矩陣逐次變換如下： 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表示。從最后一個矩陣立即可得此調(diào)色問題的一個最 優(yōu)順序：紅 藍(lán) 黑 白 黃（黃 紅）。 讀者不難發(fā)現(xiàn)，利用指派問題的算法求得調(diào)色問題例 2的解純系巧合。

63、事 實(shí)上，調(diào)色問題可看成旅行商問題的實(shí)例。 TSP是 NP完全的，而求解指 派問題的匈牙利算法是多項(xiàng)式時間算法，不可能用來求解 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 _ 共計減 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)成一個旅行回路（哈密頓圈），它含有兩

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

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

66、 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） 兩個旅行圈的費(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 累計減 25 求得（ 1， 2， 3， 5， 4） 比較各分枝，求得原問題的最優(yōu)解（ 1， 2， 3， 5， 4），最優(yōu)目標(biāo)值為 25， 如圖 9.20所示。 需要指出的是，雖然在上面的實(shí)例中計 算量并不是很大，但對于 n較大的實(shí)例， 用以上介紹的分枝定界法求解旅行商問 題效果并不理想，如何構(gòu)造實(shí)用效果更 好的分枝定界算法仍然是一個值得進(jìn)一 步研究的問題。 二、隱枚舉法 現(xiàn)考察 0-1規(guī)劃的一個實(shí)例： 例： 9.21 試求解 0-1規(guī)劃： S.t 約束條件（ 1） 約束條件（ 2） 約束條件（ 3） 或 1 321 523m a x x