【正文】 矩陣列秩的概念。由于 E的任一線性無(wú)關(guān)子集的子集也是 E的線性無(wú)關(guān)子集，故獨(dú)立系統(tǒng) γ是封閉的。 ,39。 ? ? ? ?1 , ,i in?例 求矩陣 A的列向量具有最大權(quán)和的獨(dú)立子集 7*45762101543100012731214531011?????????????AC(ei)＝ 8 4 7 5 2 6 4 解： 采用貪婪法，先取權(quán)最大的列 e1，同時(shí)對(duì) A作高斯消去，逐次加入 線性無(wú)關(guān)的向量： A的列向量中具有最大權(quán)的獨(dú)立子集為 。 例 (矩陣擬陣問(wèn)題 )給出一個(gè)矩陣 Amxn，記其 n個(gè)列向量為 e1,… ， en。 考察下面的入樹(shù)問(wèn)題實(shí)例： 例 給出有向圖 G=（ V， A） （圖 ） ，孤上標(biāo)出的數(shù)字為該邊的 權(quán)，求此圖具有最大權(quán)的入樹(shù)。找到的最小生成樹(shù)已用又線標(biāo)在圖 。 解 ： 不妨從頂點(diǎn)開(kāi)始尋找。39。 39。將（ ,u）加入 T，由于（ V， T）是生成樹(shù)， T U（ ,u）中含有過(guò)（ ,u）的唯一的圈。 … k,若僅有一個(gè)頂點(diǎn)在 Vi中的具有最小權(quán)的邊為（ ,u），則必有一棵 G的最小生成樹(shù)包含邊（ ,u）。不相交的樹(shù)的集合被稱為森林。 例 （最小生成樹(shù)問(wèn)題 ——MST） 給定一連通圖 G=（ V， E）， ，有一表示邊長(zhǎng)的權(quán) C（ e）（表示頂點(diǎn)間的距離或費(fèi)用），求此圖的具有最小總權(quán)的生成樹(shù)。雖然從平均的角度講，人們似乎更常遇到 NP完全問(wèn)題，但 P仍不失為一個(gè)十分重要的問(wèn)題類。從這一點(diǎn)上講， P問(wèn)題可以看成是一類具有良好性質(zhì)而又較容易求解的問(wèn)題，而 NP完全問(wèn)題則是固有地難解的。第九章 離散優(yōu)化模型及算法設(shè)計(jì) 浙江大學(xué)數(shù)學(xué)建?；? 167。 在 167。一方面，很多 P問(wèn)題象線性規(guī)劃一樣有著極廣泛的應(yīng)用前景，且它們本身又是十分有趣的；另一方面，它們也是研究一些更為復(fù)雜、難解的問(wèn)題時(shí)經(jīng)常被采用的研究工具。 ???e此問(wèn)題的標(biāo)準(zhǔn)形式為給定一完全圖 G，其每邊賦有一權(quán)數(shù)，求此完全圖的最小生成樹(shù)。一個(gè)連通圖的生成樹(shù)是指圖中具有最多邊數(shù)的一棵樹(shù)。 ,1??i??根據(jù)定 1可以作了如下算法：任選一點(diǎn) ，令 若 V1=V，停；否則，找出僅有一個(gè)頂點(diǎn)在 V1中的邊里具有最小權(quán)的邊（ ,u），設(shè)，將 u加入 V1（ ,u）加入 T。不妨設(shè) ，則 ，此圈中的點(diǎn)不全由 Vi中的點(diǎn)組成 ,因此必存在圈中的另一邊 。 39。u?? ?? ? ? ?39。 標(biāo)號(hào) 1，先加入 （因?yàn)檫厵?quán) 最?。?， 標(biāo)號(hào) 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)被檢查一次。 解：由于入樹(shù)不能包含具有公共終點(diǎn)的孤，故對(duì)每一頂點(diǎn) 只能選取一條入孤。設(shè)對(duì)每一列向量 en已指定一權(quán) C（ en）求 的一個(gè)線性無(wú)關(guān)的子集，它具有最大的權(quán)和。 ? ?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 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 定義 (擬陣 ) 設(shè) E是一個(gè)有限集， γ為 E的部分子集構(gòu)成的封閉系統(tǒng)（即若 ，則必有 ）。AA???? 39。又由于這一離散優(yōu)化問(wèn)題的任一實(shí)例都可用貪婪法求解，故構(gòu)成一擬陣，被稱為矩陣擬陣。對(duì)于圖擬陣，每一極大獨(dú)立集均為一生成樹(shù)，其邊數(shù)均為|V|1。 定理 E為一有限集合，為 E的部分子集構(gòu)成的封閉獨(dú)立系統(tǒng)。I? Ie ???,??二、兩分圖匹配問(wèn)題與增廣路算法 在上一小節(jié)中我們已經(jīng)看到，有些 P問(wèn)題可以用極為簡(jiǎn)單的貪婪法求解。假定三個(gè)女兒為 A、 B、 C，三位求婚者為 X、 Y、 Z。再用三個(gè)點(diǎn)表示求婚者，將它們放在另一邊。 容易看出，酋長(zhǎng)要解的問(wèn)題是在兩分圖圖 匹配，讀者不難由此得到一般兩分圖最大權(quán)匹配問(wèn)題的數(shù)學(xué)模型。事實(shí)上，酋長(zhǎng)的女兒只有六種嫁法（ 3?。容^所有方案，發(fā)現(xiàn) C嫁x、 A嫁 y、 B嫁 z最好（ y幾乎差不多同樣喜歡 C和 A，而 z則明顯喜歡 C而不太喜歡 A），可得財(cái)禮 57頭牛。 如果所有邊的權(quán)均為 1，則最大權(quán)匹配化成最大匹配問(wèn)題（即求邊數(shù)最多 的匹配）。 定義 依次取未匹配邊、匹配邊的路稱為交錯(cuò)路。由未蓋點(diǎn) 出發(fā)，可作出增廣路 ，從而可得到一個(gè)增加一條匹配邊的更大匹配，如圖 （ b）所示。 證明： 必要性顯然，現(xiàn)證充分性。 現(xiàn)在可以看出，找最大匹配的關(guān)鍵在于找增廣路。 最大流問(wèn)題（ MFP） 邊賦值的有向圖稱為網(wǎng)絡(luò)。 建模： 給定一有向圖 G=（ V， A）， A的每一條孤（邊）（ i,j）上已賦一 表示邊容量的非負(fù)整數(shù) C（ i,j）。 ＭＦＰ 即在（ ）、 ()式約束下使達(dá)到最大，易見(jiàn)，這是一個(gè)線性規(guī)劃問(wèn)題的子問(wèn)題，故 ＭＦＰ 類。若 Ｐ 、 滿足 且 則稱 Ｐ 和 為Ｖ的一個(gè)切割。取Ｐ＝｛１，２，３，４｝，則＝｛５，６｝，顯然 Ｐ 、 是網(wǎng)絡(luò)的一個(gè)切割。 ? ? ? ?,i j C j i? ?? ? ? ? ? ?39。39。如圖 ，圖中的（ a）、（ b）、（ c）均是流量為 7的最大流，邊上的兩個(gè)數(shù)字依次為容量和邊上的實(shí)際流量。現(xiàn)在，我們將以最大流問(wèn)題的增廣路算法為基礎(chǔ)，導(dǎo)出求解最小費(fèi)用最大流問(wèn)題的算法。 ?例 圖 （ a）給出了有向圖 G上的一個(gè)可行流，其中弧上的三個(gè)數(shù)字分別為容量、單位流費(fèi)用及實(shí)際流量。調(diào)整此循環(huán)流上的流量，得到圖（ a）中的流。 證明： 設(shè) 1+2不是流量為 υ+1的最小費(fèi)用流，由定理 6，在 1+ 2的增廣網(wǎng)絡(luò)中必存在一負(fù)圈 C。算法可以用歸納方式給出，當(dāng) υ=0時(shí)，可取 =0，這顯然是 υ=0的最小費(fèi)用流。它可用來(lái)求解運(yùn)輸問(wèn)題、指派問(wèn)題及賦權(quán)兩分圖匹配問(wèn)題（等價(jià)于指派問(wèn)題），也可用來(lái)尋找網(wǎng)絡(luò)的瓶頸 ——即最小切割（ P， ）確定的邊。 P四、最短路徑問(wèn)題 最短路徑問(wèn)題是又一個(gè)經(jīng)常遇到的 P問(wèn)題，它在工藝流程的安排、管道或網(wǎng)絡(luò)的鋪設(shè)、設(shè)備更新等實(shí)際生產(chǎn)中常被用到，是網(wǎng)絡(luò)規(guī)劃的基本問(wèn)題之一。若點(diǎn)P在 A到 E的最短路上，則 P到 E的最短路徑必整個(gè)地包含在 A到 E的最短路徑上。（兩者目的略有不同）對(duì)例 ，如從起點(diǎn) A開(kāi)始標(biāo)導(dǎo)，先在 A點(diǎn)標(biāo)上 0。直到擬到達(dá)的終點(diǎn)已標(biāo)號(hào)為止。算法進(jìn)行中，事實(shí)上在構(gòu)造一棵由已標(biāo)號(hào)頂點(diǎn)及它們與其前行點(diǎn)間的邊組成的樹(shù)。 從圖 A到各點(diǎn)的距離及最短路徑，而從圖 各點(diǎn)到 E點(diǎn)的距離及最短路徑，這是兩者的區(qū)別?，F(xiàn)準(zhǔn)備制訂一個(gè)五年內(nèi)的設(shè)備更新計(jì)劃，使五年內(nèi)支付的設(shè)備購(gòu)置費(fèi)用及總維修費(fèi)用最少。例如，?。?① ， ② ）上的數(shù) 68表示第一年初購(gòu)買設(shè)備到 5年后的第六年初更換，需支付購(gòu)設(shè)備費(fèi) 10萬(wàn)元及各年維修費(fèi) 58 萬(wàn)元，共計(jì) 68萬(wàn)元。給定一個(gè)無(wú)向圖 G=（ V， E），問(wèn)能否由一個(gè)頂點(diǎn)出發(fā)，經(jīng)且僅經(jīng)過(guò)每條邊一次并返回原出發(fā)頂點(diǎn)。 把關(guān)聯(lián)偶數(shù)條邊的頂點(diǎn)稱為偶頂點(diǎn)，把關(guān)聯(lián)奇數(shù)條邊的頂點(diǎn)稱為奇頂點(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。而圖的奇頂點(diǎn)數(shù)又可通過(guò)對(duì)其頂點(diǎn)一一檢測(cè)而求得。要求從一指定頂點(diǎn)出發(fā)，至少經(jīng)過(guò)每一條邊一次最后返回原出發(fā)點(diǎn)，并使經(jīng)過(guò)邊的總長(zhǎng)度最小。若無(wú)向圖 G是歐拉圖，則任一歐拉圖都提供了一條最佳郵路。 。從上述 P問(wèn)題（包括第八章中的線性規(guī)劃、運(yùn)輸問(wèn)題及指派問(wèn)題）可以看出，它們都可以用某種逐次改進(jìn)的方法來(lái)求解。 最后，我們還想強(qiáng)調(diào)幾點(diǎn)： 許多表面有點(diǎn)相象的問(wèn)題事實(shí)上可能具有完全不同的計(jì)算復(fù)雜性。 （ 2）指派問(wèn)題與 TSP也有相似之處，前者求一置換而使目標(biāo)值最小，后者求一循環(huán)置換（不包含子圈）而使目標(biāo)值最小。 （ 4）線性規(guī)劃問(wèn)題、運(yùn)輸問(wèn)題及指派問(wèn)題均為 P問(wèn)題，但相應(yīng)的整數(shù)線性規(guī)劃及 0—1規(guī)劃均為 NP完全的。如若不然，我們可以利用它的有效算法如下構(gòu)造出哈密頓問(wèn)題的有效算：令圖 G=（ V， E）的所有邊的權(quán)均為 1，以一端點(diǎn)為起點(diǎn)求到其余各頂點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑。又譬如，網(wǎng)絡(luò)流中的最大流問(wèn)題是 P問(wèn)題。一方面，我們必須先搞清問(wèn)題的計(jì)算復(fù)雜性，而另一方面，條件的微小改變就有可能將一個(gè) P問(wèn)題轉(zhuǎn)變?yōu)镹P完全的。從某種意義上說(shuō)，可以認(rèn)為這些問(wèn)題已被較好地解決了。各種跡象使人們來(lái)越來(lái)越傾向于相信，對(duì)這些問(wèn)題根本不存在有效算法，自 1972年 Cook發(fā)表那篇著名的論文以來(lái)，這些問(wèn)題越來(lái)越多地被發(fā)現(xiàn)。但這類問(wèn)題事實(shí)上有無(wú)限多個(gè)，很多時(shí)候，我們會(huì)遇到一些對(duì)其計(jì)算機(jī)復(fù)雜性一無(wú)所知的問(wèn)題。本節(jié)將再分析一些問(wèn)題，看看別人是如何判定它們的 NP完全性的。 ( , )uE???對(duì)于例 ，我們?yōu)閿⑹龇奖?，采用了圖的語(yǔ)言，其實(shí)也完全可以將它們表達(dá)成其他方式。而團(tuán)問(wèn)題是 NP完全的（見(jiàn)第八章六個(gè)基本 NP完全問(wèn)題），故獨(dú)立集問(wèn)題是 NP完全的。 例 （背包問(wèn)題） 給定一組整數(shù) C={c1,…, }以及一整數(shù) K，問(wèn)是否存在C的一個(gè)子集 S，使得 。 例 。而當(dāng)我們真正想把一批已知長(zhǎng)、寬、高的物體裝入具有相同尺寸的箱子時(shí)，又遇到了三維的。事實(shí)上， 取 ， J={c1,…, }可劃分為兩個(gè)相等的集合的充要條件是 它們可裝入兩只容量為 C的箱中。順便指出， Bin—packin問(wèn)題中的臬子容量 C可以取為 1，這樣的問(wèn)題與例 。按此方法分類，有人作過(guò)統(tǒng)計(jì)，認(rèn)為至少有 9000多個(gè)不同的排序問(wèn)題已被或多或少地研究過(guò)，其中 76%為 NP完全的 ， 12%的為 P問(wèn)題 ，余下的 12%目前還未搞清其計(jì)算復(fù)雜性，但根據(jù)種種跡象 ，大部分可能是 NP完全的。 Job shop意指每一工件要在 m臺(tái)機(jī)器的每一臺(tái)上加工（當(dāng)不需某臺(tái)加工時(shí)可令加工時(shí)間為零），且各工件使用機(jī)器的順序可以不同。在那里已經(jīng)證明了這一問(wèn)題等價(jià)與 TSP，從而是 NP完全的。 γ=Cmax的解釋同上。下面給出一個(gè)稍難一些的例子，供有興趣的讀者參考。評(píng)判排序優(yōu)劣的標(biāo)準(zhǔn)為各工件完工時(shí)間 Cj的加權(quán)和 越小越好。 311 tiibat?? ?, 42ibbia? ? ?現(xiàn)在，我們來(lái)證明，對(duì)三元?jiǎng)澐謫?wèn)題的每一實(shí)例，總可構(gòu)造出一個(gè)等價(jià)的1/1/rj, prmp/ 排序問(wèn)題的實(shí)例，（因此，會(huì)解后者就必會(huì)解前者）。除去加工這 t－ 1項(xiàng)工件的時(shí)段，整個(gè)加工期還留下長(zhǎng)度均為 b的 t個(gè)時(shí)段。事實(shí)上，僅對(duì)部分變量有非負(fù)約束的線性規(guī)劃（稱為混合整數(shù)規(guī)劃）也是 NP完全的。例如，求解線性規(guī)劃的單純形法從理論上講是指數(shù)算法，但在實(shí)際應(yīng)用時(shí)它又一般表現(xiàn)得出奇地好（已經(jīng)證明，其平均計(jì)算量?jī)H為 O(nlog2n)）。我們將在本節(jié)舉幾個(gè)實(shí)例來(lái)介紹這類算法。問(wèn)此單位應(yīng)購(gòu)兩種房各多少套才能使總收入最大 建模 設(shè) x x2分別為購(gòu)買兩種房的套數(shù)，顯然 x x2必須為整數(shù)，故要求求解整數(shù)規(guī)劃（ ILP） max x1 + 13x1 + ≤91 4 x1 + 40x2≤140 x1≤4 x x2≥0且為整數(shù) 解 ： 先不考慮整數(shù)要求，求解與上述整數(shù)規(guī)劃（ ILP）相應(yīng)的線性