【正文】 a)五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113解：編寫程序如下：clc,cleara(1,2)=56。a(1,3)=35。a(1,4)=21。a(1,5)=51。a(1,6)=60。a(2,3)=21。a(2,4)=57。a(2,5)=78。a(2,6)=70。a(3,4)=36。a(3,5)=68。a(3,6)=68。a(4,5)=51。a(4,6)=61。a(5,6)=13。a(6,:)=0。a=a+a39。c1=[5 1:4 6]。L=length(c1)。flag=1。while flag0 flag=0。 for m=1:L3 for n=m+2:L1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1。 c1(m+1:n)=c1(n:1:m+1)。 end end endendsum1=0。for i=1:L1 sum1=sum1+a(c1(i),c1(i+1))。endcircle=c1。sum=sum1。c1=[5 6 1:4]。%改變初始圈，該算法的最后一個頂點不動flag=1。while flag0 flag=0。 for m=1:L3 for n=m+2:L1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1。 c1(m+1:n)=c1(n:1:m+1)。 end end endendsum1=0。for i=1:L1 sum1=sum1+a(c1(i),c1(i+1))。endif sum1sum sum=sum1。 circle=c1。endcircle,sum167。7 最大流問題 最大流問題的數(shù)學(xué)描述 網(wǎng)絡(luò)中的流 定義 在以為節(jié)點集，為弧集的有向圖上定義如下的權(quán)函數(shù)：（i）為孤上的權(quán)函數(shù)，弧對應(yīng)的權(quán)記為，稱為孤的容量下界（lower bound）；（ii）為弧上的權(quán)函數(shù)，弧對應(yīng)的權(quán)記為，稱為孤的容量上界，或直接稱為容量（capacity）；（iii）為頂點上的權(quán)函數(shù)，節(jié)點對應(yīng)的權(quán)記為，稱為頂點的供需量（supply／demand）；此時所構(gòu)成的網(wǎng)絡(luò)稱為流網(wǎng)絡(luò)，可以記為。 由于我們只討論為有限集合的情況，所以對于弧上的權(quán)函數(shù)和頂點上的權(quán)函數(shù)，可以直接用所有孤上對應(yīng)的權(quán)組成的有限維向量表示，因此有時直接稱為權(quán)向量，或簡稱權(quán)。由于給定有向圖后，我們總是可以在它的弧集合和頂點集合上定義各種權(quán)函數(shù)，所以流網(wǎng)絡(luò)一般也直接簡稱為網(wǎng)絡(luò)。 在流網(wǎng)絡(luò)中，弧的容量下界和容量上界表示的物理意義分別是：通過該弧發(fā)送某種“物質(zhì)”時，必須發(fā)送的最小數(shù)量為，而發(fā)送的最大數(shù)量為。頂點對應(yīng)的供需量則表示該頂點從網(wǎng)絡(luò)外部獲得的“物質(zhì)”數(shù)量（時），或從該頂點發(fā)送到網(wǎng)絡(luò)外部的“物質(zhì)”數(shù)量（時）。下面我們給出嚴格定義。 定義 對于流網(wǎng)絡(luò)，其上的一個流（flow）是指從的弧集到的一個函數(shù)，即對每條弧賦予一個實數(shù)（稱為弧的流量）。如果流滿足 （1）， （2）則稱為可行流（feasible flow）。至少存在一個可行流的流網(wǎng)絡(luò)稱為可行網(wǎng)絡(luò)（feasible network）．約束（1）稱為流量守恒條件（也稱流量平衡條件），約束（2）稱為容量約束。 可見，當(dāng)時，表示有個單位的流量從該項點流出，因此頂點稱為供應(yīng)點（supply node）或源（source），有時也形象地稱為起始點或發(fā)點等；當(dāng)時，表示有個單位的流量流入該點（或說被該頂點吸收），因此頂點稱為需求點（demand node）或匯（sink），有時也形象地稱為終止點或收點等；當(dāng)時，頂點稱為轉(zhuǎn)運點（transshipment node）或平衡點、中間點等。此外，根據(jù)（1）可知，對于可行網(wǎng)絡(luò)，必有 （3）也就是說，所有節(jié)點上的供需量之和為0是網(wǎng)絡(luò)中存在可行流的必要條件。 一般來說，我們總是可以把的流網(wǎng)絡(luò)轉(zhuǎn)化為的流網(wǎng)絡(luò)進行研究。所以，除非特別說明，以后我們總是假設(shè)（即所有孤的容量下界），并將時的流網(wǎng)絡(luò)簡記為。此時，相應(yīng)的容量約束（2）為 。定義 在流網(wǎng)絡(luò)中，對于流，如果 ，則稱為零流，否則為非零流。如果某條弧上的流量等于其容量（），則稱該弧為飽和?。╯aturated arc）；如果某條弧上的流量小于其容量（），則稱該弧為非飽和?。蝗绻硹l弧上的流量為 0（），則稱該弧為空弧（void arc）。 最大流問題考慮如下流網(wǎng)絡(luò)：節(jié)點為網(wǎng)絡(luò)中唯一的源點，為唯一的匯點，而其它節(jié)點為轉(zhuǎn)運點。如果網(wǎng)絡(luò)中存在可行流，此時稱流的流量（或流值，flow value）為（根據(jù)（3），它自然也等于），通常記為或，即 。對這種單源單匯的網(wǎng)絡(luò)，如果我們并不給定和（即流量不給定），則網(wǎng)絡(luò)一般記為。最大流問題（maximum flow problem）就是在中找到流值最大的可行流（即最大流）。我們將會看到，最大流問題的許多算法也可以用來求解流量給定的網(wǎng)絡(luò)中的可行流。也就是說，當(dāng)我們解決了最大流問題以后，對于在流量給定的網(wǎng)絡(luò)中尋找可行流的問題，通常也就可以解決了。因此，用線性規(guī)劃的方法，最大流問題可以形式地描述如下：. ， （4） . （5）定義 如果一個矩陣的任何子方陣的行列式的值都等于，或，則稱是全幺模的(totally unimodular TU，又譯為全單位模的)，或稱是全幺模矩陣。定理8（整流定理） 最大流問題所對應(yīng)的約束矩陣是全幺模矩陣。若所有弧容量均為正整數(shù)，則問題的最優(yōu)解為整數(shù)解。最大流問題是一個特殊的線性規(guī)劃問題。我們將會看到利用圖的特點，解決這個問題的方法較之線性規(guī)劃的一般方法要方便、直觀得多。 單源和單匯運輸網(wǎng)絡(luò)實際問題往往是多源多匯網(wǎng)絡(luò)，為了計算的規(guī)格化，可將多源多匯網(wǎng)絡(luò)化成單源單匯網(wǎng)絡(luò)。設(shè)是的源，是的匯，具體轉(zhuǎn)化方法如下：（i）在原圖中增加兩個新的頂點和，令其分別為新圖中之單源和單匯，則中所有頂點成為之中間頂點集。（ii）用一條容量為的弧把連接到中的每個頂點。（iii）用一條容量為的弧把中的每個頂點連接到。和中的流以一個簡單的方式相互對應(yīng)。若是中的流，則由所定義的函數(shù)是中使得的流。反之，中的流在的弧集上的限制就是中具有相同值的流。 最大流和最小割關(guān)系設(shè)，，則稱為網(wǎng)絡(luò)的一個割，其中，為尾在，頭在的弧集，稱 為割的容量。定理9 是最大流，是容量最小的割的充要條件是。在網(wǎng)絡(luò)中，對于軌（此軌為無向的），若，則稱它為前向??；若，則稱它為后向弧。在網(wǎng)絡(luò)中，從到的軌上，若對所有的前向弧都有，對所有的后向弧恒有，則稱這條軌為從到的關(guān)于的可增廣軌。令，則在這條可增廣軌上每條前向弧的流都可以增加一個量，而相應(yīng)的后向弧的流可減少，這樣就可使得網(wǎng)絡(luò)的流量獲得增加，同時可以使每條弧的流量不超過它的容量，而且保持為正，也不影響其它弧的流量?？傊W(wǎng)絡(luò)中可增廣軌的存在是有意義的，因為這意味著不是最大流。 最大流的一種算法—標號法標號法是由Ford和Fulkerson在1957年提出的。用標號法尋求網(wǎng)絡(luò)中最大流的基本思想是尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止。63