圖論中幾個(gè)典型問題的求解

圖論中幾個(gè)典型問題的求解第一頁，共一百六十一頁，編輯于2023年，星期二§1圖的基本概念第二頁，共一百六十一頁，編輯于2023年，星期二圖是一種直觀形象地描述已知信息的方式，它使事物之間的關(guān)系簡(jiǎn)潔明了，是分析問題的有用工具，很多實(shí)際問題可以用圖來描述。第三頁，共一百六十一頁，編輯于2023年，星期二一、圖的定義

圖論是以圖為研究對(duì)象的數(shù)學(xué)分支，在圖論中，圖由一些點(diǎn)和點(diǎn)之間的連線所組成．

稱圖中的點(diǎn)為頂點(diǎn)（節(jié)點(diǎn)），稱連接頂點(diǎn)的沒有方向的線段為邊，稱有方向的線段為?。肰={v1,v2,…}表示全體頂點(diǎn)的集合，用

E={e1,e2,…}表示全體邊的集合，如果對(duì)于E中的任一條邊ek，在V中都有一對(duì)頂點(diǎn)(vi,vj)和它對(duì)應(yīng)，則稱由V和E組成的集體為一個(gè)圖，記為G={V,E}，簡(jiǎn)寫為G．第四頁，共一百六十一頁，編輯于2023年，星期二二、基本概念

點(diǎn)與邊相連接稱為關(guān)聯(lián)，與邊e關(guān)聯(lián)的頂點(diǎn)稱為該邊的端點(diǎn)，與同一條邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)稱為相鄰頂點(diǎn)，與同一個(gè)頂點(diǎn)關(guān)聯(lián)的邊稱為相鄰邊．具有相同頂點(diǎn)的邊稱為平行邊，兩個(gè)端點(diǎn)重合的邊稱為環(huán)．所有線段都沒有方向的圖稱為無向圖，所有線段都有方向的圖稱為有向圖，既有邊也有弧的圖稱為混合圖．在無向圖中，沒有環(huán)和平行邊的圖稱為簡(jiǎn)單圖，任意兩個(gè)頂點(diǎn)之間都有一條邊相連的簡(jiǎn)單圖稱為完全圖．任意兩個(gè)頂點(diǎn)之間有且只有一條弧相連的有向圖稱為競(jìng)賽圖．第五頁，共一百六十一頁，編輯于2023年，星期二在無向圖中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目（環(huán)算兩次）稱為該頂點(diǎn)的度（或次數(shù)），記為d(v)。度為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度為偶數(shù)的頂點(diǎn)叫做偶點(diǎn)。在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為該頂點(diǎn)的出度，記為d+(v)，從頂點(diǎn)v引入的邊的數(shù)目稱為該頂點(diǎn)的入度，記為d-(v)，而d(v)＝d+(v)+d-(v)稱為v的次數(shù)。第六頁，共一百六十一頁，編輯于2023年，星期二在圖中，兩個(gè)頂點(diǎn)u和v之間由頂點(diǎn)和邊構(gòu)成的交錯(cuò)序列（使u和v相通）稱為鏈（通道），沒有重復(fù)邊的通道稱為跡，起點(diǎn)與終點(diǎn)重合的通道稱為閉通道，不重合的稱為開通道，沒有重復(fù)頂點(diǎn)（必然邊也不重復(fù)）的開通道稱為路，起點(diǎn)與終點(diǎn)重合的路稱為圈（回路）．包含奇數(shù)個(gè)頂點(diǎn)（或邊）的圈稱為奇圈，包含偶數(shù)個(gè)頂點(diǎn)（或邊）的圈稱為偶圈。如果頂點(diǎn)u和v之間存在一條路，則稱u和v是連通的，任意兩個(gè)頂點(diǎn)都連通的圖稱為連通圖．無圈的連通圖稱為樹，如果一棵樹T包含了圖G的所有頂點(diǎn)，稱T為G的生成樹．第七頁，共一百六十一頁，編輯于2023年，星期二如果圖G的每條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)C(e)，稱C(e)為該邊e的權(quán)，稱圖G為賦權(quán)圖．通常稱賦權(quán)的有向圖為網(wǎng)絡(luò)．圖中邊e6和e7是平行邊，e9是環(huán)，頂點(diǎn)v4是懸掛點(diǎn)，邊e4是懸掛邊．第八頁，共一百六十一頁，編輯于2023年，星期二§2最短路問題第九頁，共一百六十一頁，編輯于2023年，星期二最短路問題是圖論應(yīng)用的基礎(chǔ)，很多實(shí)際問題，如線路的布設(shè)、運(yùn)輸規(guī)劃、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)用流等問題，都可以通過建立最短路模型來求解。有些有深度的圖與網(wǎng)絡(luò)優(yōu)化問題，如旅行售貨商、中國(guó)郵遞員等問題，需要在首先求出任意兩點(diǎn)之間最短路的基礎(chǔ)上解決。一、最短路的概念給定一個(gè)連通的賦權(quán)圖G={V,E}，設(shè)R是連接節(jié)點(diǎn)vi和vj的一條路，該路的權(quán)定義為路中所有各邊權(quán)之和，如果路R在所有連接節(jié)點(diǎn)vi和vj的路中權(quán)最小，則稱它為vi和vj間的最短路。第十頁，共一百六十一頁，編輯于2023年，星期二二、任意兩點(diǎn)之間的最短路(Floyd算法)Floyd算法利用距離矩陣進(jìn)行迭代運(yùn)算，可以一次性地求出任意兩點(diǎn)之間的最短路，該方法的思路有創(chuàng)意，計(jì)算量小，編程較簡(jiǎn)單，又稱矩陣求解法。1．算法原理

設(shè)A=[aij]m×n是圖的權(quán)矩陣（也稱帶權(quán)鄰接矩陣），其中aij是圖上連接頂點(diǎn)i和j的邊的權(quán)，如果兩頂點(diǎn)之間沒有直接相連的邊（即兩頂點(diǎn)不相鄰），則aij=∞。第十一頁，共一百六十一頁，編輯于2023年，星期二令矩陣D(0)=A，作為迭代的初始矩陣，從它出發(fā)按照一定規(guī)則求D(1)，又由D(1)按照類似的規(guī)則求D(2)，依此類推進(jìn)行迭代直至求出D(n)，設(shè)矩陣D(m)的元素為dij(m)，迭代規(guī)則為：

上式表示dij(1)在dij(0)以及從頂點(diǎn)vi經(jīng)過頂點(diǎn)v1到vj的權(quán)之和di1(0)+d1j(0)兩者之中選擇最短長(zhǎng)度。依此規(guī)則迭代。第十二頁，共一百六十一頁，編輯于2023年，星期二上式表示dij(2)在dij(1)以及從頂點(diǎn)vi經(jīng)過頂點(diǎn)v2到vj的權(quán)之和di2(1)+d2j(1)兩者之中選擇最短長(zhǎng)度。依此類推，迭代公式為：上式表示dij(m)在dij(m-1)以及從頂點(diǎn)vi經(jīng)過頂點(diǎn)vm到vj的權(quán)之和dim(m-1)+dmj(m-1)兩者之中選擇最短長(zhǎng)度。當(dāng)m=n時(shí)結(jié)束迭代。

第十三頁，共一百六十一頁，編輯于2023年，星期二2．程序設(shè)計(jì)

先編寫Flody算法的子程序（函數(shù)）如下：Function[D,R]=floyd(a)n=size(a,1);D=a;%D是初始矩陣fori=1:n

forj=1:nR(i,j)=j;endend第十四頁，共一百六十一頁，編輯于2023年，星期二fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)

D(i,j)=D(i,k)+D(k,j);%在循環(huán)中進(jìn)行矩陣迭代

R(i,j)=R(i,k);%R是路徑矩陣endendendendD,R%輸出最短路矩陣和最短路的路徑矩陣。第十五頁，共一百六十一頁，編輯于2023年，星期二以上程序是通用程序，只需輸入初始距離矩陣，就能輸出最短路矩陣以及最短路的路徑矩陣，將程序以文件名floyd.m存盤。例1以2007年研究生數(shù)學(xué)建模競(jìng)賽C題為例，已知16個(gè)郵政支局的初始距離矩陣，求任意兩個(gè)節(jié)點(diǎn)之間的最短路。解：編寫主程序如下：a=[0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;…………inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0];[D,R]=floyd(a);第十六頁，共一百六十一頁，編輯于2023年，星期二輸入數(shù)據(jù)中的inf表示無窮大（兩個(gè)頂點(diǎn)之間沒有邊直接相連）。運(yùn)行以上程序，求得最短路矩陣D和最短路的路徑矩陣。此處省略結(jié)果。

第十七頁，共一百六十一頁，編輯于2023年，星期二§3最小生成樹第十八頁，共一百六十一頁，編輯于2023年，星期二一、最小生成樹的概念樹是圖論中的一種簡(jiǎn)單而重要的圖，連通并且無圈的無向圖稱為樹，常用T表示。樹有以下性質(zhì)：(1)樹中任意兩點(diǎn)之間有唯一路徑；(2)樹的邊數(shù)等于頂點(diǎn)數(shù)減1；(3)在樹中刪去任意一條邊就不連通；(4)在樹中任意兩個(gè)不相鄰的頂點(diǎn)間添加一條邊，則恰好產(chǎn)生一個(gè)圈。第十九頁，共一百六十一頁，編輯于2023年，星期二具有n個(gè)頂點(diǎn)的無向連通圖是樹的充分必要條件是它有n-1條邊．連通圖G的子圖T，如果它的頂點(diǎn)集與G的頂點(diǎn)集相同，且T為樹，則稱T是圖G的生成樹，又稱支撐樹。如果圖的邊有權(quán)（對(duì)應(yīng)于邊的實(shí)數(shù)），則生成樹上各邊權(quán)的總和稱為生成樹的權(quán)，生成樹并不唯一，權(quán)達(dá)到最小的生成樹稱為最小生成樹(MinimalSpanningTree，簡(jiǎn)稱MST)，最小生成樹不一定唯一．第二十頁，共一百六十一頁，編輯于2023年，星期二最小生成樹是網(wǎng)絡(luò)優(yōu)化中的一個(gè)重要問題，在網(wǎng)絡(luò)設(shè)計(jì)中有廣泛的應(yīng)用，例如如何修筑一些公路把若干個(gè)城鎮(zhèn)連接起來且總里程最短；如何架設(shè)通訊網(wǎng)絡(luò)將若干個(gè)地區(qū)連接起來且總費(fèi)用最??；如何修筑水渠將水源和若干塊待灌溉的土地連接起來且總距離最短等等．這些應(yīng)用問題通稱為最優(yōu)連線問題，其實(shí)質(zhì)是尋找圖的最小生成樹．第二十一頁，共一百六十一頁，編輯于2023年，星期二二、Prim（普里姆）算法求圖的最小生成樹最常用的算法有兩種：Prim（普里姆）算法和Kruskal（克羅斯克爾）算法，這兩種方法都由貪婪法的思想發(fā)展而來。貪婪法又稱貪心法，該法總是做出在當(dāng)前看來最好的選擇，也就是說該算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪婪算法不能對(duì)所有問題都得到整體最優(yōu)解，但是它對(duì)某些問題能夠得到整體最優(yōu)解，例如圖的固定起點(diǎn)的最短路問題，最小生成樹問題。有時(shí)候，即使貪婪算法不能得到整體最優(yōu)解，但其結(jié)果卻是整體最優(yōu)解的很好近似。第二十二頁，共一百六十一頁，編輯于2023年，星期二Prim算法的思路是：把所有頂點(diǎn)分成部分（兩個(gè)集合），一個(gè)用S表示（該集合中的頂點(diǎn)都涂成紅色），另一個(gè)用V-S表示（該集合中的頂點(diǎn)都涂成白色），開始時(shí)S中只有一個(gè)頂點(diǎn)v1，其余頂點(diǎn)都是白色，在一個(gè)端點(diǎn)為紅色，另一個(gè)端點(diǎn)為白色的邊中選取權(quán)最小的邊，將該邊涂紅（表示入選最小生成樹）并且把該邊的白色端點(diǎn)也涂紅（表示移入S中）這個(gè)過程一直進(jìn)行下去，S中的端點(diǎn)越來越多，直到所有頂點(diǎn)都涂成紅色為止，或者說紅色邊達(dá)到n-1條為止。第二十三頁，共一百六十一頁，編輯于2023年，星期二從Prim算法的思路中可以看出，該算法的關(guān)鍵是如何找出連接紅點(diǎn)和白點(diǎn)的所有邊中找出權(quán)最小的邊。若G為完全圖，當(dāng)前有k個(gè)紅點(diǎn)，則有n-k個(gè)白點(diǎn)，有k(n-k)條連接紅、白點(diǎn)的邊，為了在如此眾多的邊中找到權(quán)最小的邊，可以分兩步走，對(duì)每一個(gè)白點(diǎn)，先從連接該點(diǎn)至k個(gè)紅點(diǎn)的k條中找出權(quán)最小的邊作為候選邊，然后對(duì)n-k個(gè)白點(diǎn)，從n-k條候選邊中找出權(quán)最小的邊。第二十四頁，共一百六十一頁，編輯于2023年，星期二實(shí)現(xiàn)Prim算法的Matlab編程思路如下：(1)設(shè)第一個(gè)紅點(diǎn)是節(jié)點(diǎn)v1。構(gòu)建初始候選邊的權(quán)矩陣B。該矩陣有3行，第一行表示當(dāng)前紅點(diǎn)，開始時(shí)第一個(gè)紅點(diǎn)是v1，故第一行都是1，第二行表示白點(diǎn)，開始時(shí)白點(diǎn)的序號(hào)是2,3,…,n，第三行表示連接紅點(diǎn)和白點(diǎn)的邊的權(quán)值。當(dāng)前入選最小生成樹的最短邊將從該矩陣中產(chǎn)生。初始最小生成樹T是空集。(2)對(duì)B矩陣的第3行排序，即對(duì)候選邊的權(quán)值進(jìn)行排序，選取最短邊（權(quán)值最小的邊），把該邊涂紅（選入最小生成樹的邊集T），該邊的白色端點(diǎn)也涂成紅色。第二十五頁，共一百六十一頁，編輯于2023年，星期二(3)將(2)選出的邊移出B（不參與下一輪競(jìng)選），即將它從B矩陣中刪除。當(dāng)前有n-2個(gè)白點(diǎn)（兩個(gè)紅點(diǎn)），對(duì)每個(gè)白點(diǎn)都有到兩個(gè)紅點(diǎn)的兩條邊，通過比較這兩者的大小，選出權(quán)值小的邊，放入B矩陣的相應(yīng)位置上，由此構(gòu)建新的候選邊矩陣B，此時(shí)B矩陣的有n-2列。(4)對(duì)新的B矩陣重復(fù)(2)和(3)，T中的邊將越來越多，B矩陣的列數(shù)越來越少，當(dāng)選入T中的紅色邊達(dá)到n-1條時(shí)結(jié)束運(yùn)算，輸出T。第二十六頁，共一百六十一頁，編輯于2023年，星期二按照以上思路編寫Matlab程序如下：function[T,e]=prim(a)T=[];%T為最小生成樹的邊集，開始為空集。e=0;%e是最小生成樹的長(zhǎng)度，開始為0。v=1;%v表示第一個(gè)紅點(diǎn)是1號(hào)頂點(diǎn)。n=size(a,1);%n是總頂點(diǎn)數(shù)，它等于初始距離矩陣a的列數(shù)。c=2:n;%c代表所有白點(diǎn)，開始是2,3,…,n。第二十七頁，共一百六十一頁，編輯于2023年，星期二forj=2:nb(1,j-1)=1;b(2,j-1)=j;

b(3,j-1)=a(1,j);end%以上一段程序生成3行n-1列的矩陣，存儲(chǔ)初始候選邊及其權(quán)值信息，該矩陣的第一行都是1，表示第一個(gè)紅色點(diǎn)是1號(hào)頂點(diǎn)，第二行表示白色點(diǎn)依次為2,3,…,n，第三行表示所有連接紅點(diǎn)和白點(diǎn)的邊的權(quán)值第二十八頁，共一百六十一頁，編輯于2023年，星期二whilesize(T,2)<n-1%只要最小生成樹的邊數(shù)小于n-1就循環(huán)[m,i]=min(b(3,:));%從候選邊中找出權(quán)值最小的邊（其值存入變量m，序號(hào)為i）T(:,size(T,2)+1)=b(:,i);%當(dāng)前最短邊（含起點(diǎn)、終點(diǎn)和權(quán)值3個(gè)樹中）存入T中當(dāng)前列，表示入選最小生成樹

e=e+b(3,i);%累計(jì)最小生成樹的長(zhǎng)度

v=b(2,i);%把新入選最小生成樹的邊的白色端點(diǎn)變成當(dāng)前紅點(diǎn)第二十九頁，共一百六十一頁，編輯于2023年，星期二t=find(c==b(2,i));c(t)=[];%把該點(diǎn)從白點(diǎn)集合中移出去b(:,i)=[];%把該邊從候選邊中刪除

forj=1:length(c)d=a(v,b(2,j));ifd<b(3,j)b(1,j)=v;b(3,j)=d;endend第三十頁，共一百六十一頁，編輯于2023年，星期二%以上循環(huán)調(diào)整候選邊集合，入選該集合的邊數(shù)等于當(dāng)前白點(diǎn)數(shù)，對(duì)每一個(gè)白點(diǎn)入選一條邊，該邊通過比較連接該白點(diǎn)到紅點(diǎn)的邊的權(quán)值大小確定，小者入選。該循環(huán)是程序的關(guān)鍵和核心部分。endT,e以上程序以文件名prim.m存盤。第三十一頁，共一百六十一頁，編輯于2023年，星期二例2以2007年研究生數(shù)學(xué)建模競(jìng)賽C題為例，已知縣郵政局X1和16個(gè)郵政支局的初始距離矩陣，求該運(yùn)輸圖的最小生成樹。解：在Matlab中輸入a=[0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;……inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0];[T,e]=prim(a);第三十二頁，共一百六十一頁，編輯于2023年，星期二計(jì)算結(jié)果為：T=1567551116111016164111456784111617109151231314211139131415991011111419212121e=221T中每一列代表入選最小生成樹的一條邊，每一列有3個(gè)元素，前兩個(gè)代表頂點(diǎn)的編號(hào)，第3個(gè)是邊的權(quán)值。e是最小生成樹的總長(zhǎng)。第三十三頁，共一百六十一頁，編輯于2023年，星期二三、Kruskal（克羅斯克爾）算法Kruskal（克羅斯克爾）算法又稱“避圈法”，也是一種貪婪算法。給定加權(quán)連通圖G={V,E}，Kruskal算法的基本思路如下：(1)把所有邊按照權(quán)值的大小由小到大排序，將最小邊入選最小生成樹T。(2)從剩下的邊中選取權(quán)值最小的邊，并且該邊與T中已經(jīng)存在的邊不形成圈，將它也取進(jìn)T中（若某邊權(quán)值雖然小，但形成圈則舍去此邊，并且另選。重復(fù)步驟(2),直至入選T的邊達(dá)到n-1條為止。第三十四頁，共一百六十一頁，編輯于2023年，星期二由以上思路可知，Kruskal算法的關(guān)鍵是如何判斷一條候選邊是否會(huì)與T中已有邊形成圈，下面介紹一種判斷方法。設(shè)所有頂點(diǎn)都是紅色，選入最小生成樹T的邊為紅色，沒有選入的邊為白色。則紅點(diǎn)和紅邊會(huì)形成一個(gè)或者一個(gè)以上的連通分支，它們都是G的子樹，當(dāng)一條待選邊的兩個(gè)端點(diǎn)屬于同一棵子樹時(shí)候就會(huì)形成圈，否則不構(gòu)成圈，且該邊入選后會(huì)使原來兩個(gè)不連通的紅色子樹合并成為一棵紅色連通子樹。因此判斷一條邊是否會(huì)與現(xiàn)有紅邊形成圈，只需要判斷該邊的兩個(gè)端點(diǎn)是否屬于同一棵子樹。第三十五頁，共一百六十一頁，編輯于2023年，星期二可以用下面的方法來實(shí)現(xiàn)以上判斷：給每棵子樹一個(gè)不同的編號(hào)，對(duì)每一個(gè)頂點(diǎn)引入一個(gè)標(biāo)記t，表示該頂點(diǎn)所在子樹的編號(hào)。當(dāng)加入一條紅色邊時(shí)，就該邊兩個(gè)端點(diǎn)所在的子樹連接起來成為一棵子樹，從而兩棵子樹中的頂點(diǎn)標(biāo)記要改成一樣。第三十六頁，共一百六十一頁，編輯于2023年，星期二按照以上思路編寫Matlab程序如下：function[T,c]=kruskal(a)n=size(a,1);%n是總頂點(diǎn)數(shù)m=0;fori=1:n-1forj=i+1:nifa(i,j)>0&a(i,j)<infm=m+1;b(1,k)=i;b(2,k)=j;b(3,k)=a(i,j);endendend第三十七頁，共一百六十一頁，編輯于2023年，星期二%以上循環(huán)生成圖的邊權(quán)矩陣，該矩陣有3行，第1行和第2行是頂點(diǎn)的編號(hào)，第3行是邊的權(quán)值，矩陣的列數(shù)對(duì)于圖的邊數(shù)，每一列代表一條邊。程序運(yùn)行以后，該矩陣的列數(shù)（即圖的總邊數(shù)記錄在變量m中）。[B,i]=sortrows(b',3);B=B';%實(shí)現(xiàn)對(duì)邊權(quán)矩陣按照權(quán)值大小由小到大排序，B是排序以后的邊權(quán)矩陣。k=0;%k表示已經(jīng)被選入最小生成樹的邊數(shù)t=1:n;%開始每個(gè)頂點(diǎn)各自為一棵獨(dú)立的子樹，子樹的編號(hào)分別1,2,…,n。T=[];c=0;%開始時(shí)最小生成樹為空集，權(quán)值之和為0第三十八頁，共一百六十一頁，編輯于2023年，星期二fori=1:m%對(duì)排序以后的邊權(quán)矩陣，按順序考察每一條邊ift(B(1,i))~=t(B(2,i))%當(dāng)?shù)趇條邊的兩個(gè)端點(diǎn)所在子樹的編號(hào)不相等時(shí)，該邊與已經(jīng)選入最小生成樹的邊不形成圈，于是運(yùn)行以下語句

k=k+1;%入選最小生成樹的邊數(shù)k增加1T(:,k)=B(:,i);%把該邊選入最小生成樹的集合Tc=c+B(3,i);%把該邊的權(quán)值加到最小生成樹的總權(quán)值之中

tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));第三十九頁，共一百六十一頁，編輯于2023年，星期二%入選邊的兩個(gè)端點(diǎn)分別屬于不同的子樹，t標(biāo)號(hào)不同，對(duì)這兩個(gè)t標(biāo)號(hào)排序forj=1:n

ift(j)==tmaxt(j)=tmin;

endend%將入選邊所屬兩個(gè)t標(biāo)號(hào)合并成一個(gè)（大標(biāo)號(hào)改為小標(biāo)號(hào)）end第四十頁，共一百六十一頁，編輯于2023年，星期二

ifk==n-1%如果入選最小生成樹的邊數(shù)達(dá)到n-1，則結(jié)束計(jì)算

break;endendT,c以上程序以文件名kruskal.m存盤。第四十一頁，共一百六十一頁，編輯于2023年，星期二仍然以例2的數(shù)據(jù)為例，先輸入數(shù)據(jù)矩陣a，然后運(yùn)行[T,e]=kruskal(a)得到計(jì)算結(jié)果。T=6111610191557412531127161711510166851611413141499910111111131314141519212121e=221該結(jié)果與Prim算法求出的結(jié)果相同。雖然Prim和kruskal兩種算法的思路都由貪婪法發(fā)展而來，但它們用來求最小生成樹時(shí)，最終輸出結(jié)果必定是最優(yōu)解。第四十二頁，共一百六十一頁，編輯于2023年，星期二最小生成樹

的圖形第四十三頁，共一百六十一頁，編輯于2023年，星期二四、用LINGO求最小生成樹1.把最小生成樹問題轉(zhuǎn)化為整數(shù)規(guī)劃采用一定的方法可以把最小生成樹問題轉(zhuǎn)化為整數(shù)規(guī)劃，然后用LINGO求解。節(jié)點(diǎn)1表示樹根，點(diǎn)i到點(diǎn)j的距離用Cij表示，當(dāng)兩個(gè)節(jié)點(diǎn)之間沒有線路相通時(shí)，兩點(diǎn)之間距離用M(很大的實(shí)數(shù))表示。引入0-1整數(shù)變量xij：若xij=1(且i≠j)表示從i到j(luò)的邊在樹中，xij＝0則表示該邊不在樹中。第四十四頁，共一百六十一頁，編輯于2023年，星期二目標(biāo)函數(shù)約束條件：(1)除樹根外每個(gè)點(diǎn)都有線路通到(且只需要一次)表示為(2)至少有一條線路從1出來第四十五頁，共一百六十一頁，編輯于2023年，星期二以上約束條件是必要條件，但不充分，類似于TSP問題，增加一個(gè)變量u，再附加約束條件：(1)限制uj的取值范圍為：u1=0，1≤uj≤n-1，j=2,3,...,n；用以下不等式可以達(dá)到目的：uj≥1且uj≤

n-1-(n-2)x1j，j>1，(2)如果線路從j到k，則uk=uj+1，且避免來回重復(fù)和圈，約束條件為:uj≥uk+xkj-(n-2)(1-xkj)+(n-3)xjk，1≤k≤n，2≤j≤nj≠k；第四十六頁，共一百六十一頁，編輯于2023年，星期二最優(yōu)連線(最小生成樹)轉(zhuǎn)化為整數(shù)規(guī)劃：第四十七頁，共一百六十一頁，編輯于2023年，星期二例3假設(shè)某電力公司計(jì)劃在七個(gè)村莊之間架設(shè)電線，各村莊之間的距離如圖所示．試求出使電線總長(zhǎng)度最小的架線方案．第四十八頁，共一百六十一頁，編輯于2023年，星期二2.LINGO程序編寫LINGO程序如下：MODEL:sets:city/1..7/:u;!定義7個(gè)城市;link(city,city):dist,x;!距離矩陣和決策變量;endsetsn=@size(city);data:!dist是距離矩陣;第四十九頁，共一百六十一頁，編輯于2023年，星期二dist=034710010010030324100100430100571007210002100610045201410010071001021001001006420;!這里可改為你要解決的問題的數(shù)據(jù);enddata第五十頁，共一百六十一頁，編輯于2023年，星期二

min=@sum(link:dist*x);!目標(biāo)函數(shù);U(1)=0;@for(link:@bin(x));!定義X為0\1變量;@FOR(city(K)|K#GT#1:@sum(city(I)|I#ne#K:x(I,K))=1;@for(city(J)|J#gt#1#and#J#ne#K:

u(J)>=u(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K);););@sum(city(J)|J#GT#1:x(1,J))>=1;

@for(city(K)|K#gt#1:U(K)>=1;U(K)<=N-1-(N-2)*X(1,K););end第五十一頁，共一百六十一頁，編輯于2023年，星期二計(jì)算結(jié)果：目標(biāo)函數(shù)值(最優(yōu)連線的長(zhǎng)度)為13，最優(yōu)連線的構(gòu)成如圖所示4123567第五十二頁，共一百六十一頁，編輯于2023年，星期二§4旅行商問題第五十三頁，共一百六十一頁，編輯于2023年，星期二一、旅行商問題的基本概念旅行商問題（又稱貨郎擔(dān)問題，travelingsalesmanproblem，簡(jiǎn)稱TSP問題）是典型的組合優(yōu)化問題，并且是一個(gè)NP完全難題，其提法為：有n個(gè)城市，相互之間的旅行費(fèi)用（或距離）為已知，有一個(gè)旅行推銷商，從某個(gè)基點(diǎn)城市出發(fā)，要遍訪其余n-1個(gè)城市至少一次，最后回到出發(fā)點(diǎn)，試找出總費(fèi)用最?。ɑ蚩偮烦套疃蹋┑穆眯新肪€。稱能夠到每個(gè)城市至少一次的回路為旅行商回路，其中費(fèi)用最少者為最優(yōu)旅行商回路.

第五十四頁，共一百六十一頁，編輯于2023年，星期二在圖論中，經(jīng)過所有頂點(diǎn)恰好一次的圈（路）稱為哈密頓圈（路），簡(jiǎn)稱H圈（H路），存在H圈的圖稱為哈密頓圖，簡(jiǎn)稱H圖。旅行商問題是指在賦權(quán)圖上經(jīng)過每個(gè)頂點(diǎn)至少一次，且總長(zhǎng)度（路徑上權(quán)的總和）達(dá)到最小的閉通路。在加權(quán)的連通無向圖中，權(quán)最小的H圈簡(jiǎn)稱最優(yōu)H圈；經(jīng)過每個(gè)頂點(diǎn)至少一次且權(quán)最小的閉通路稱為最優(yōu)旅行商回路。注意：最優(yōu)H圈與最優(yōu)旅行商回路兩者是有區(qū)別的，最優(yōu)H圈只允許經(jīng)過每個(gè)頂點(diǎn)恰好一次，而最優(yōu)旅行商回路允許經(jīng)過某些頂點(diǎn)一次以上。第五十五頁，共一百六十一頁，編輯于2023年，星期二定理1在加權(quán)圖G=（V，E）中，若對(duì)任意頂點(diǎn)x,y,z（z≠x,z≠y），都滿足w(x,y)≤w(x,z)+w(y,z)（三角形的兩邊之和大于等于第三邊，稱為三角不等式），則該圖的最優(yōu)哈密頓圈也是最優(yōu)旅行商回路。對(duì)于連通的非完全賦權(quán)圖G，先求出任意兩點(diǎn)之間的最短路，然后用最短路作為每一條邊的權(quán)，構(gòu)造一個(gè)以V為頂點(diǎn)集的完全圖G’=（V，E’），容易證明，在如此構(gòu)造出來的圖G’中，各邊的權(quán)自然滿足三角不等式，故在加權(quán)圖G中尋求最優(yōu)旅行商回路的問題就可以轉(zhuǎn)化為在圖G’中尋求最優(yōu)哈密頓圈的問題。第五十六頁，共一百六十一頁，編輯于2023年，星期二尋找最優(yōu)哈密頓圈和最優(yōu)旅行商回路是圖論中的典型問題，而且是一個(gè)NP完全難題。問題的求解沒有多項(xiàng)式時(shí)間算法，除了窮舉法，目前還沒有尋找最優(yōu)解的算法，隨著頂點(diǎn)數(shù)的增加，運(yùn)算所需時(shí)間呈指數(shù)級(jí)增長(zhǎng)，當(dāng)頂點(diǎn)數(shù)較大時(shí)，求出最優(yōu)解所需時(shí)間可能是難以忍受的。可行的方法是用近似算法，力爭(zhēng)在較短時(shí)間尋找接近最優(yōu)解的近似最優(yōu)解。旅行商問題得到了許多學(xué)者的關(guān)注和長(zhǎng)期研究，提出了多種近似算法，例如分支定界法、遺傳算法、模擬退火法、蟻群算法、神經(jīng)網(wǎng)絡(luò)方法、粒子群優(yōu)化算法、重繞最小生成樹法、二次逐邊修正法等。第五十七頁，共一百六十一頁，編輯于2023年，星期二二、用LINGO求解TSP問題的方法一1.把最優(yōu)哈密頓圈問題轉(zhuǎn)化為0-1線性規(guī)劃

將任意兩點(diǎn)之間的最短路作為兩點(diǎn)之間邊的權(quán)構(gòu)造完全圖G’。引入0-1整數(shù)變量xij(且i≠j)：若xij=1則邊i-j在回路中，而xij＝0則表示否。目標(biāo)函數(shù)首先必須滿足約束條件：對(duì)每個(gè)城市訪問一次且僅一次。從城市i出發(fā)一次(到其它城市去),表示為第五十八頁，共一百六十一頁，編輯于2023年，星期二從某個(gè)城市到達(dá)j一次且僅一次，表示為：以上建立的模型類似于指派問題的模型，對(duì)TSP問題只是必要條件，并不充分。第五十九頁，共一百六十一頁，編輯于2023年，星期二例如，用圖示路線連接六個(gè)城市，滿足以上兩個(gè)約束條件，但這樣的路線出現(xiàn)了兩個(gè)子回路，兩者之間不通，不構(gòu)成整體巡回路線。為此需要考慮增加充分的約束條件以避免產(chǎn)生子巡回。下面介紹一種方法：增加變量ui,i=2,3,…,n，（它的大小可以取正整數(shù)：例如從起點(diǎn)出發(fā)所達(dá)到的城市u=2,依此類推）。312456第六十頁，共一百六十一頁，編輯于2023年，星期二附加約束條件：ui-uj+nxij≤n-1,i=1,…,n，j=2,…,n，且i≠j

。下面證明：(1)任何含子巡回的路線都必然不滿足該約束條件（不管ui如何取值）；(2)全部不含子巡回的整體巡回路線都可以滿足該約束條件（只要ui取適當(dāng)值）。用反證法證明(1),假設(shè)存在子巡回，則至少有兩個(gè)子巡回。那么（必然）至少有一個(gè)子巡回中不含起點(diǎn)城市1，如上圖中的4－5－6－4，則必有

u4-u5+n≤n-1，u5-u6+n≤n-1，u6-u4+n≤n-1，把這三個(gè)不等式加起來得到n≤n-1，不可能，故假設(shè)不能成立。而對(duì)整體巡回，因?yàn)楦郊蛹s束中j≥2,不包含起點(diǎn)城市1，故不會(huì)發(fā)生矛盾。第六十一頁，共一百六十一頁，編輯于2023年，星期二對(duì)于整體巡回路線，只要ui取適當(dāng)值，都可以滿足該約束條件：(ⅰ)對(duì)于總巡回上的邊，xij=1,ui可取訪問城市i的順序數(shù)，則必有ui-uj＝-1，約束條件ui-uj+nxij≤n-1變成：-1+n≤n-1，必然成立。(ⅱ)對(duì)于非總巡回上的邊，因?yàn)閤ij=0，約束條件ui-uj+nxij≤n-1變成-1≤n-1，肯定成立。綜上所述，該約束條件只限止子巡回，不影響其它，于是TSP問題轉(zhuǎn)化成了一個(gè)整數(shù)線性規(guī)劃問題。第六十二頁，共一百六十一頁，編輯于2023年，星期二求最優(yōu)哈密頓圈可以表示為規(guī)劃：第六十三頁，共一百六十一頁，編輯于2023年，星期二2.LINGO程序!旅行售貨員問題;model:sets:city/1..17/:u;!定義17個(gè)城市;link(city,city):dist,!距離矩陣;x;!決策變量;endsetsn=@size(city);data:!距離矩陣;第六十四頁，共一百六十一頁，編輯于2023年，星期二C=016.311.910.12812.9620.628.422.220.835.722.130.223.727.83616.3012.226.423.98.810.336.940.132.216.731.614.722.87.411.519.711.912.202236.1215.932.540.334.128.943.826.93519.617.625.810.126.422020.42316.110.518.312.115.228.132.238.433.837.946.12823.936.120.4015.1342416.28.37.27.724.31831.335.432.912.98.8212315.1018.933.531.323.47.922.89.217.316.220.328.5610.35.916.13418.9026.634.428.226.841.72533.117.721.83020.636.932.510.52433.526.607.815.725.731.742.74244.348.456.628.440.140.318.316.231.334.47.807.923.423.940.534.247.551.649.122.232.234.112.18.323.428.215.77.9015.51632.626.339.643.741.220.816.728.915.27.27.926.825.723.415.5014.917.125.224.128.236.435.731.643.828.17.722.841.731.723.91614.9018.410.325.733.425.222.114.726.932.224.39.22542.740.532.617.118.408.17.326.22330.222.83538.41817.333.14234.226.325.210.38.1015.423.114.923.77.419.633.831.316.217.744.347.539.624.125.77.315.4018.920.327.811.517.637.935.420.321.848.451.643.728.233.426.223.118.908.23619.725.846.132.928.53056.649.141.236.425.22314.920.38.20;第六十五頁，共一百六十一頁，編輯于2023年，星期二!這里可改為你要解決的問題的數(shù)據(jù);enddata!目標(biāo)函數(shù);min=@sum(link:dist*x);@FOR(city(K):

!進(jìn)入城市K;

@sum(city(I)|I#ne#K:x(I,K))=1;

!離開城市K;

@sum(city(J)|J#ne#K:x(K,J))=1;);

!保證不出現(xiàn)子圈;第六十六頁，共一百六十一頁，編輯于2023年，星期二

@for(city(I)|I#gt#1:

@for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)<=n-1););

!限制u的范圍以加速模型的求解，保證所加限制并不排除掉TSP問題的最優(yōu)解;

@for(city(I):u(I)<=n-1);

@for(link:@bin(x));!定義X為0\1變量;end第六十七頁，共一百六十一頁，編輯于2023年，星期二計(jì)算結(jié)果：目標(biāo)函數(shù)值：159.3路線：1→7→3→16→17→14→13→15→2→6→11→12→5→10→9→8→4→1因?yàn)橐陨弦?guī)劃是線性規(guī)劃，所以求解不費(fèi)時(shí)，當(dāng)頂點(diǎn)數(shù)為20－30個(gè)時(shí)，一般幾分鐘就可以得到最優(yōu)解。利用LINGO軟件的強(qiáng)大優(yōu)化能力，不必研究旅行商問題的算法，通過編寫不太復(fù)雜的LINGO程序，能夠較快地解決實(shí)際問題，達(dá)到事半功倍的效果。

第六十八頁，共一百六十一頁，編輯于2023年，星期二三、用LINGO求解TSP問題的方法二1.對(duì)城市排序，找出最優(yōu)排序在現(xiàn)實(shí)中的城市交通圖中，有些城市之間有直接道路，有些則沒有，如果兩點(diǎn)之間沒有直接的通路，則兩點(diǎn)之間的距離取最短路（經(jīng)過其它點(diǎn)），即用任意兩點(diǎn)之間的最短路Cij作為圖的距離矩陣，構(gòu)成一個(gè)完全圖G'，其任意一對(duì)頂點(diǎn)都有一條邊相連。圖G的最優(yōu)旅行商回路等價(jià)于圖G'的最優(yōu)哈密頓圈，此時(shí)形式上的環(huán)形巡回路線實(shí)際上個(gè)別點(diǎn)有可能不止經(jīng)過一次。第六十九頁，共一百六十一頁，編輯于2023年，星期二設(shè)某個(gè)城市為旅行的出發(fā)地和終點(diǎn)（相當(dāng)于總部所在地），旅行者從該城市出發(fā)到其它n個(gè)城市各一次且僅一次，最后回到出發(fā)地。我們把行進(jìn)路線分成n步，每一步到一個(gè)城市（第n+1步返回出發(fā)地），于是一條旅行路線就相當(dāng)于n個(gè)城市的一種排列，n個(gè)城市共有n!種排列方式。排序不同則總里程（或費(fèi)用）可能不同，總里程（或總費(fèi)用）最小的排序就是我們要尋找的最優(yōu)路線。第七十頁，共一百六十一頁，編輯于2023年，星期二引入0-1型決策變量Xkj，下標(biāo)k表示旅行的步數(shù)，下標(biāo)j表示到達(dá)哪一個(gè)城市，Xkj=1表示旅行者第k個(gè)目的地（到達(dá)點(diǎn)）是城市j，Xkj=0則表示否。用lj表示總部到各城市的距離，用Cij表示城市i與城市j之間的最短路。從出發(fā)地到第1個(gè)點(diǎn)的路程為從最后一個(gè)點(diǎn)返回出發(fā)地的里程為

第七十一頁，共一百六十一頁，編輯于2023年，星期二假設(shè)在第k步到達(dá)城市i，在第k+1步達(dá)到城市j，即Xki=Xk+1,j=1，則走過的里程為：

Cij·Xki·Xk+1,j從第1點(diǎn)到第n點(diǎn)走過的總里程為目標(biāo)函數(shù)為第七十二頁，共一百六十一頁，編輯于2023年，星期二約束條件有以下2條：(1)每一步到達(dá)一個(gè)城市，即(2)每一個(gè)城市必須到一次且只需一次，即第七十三頁，共一百六十一頁，編輯于2023年，星期二綜上所述，可以把最優(yōu)哈密頓圈問題轉(zhuǎn)化成如下非線性0-1

規(guī)劃第七十四頁，共一百六十一頁，編輯于2023年，星期二以上規(guī)劃中允許包含其它約束條件。用LINGO可以求解該規(guī)劃，舉例如下。某縣郵局和10個(gè)鄉(xiāng)鎮(zhèn)支局組成該縣的郵政運(yùn)輸網(wǎng)絡(luò)，已知縣局到各支局的距離和支局之間的距離矩陣（數(shù)據(jù)在程序中）。用一輛郵車完成郵件運(yùn)輸任務(wù)，郵車從縣局出發(fā)到各支局去一次且只需一次，最后回到縣局，求總路程最短的行駛路線。解：本題是“旅行商”問題?？梢杂蒙厦娼榻B的方法求解。第七十五頁，共一百六十一頁，編輯于2023年，星期二編寫LINGO程序如下：MODEL:SETS:CITY/1..10/:JL;STEP/1..10/;LINE(STEP,CITY):X;LINKS(CITY,CITY):C;ENDSETS第七十六頁，共一百六十一頁，編輯于2023年，星期二DATA:JL=71,56,27,30,28,26,15,9,30,27;C=0,15,44,47,64,83,86,75,93,98 15,0,29,32,49,68,71,60,78,83 44,29,0,20,37,53,42,31,49,54 47,32,20,0,17,36,42,39,60,57 64,49,37,17,0,19,37,37,58,55 83,68,53,36,19,0,18,35,56,47 86,71,42,42,37,18,0,24,38,29 75,60,31,39,37,35,24,0,21,26 93,78,49,60,58,56,38,21,0,29 98,83,54,57,55,47,29,26,29,0;ENDDATA第七十七頁，共一百六十一頁，編輯于2023年，星期二@FOR(LINE:@BIN(X));M1=@SIZE(STEP);@FOR(CITY(I):@SUM(STEP(N):X(N,I))=1);@FOR(STEP(N):@SUM(CITY(I):X(N,I))=1);L1=@SUM(CITY(I):(X(1,I)+X(M1,I))*JL(I));LX=@SUM(STEP(N)|N#LT#M1:@SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));MIN=L1+LX;END第七十八頁，共一百六十一頁，編輯于2023年，星期二在程序運(yùn)行前需要對(duì)LINGO的參數(shù)作必要的設(shè)置。對(duì)于非線性規(guī)劃，LINGO提供兩種求解方法，一種是“GlobalSolver”（稱為全局優(yōu)化求解器），另一種是“MultistartSolver”（稱為多起點(diǎn)算法），全局優(yōu)化求解器優(yōu)點(diǎn)是確保找到全局最優(yōu)解，缺點(diǎn)是有時(shí)需要較長(zhǎng)運(yùn)行時(shí)間。多起點(diǎn)算法的優(yōu)點(diǎn)是節(jié)省運(yùn)行時(shí)間，但不能保證找到的解就是全局最優(yōu)解，設(shè)置起點(diǎn)數(shù)多一些往往找到的解就是全局最優(yōu)解。點(diǎn)擊菜單“Options”，再打開全局優(yōu)化求解器“GlobalSolver”選項(xiàng)，可以選或不選“GlobalSolver”，當(dāng)選擇多起點(diǎn)算法“MultistartSolver”時(shí)，需要設(shè)置起點(diǎn)數(shù)，若選擇“SolverDecides”表示由LINGO決定。第七十九頁，共一百六十一頁，編輯于2023年，星期二對(duì)以上程序，我們選擇“GlobalSolver”，點(diǎn)擊菜單“Options”，在全局優(yōu)化求解器“GlobalSolver”選項(xiàng)框內(nèi)打“√”，再點(diǎn)擊“確定”。運(yùn)行以上程序，費(fèi)時(shí)4分多鐘，得到最優(yōu)解：目標(biāo)函數(shù)值（總路程）260公里郵車的行駛路線為：縣局→8→9→10→7→6→5→4→1→2→3→縣局第八十頁，共一百六十一頁，編輯于2023年，星期二四、多旅行商（MTSP）問題1.

多旅行商問題的概念在現(xiàn)實(shí)中問題中，有時(shí)候不是由一人走遍所有點(diǎn)，而是由幾個(gè)人分工合作，每個(gè)人只到其中部分城市，每個(gè)點(diǎn)都有人來過一次且只需一次，事先不指定誰到哪些點(diǎn)，求出使總路程最小的旅行規(guī)劃（每個(gè)人的行走路線）。例如郵路規(guī)劃中，為了在允許的時(shí)間內(nèi)完成郵件運(yùn)輸任務(wù)，縣局的郵車往往不止1輛，而是用若干輛郵車分工運(yùn)輸，只要保證每個(gè)支局有郵車來過即可，為了節(jié)省行駛費(fèi)用，需要規(guī)劃幾輛郵車的最佳路線。這就是多旅行商問題。第八十一頁，共一百六十一頁，編輯于2023年，星期二多旅行商問題的提法如下：有n+1個(gè)城市，相互間的路程（或旅行費(fèi)用）為已知，有k個(gè)旅行商都從總部所在城市出發(fā)，赴其它城市旅行推銷，分工遍歷其余n個(gè)城市，即每個(gè)城市各有任意一名旅行商來過一次且僅一次，最后都回到出發(fā)地，目標(biāo)是總路程最短或總費(fèi)用最省。多旅行商問題在物流配送、郵路優(yōu)化等方面具有較高的實(shí)用價(jià)值，而在現(xiàn)實(shí)問題中，研究對(duì)象往往不是單純的旅行商問題，而要考慮各種約束條件，例如時(shí)間約束、載重量約束等等。研究這一類帶約束條件的多旅行商問題具有很強(qiáng)的現(xiàn)實(shí)意義。

第八十二頁，共一百六十一頁，編輯于2023年，星期二在現(xiàn)實(shí)的多旅行商問題中，往往帶有約束條件，例如時(shí)間約束、載重量約束等等。帶約束條件的多旅行商問題具有廣泛現(xiàn)實(shí)意義，且是極具挑戰(zhàn)性的難題，我們?nèi)匀话阉D(zhuǎn)化為0-1非線性規(guī)劃并編成LINGO程序來求解。實(shí)例某縣郵政局管轄16個(gè)支局，已知縣局到各支局的距離以及16個(gè)支局之間的距離矩陣。寄達(dá)各支局和各支局收寄的郵件(袋)如下表所示：第八十三頁，共一百六十一頁，編輯于2023年，星期二縣郵局和各支局分布圖第八十四頁，共一百六十一頁，編輯于2023年，星期二每一輛郵車最多裝載65袋郵件，郵車的運(yùn)行成本為3元/公里。試用最少郵車，并規(guī)劃郵車的行駛路線使總費(fèi)用最省。分析：首先考慮最少郵車數(shù)量，由題目所給表中數(shù)據(jù)，寄達(dá)16個(gè)支局的郵件總數(shù)為176袋，從各支局收寄的郵件總數(shù)為170袋，每一輛郵車最多容納65袋郵件，至少需要176/65≈2.7輛郵車，由于郵車數(shù)量為整數(shù)，故最少需要3輛郵車。如果3輛郵車能夠完成郵件運(yùn)輸任務(wù)，則3輛車就是郵車數(shù)量的最優(yōu)解。

第八十五頁，共一百六十一頁，編輯于2023年，星期二運(yùn)輸費(fèi)用與行駛里程成正比，總里程最短對(duì)應(yīng)總費(fèi)用最省。把16個(gè)支局放在一起作為一個(gè)整體考慮，找出3條郵路，每條郵路都從縣局出發(fā)，到若干支局進(jìn)行卸裝，最后回到縣局。各郵車路過的支局?jǐn)?shù)量未知，合理安排各郵車的行駛路線，由3輛郵車分別承包運(yùn)輸，在滿足運(yùn)載量約束前提下，把3條巡回路線的總里程最小作為優(yōu)化的目標(biāo)。該問題相當(dāng)于附帶約束條件的多旅行商模型。第八十六頁，共一百六十一頁，編輯于2023年，星期二2.0-1規(guī)劃模型引入0-1型決策變量Xkj,Ykj,Zkj，分別表示3輛郵車第k步到達(dá)支局j，下標(biāo)k表示郵車行走的步數(shù)，下標(biāo)j表示到達(dá)哪一個(gè)支局，當(dāng)決策變量Xkj,Ykj,Zkj等于1時(shí)分別表示某郵車第k個(gè)裝卸點(diǎn)是支局j，等于0時(shí)表示否。設(shè)各郵車管轄的支局?jǐn)?shù)量分別為m1,m2,m3，則m1+m2+m3=16。約束條件有以下3條：(1)任何一輛車在任何一步到達(dá)一個(gè)支局

，即第八十七頁，共一百六十一頁，編輯于2023年，星期二(2)任何一個(gè)支局必須有一輛郵車到達(dá)一次且只需要一次，即

(3)在郵車行進(jìn)的任何路段上，裝載的郵件不超過65袋。

設(shè)寄達(dá)各支局的郵件量為Pj，各支局收寄的郵件量為Qj。

裝載量是動(dòng)態(tài)變化的，以第1輛郵車為例，出發(fā)時(shí)的裝載量為第八十八頁，共一百六十一頁，編輯于2023年，星期二到第1個(gè)支局卸裝以后，裝載量變?yōu)樵谛旭傔^程中，裝載量的遞推公式為約束條件為第八十九頁，共一百六十一頁，編輯于2023年，星期二綜上所述，建立多旅行商問題的0-1規(guī)劃模型如下：第九十頁，共一百六十一頁，編輯于2023年，星期二裝載量的計(jì)算公式為：第九十一頁，共一百六十一頁，編輯于2023年，星期二3.LINGO程序編寫LINGO程序如下：MODEL:SETS:STATION/1..16/:JL,P,Q;STEPX/1..6/:WX;STEPY/1..5/:WY;STEPZ/1..5/:WZ;LINEX(STEPX,STATION):X;LINEY(STEPY,STATION):Y;LINEZ(STEPZ,STATION):Z;LINKS(STATION,STATION):C;ENDSETS第九十二頁，共一百六十一頁，編輯于2023年，星期二DATA:JL=27361711243144403020252121182736;P=10,15,6,9,13,6,11,4,13,17,11,2,11,21,13,14;Q=9,14,5,10,9,10,13,9,15,9,6,7,13,15,10,16;C=031273851587167574752482141526131019332732456453476157524856632719014273447493929423838293844

3833140132033352515333232152430512727130921372626434545282938583234209013323235475252353342714547332113019303950656548444067644935373219011203154613425215753392526323011010204351241413474729152635392010018364114918

第九十三頁，共一百六十一頁，編輯于2023年，星期二

526142334347503120180234625142348573832455265544336230272233422152383245526561514146270394857414829152835483424142522390112052563824293344251491433481109616344303842402113182342572090;ENDDATA第九十四頁，共一百六十一頁，編輯于2023年，星期二@FOR(LINEX:@BIN(X));@FOR(LINEY:@BIN(Y));@FOR(LINEZ:@BIN(Z));M1=@SIZE(STEPX);M2=@SIZE(STEPY);M3=@SIZE(STEPZ);@FOR(STATION(I):@SUM(STEPX(N):X(N,I))+@SUM(STEPY(N):Y(N,I))+@SUM(STEPZ(N):Z(N,I))=1);@FOR(STEPX(N):@SUM(STATION(I):X(N,I))=1);@FOR(STEPY(N):@SUM(STATION(I):Y(N,I))=1);@FOR(STEPZ(N):@SUM(STATION(I):Z(N,I))=1);第九十五頁，共一百六十一頁，編輯于2023年，星期二WX0=@SUM(STATION(I):P*@SUM(STEPX(N):X(N,I)));WY0=@SUM(STATION(I):P*@SUM(STEPY(N):Y(N,I)));WZ0=@SUM(STATION(I):P*@SUM(STEPZ(N):Z(N,I)));WX(1)=WX0-@SUM(STATION(J):(P(J)-Q(J))*X(1,J));WY(1)=WY0-@SUM(STATION(J):(P(J)-Q(J))*Y(1,J));WZ(1)=WZ0-@SUM(STATION(J):(P(J)-Q(J))*Z(1,J));@FOR(STEPX(N)|N#GE#2:WX(N)=WX(N-1)-@SUM(STATION(J):(P(J)-Q(J))*X(N,J)));@FOR(STEPY(N)|N#GE#2:WY(N)=WY(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Y(N,J)));@FOR(STEPZ(N)|N#GE#2:WZ(N)=WZ(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Z(N,J)));WX0<=65;WY0<=65;WZ0<=65;@FOR(STEPX(N):WX(N)<=65);@FOR(STEPY(N):WY(N)<=65);第九十六頁，共一百六十一頁，編輯于2023年，星期二@FOR(STEPZ(N):WZ(N)<=65);L1=@SUM(STATION(I):(X(1,I)+X(M1,I))*JL(I));L2=@SUM(STATION(I):(Y(1,I)+Y(M2,I))*JL(I));L3=@SUM(STATION(I):(Z(1,I)+Z(M3,I))*JL(I));LX=@SUM(STEPX(N)|N#LT#M1:@SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));LY=@SUM(STEPY(N)|N#LT#M2:@SUM(LINKS(I,J):C(I,J)*Y(N,I)*Y(N+1,J)));LZ=@SUM(STEPZ(N)|N#LT#M3:@SUM(LINKS(I,J):C(I,J)*Z(N,I)*Z(N+1,J)));MIN=L1+L2+L3+LX+LY+LZ;END第九十七頁，共一百六十一頁，編輯于2023年，星期二三輛郵車各自負(fù)責(zé)的支局?jǐn)?shù)量有若干種分配方法，例如有6,5,5、6,6,4、7,5,4等不同分組法。經(jīng)過試驗(yàn)，以6,5,5方案最優(yōu)。目標(biāo)函數(shù)值（3條郵路的總里程）為343km。第一條郵路：縣局→10→9→8→7→5→6→縣局，總里程121km，沿途各段郵件的裝載量為64,56,58,63,65,61,65袋。注意：如果支局5和6的先后次序倒過來，即走7→6→5→縣局，則里程為106km，減少15km，但是在支局6卸裝以后，郵件達(dá)69袋，超過了裝載量約束，看來先到支局5，后到支局6是因?yàn)楸苊獬d的原因，被迫繞路，整體上仍然保持最優(yōu)。第九十八頁，共一百六十一頁，編輯于2023年，星期二第二條郵路：縣局→14→15→16→11→12→縣局，總里程105km，沿途各段郵件的裝載量為61,55,52,54,49,54袋。第三條郵路：縣局→13→1→2→3→4→縣局，總里程117km，沿途各段郵件的裝載量為51,53,52,51,50,51袋。第九十九頁，共一百六十一頁，編輯于2023年，星期二三條郵路的圖形如圖所示

第一百頁，共一百六十一頁，編輯于2023年，星期二§5中國(guó)郵遞員問題第一百零一頁，共一百六十一頁，編輯于2023年，星期二一、歐拉（Euler）圖

定義：設(shè)圖G={V,E}是連通無向圖，則經(jīng)過G的每邊正好一次的道路稱為歐拉道路（歐拉跡）；經(jīng)過G的每邊至少一次的閉通路稱為巡回；經(jīng)過G的每邊正好一次的巡回稱為歐拉巡回；存在歐拉巡回的圖稱為歐拉圖；定理：一個(gè)非空連通圖是歐拉圖的充分必要條件是它沒有奇點(diǎn)。推論：連通圖G能夠一筆畫出（存在歐拉跡）的充要條件是所有頂點(diǎn)是偶點(diǎn)或者僅有兩個(gè)頂點(diǎn)是奇點(diǎn)。第一百零二頁，共一百六十一頁，編輯于2023年，星期二二、中國(guó)郵遞員問題

1.概念郵遞員從郵局出發(fā)，經(jīng)過他所投遞范圍內(nèi)的每一條街道至少一次，然后返回郵局，如何安排投遞路線使總路程最短，這個(gè)問題由中國(guó)學(xué)者管梅谷于1962年首先提出并給出了一種解法，被國(guó)際上稱為中國(guó)郵遞員問題。用圖來描述投遞區(qū)域，用邊表示街道，用點(diǎn)表示路口和郵局，則投遞區(qū)構(gòu)成一個(gè)非負(fù)的賦權(quán)連通圖。中國(guó)郵遞員問題就是在一個(gè)非負(fù)的賦權(quán)連通圖中尋找一條總權(quán)最小的巡回，這種巡回稱為最優(yōu)巡回。

第一百零三頁，共一百六十一頁，編輯于2023年，星期二2．歐拉圖中的最優(yōu)巡回若圖G是歐拉圖，則G的任何一個(gè)歐拉巡回都是最優(yōu)巡回，因?yàn)闅W拉巡回是一條通過G的每一條邊恰好一次的巡回。此時(shí)可用Fleury算法來確定一個(gè)歐拉巡回。定義：設(shè)G是連通圖，邊，若從G中刪除邊e后，圖不連通，則稱邊e為圖G的割邊。定理：e是G的割邊的充要條件是e不含在G的圈中。第一百零四頁，共一百六十一頁，編輯于2023年，星期二Fleury算法的基本思想：從任一點(diǎn)出發(fā)，每當(dāng)訪問一條邊時(shí)，先進(jìn)行檢查，如果可供訪問的邊不止一條，則應(yīng)選不是未訪問邊集構(gòu)成的子圖的割邊作為訪問邊直到?jīng)]有邊可供選擇為止。Fleury算法的步驟：(1)任意選取一個(gè)頂點(diǎn)v0，令W0=v0（作為起點(diǎn)）；(2)假設(shè)道路Wi=v0e1v1e2…eivi已經(jīng)選定，則按以下方法從E\{e1,e2,…,ei}中選取一條邊ei+1：①ei+1和vi相關(guān)聯(lián)；②除非沒有別的邊可選擇，否則ei+1不是Gi=G\{e1,e2,…,ei}的割邊。③當(dāng)?shù)冖诓讲荒苓M(jìn)行時(shí)就停止。

第一百零五頁，共一百六十一頁，編輯于2023年，星期二3．非歐拉圖中的最優(yōu)巡回如果G不是歐拉圖（圖中有奇點(diǎn)），則G的任何一個(gè)巡回經(jīng)過某些（與奇點(diǎn)相關(guān)聯(lián)的）邊必定多于一次。解決這一類問題的一般方法是，引入重復(fù)邊，使原圖成為歐拉圖，并且添加的重復(fù)邊的權(quán)的總和為最小。情形1G只有兩個(gè)奇點(diǎn)u和v，求最優(yōu)巡回的算法如下：(1)用Dijkstra算法或Floyd算法求出奇點(diǎn)u和v之間的最短路徑P。(2)令G*=G∪P，則G*為歐拉圖。(3)用Fleury算法來確定一個(gè)G*的歐拉巡回，這就是G的最優(yōu)巡回。第一百零六頁，共一百六十一頁，編輯于2023年，星期二情形2

G有2n個(gè)奇點(diǎn)（n>1），可以用Edmonds算法解決，其基本思路為：首先將奇點(diǎn)配對(duì)，使配對(duì)以后各對(duì)之間距離的總和（兩點(diǎn)之間的距離按照最短路計(jì)算）達(dá)到最?。ǚQ為最佳配對(duì)）,求最佳配對(duì)的方法可以用匈牙利法或0-1規(guī)劃法等方法（可以用Lingo實(shí)現(xiàn)）。然后把每一對(duì)點(diǎn)之間的最短路作為邊添加到原圖中,使之成為歐拉圖G*，找出G*的歐拉巡回就是原圖的最佳巡回。第一百零七頁，共一百六十一頁，編輯于2023年，星期二算法步驟如下：(1)用Floyd算法求出所有奇點(diǎn)之間的最短路徑和距離矩陣。(2)用匈牙利法或0-1規(guī)劃法求出所有奇點(diǎn)之間的最佳配對(duì)。(3)在原圖上添加最佳配對(duì)所包含的兩兩頂點(diǎn)之間的最短路得到歐拉圖G*。(4)用Fleury算法確定一個(gè)G*的歐拉巡回，這就是G的最優(yōu)巡回。

第一百零八頁，共一百六十一頁，編輯于2023年，星期二三、Fleury算法的Matlab程序

設(shè)圖是連通無向圖，如果所有頂點(diǎn)都是偶點(diǎn)，則該圖是歐拉圖，必然存在歐拉巡回，如果恰好有兩個(gè)奇次頂點(diǎn)，則稱該圖為半歐拉圖，必然存在起點(diǎn)在奇點(diǎn)（兩個(gè)奇點(diǎn)中的一個(gè)）且終點(diǎn)在另一個(gè)奇點(diǎn)的歐拉道路。這兩種情況下都可用fleury算法確定一條歐拉巡回或者歐拉道路。第一百零九頁，共一百六十一頁，編輯于2023年，星期二按照fleury算法的思路編寫Matlab程序。主要程序arEuler根據(jù)圖的邊集確定是否為歐拉圖、半歐拉圖或非歐拉圖，如果是歐拉圖則用fleury算法找到一條歐拉巡回路線（歐拉圖的歐拉巡回不止一條，輸出的是其中的一條），如果是半歐拉圖則返回一條歐拉道路，其起點(diǎn)在兩個(gè)奇點(diǎn)之一，終點(diǎn)是另一個(gè)奇點(diǎn)。第一百一十頁，共一百六十一頁，編輯于2023年，星期二function[eu,cEu]=arEuler(E)%輸入?yún)?shù)E是圖的邊集（m行2列矩陣，每一行的兩個(gè)數(shù)字代表一條邊的兩個(gè)頂點(diǎn)，共有m條邊），輸出參數(shù)eu有三種結(jié)果：若為歐拉圖則eu=1；半歐拉圖則eu=0.5；否則eu=0。輸出參數(shù)cEu是m行1列矩陣，表示歐拉巡回或歐拉道路中邊的序列。eu=0;%eu的初始值為0cEu=[];%cEu開始時(shí)為空集ncV=arComp(E);%調(diào)用函數(shù)arComp確定圖的分枝構(gòu)成，判斷是否連通

第一百一十一頁，共一百六十一頁，編輯于2023年，星期二ifmax(ncV)>1,%表示有2個(gè)或以上互不連通的部分

return%不是連通圖就返回endn=max(max(E(:,1:2)));%n是圖的頂點(diǎn)總數(shù)m=size(E,1);%m是邊的總數(shù)第一百一十二頁，共一百六十一頁，編輯于2023年，星期二fori=1:n

b(i)=0;forj=1:mifE(j,1)==i|E(j,2)==ib(i)=b(i)+1;endendend%b表示各頂點(diǎn)的度數(shù)第一百一十三頁，共一百六十一頁，編輯于2023年，星期二rp=rem(b,2);%各頂點(diǎn)的度數(shù)除2取余數(shù)，偶點(diǎn)的余數(shù)為0，奇點(diǎn)的余數(shù)為1srp=sum(rp);%srp是rp的總和switchsrpcase0,%若余數(shù)的總和為0，則所有頂點(diǎn)為偶點(diǎn)，原圖是歐拉圖

eu=1;case2,%恰好有兩個(gè)奇點(diǎn)，原圖是半歐拉圖

eu=0.5;otherwise,%否則是非歐拉圖

return第一百一十四頁，共一百六十一頁，編輯于2023年，星期二end%以下程序?qū)ふ乙粭l歐拉巡回或歐拉道路

ifsrp==0,%對(duì)于歐拉圖

v1=1;%把第一個(gè)頂點(diǎn)作為歐拉巡回的起點(diǎn)

else%對(duì)于半歐拉圖

v1=find(rp);%先找出奇點(diǎn)

v1=v1(1);%把第一個(gè)奇點(diǎn)作為歐拉道路的起點(diǎn)

end第一百一十五頁，共一百六十一頁，編輯于2023年，星期二

vc=v1;%vc是