第8章 圖與網(wǎng)絡(luò)分析實(shí)驗(yàn)

第8章圖與網(wǎng)絡(luò)分析實(shí)驗(yàn)8.1基礎(chǔ)知識(shí)8.2使用Lingo軟件求解圖與網(wǎng)絡(luò)分析問(wèn)題8.3使用WinQSB軟件求解圖與網(wǎng)絡(luò)分析問(wèn)題8.4使用MATLAB軟件求解圖與網(wǎng)絡(luò)分析問(wèn)題8.1基礎(chǔ)知識(shí)圖與網(wǎng)絡(luò)分析作為運(yùn)籌學(xué)的分支，應(yīng)用范圍廣泛。其理論已成為研究經(jīng)濟(jì)管理、計(jì)算機(jī)科學(xué)、通信理論、自動(dòng)控制、系統(tǒng)控制和軍事科學(xué)等領(lǐng)域相關(guān)問(wèn)題的重要數(shù)學(xué)手段。圖論起源于1736年瑞士著名數(shù)學(xué)家歐拉（Euler）解決的哥尼斯堡七橋問(wèn)題。圖是對(duì)于實(shí)際問(wèn)題的數(shù)學(xué)抽象，由一些點(diǎn)及連接這些點(diǎn)的邊所組成。圖與網(wǎng)絡(luò)分析這一分支通過(guò)研究圖與網(wǎng)絡(luò)的性質(zhì)，結(jié)合優(yōu)化知識(shí)，解決設(shè)計(jì)與管理中的實(shí)際問(wèn)題。圖的基本概念無(wú)向圖：如果圖G是由點(diǎn)和邊（兩點(diǎn)之間的不帶箭頭的連線(xiàn)）所構(gòu)成的。有向圖：如果圖G是由點(diǎn)和?。▋牲c(diǎn)之間用箭頭表示方向的連線(xiàn)）所構(gòu)成的。簡(jiǎn)單圖：無(wú)環(huán)（邊e的兩個(gè)端點(diǎn)相重）、無(wú)多重邊（兩點(diǎn)之間的邊多于一條）的圖。鏈：圖G中一個(gè)以點(diǎn)和邊交替的序列,若滿(mǎn)足,

則稱(chēng)之為G中一條連接點(diǎn)和點(diǎn)的鏈。若點(diǎn)與點(diǎn)相同，則稱(chēng)為圈。連通圖：圖G中任意兩點(diǎn)之間至少有一條鏈，則稱(chēng)為連通圖?；芈罚簣DG中的一條鏈，對(duì)

均有弧，則稱(chēng)之為從點(diǎn)到點(diǎn)的一條

路；若點(diǎn)與點(diǎn)相同，則稱(chēng)為回路。若回路中的各點(diǎn)都不相同，則稱(chēng)為初等路。支撐子圖：給定一個(gè)圖G=(V,E)，如果圖G?=(V?,E?)，使V=V?及

，則稱(chēng)圖G?是圖G

的一個(gè)支撐子圖。樹(shù)：無(wú)圈的連通圖稱(chēng)為樹(shù)；樹(shù)的各條邊稱(chēng)為樹(shù)枝。支撐樹(shù)：圖T=(V,E?)是圖G=(V,E)的支撐子圖，如果圖T=(V,E?)同時(shí)是樹(shù)圖，則稱(chēng)圖T是圖

G的一個(gè)支撐樹(shù)。最小支撐樹(shù)問(wèn)題及求解方法最小支撐樹(shù)：樹(shù)枝權(quán)重總和最小的支撐樹(shù)，稱(chēng)為最小支撐樹(shù)。求解方法：破圈法：在賦權(quán)連通圖G中任選一個(gè)圈，從圈中去掉一條權(quán)重最大的邊，在余下的圖中重復(fù)上述過(guò)程，直到圖中沒(méi)有圈為止。避圈法（Kruskal

算法）：在賦權(quán)連通圖G中選擇一條權(quán)重最小的邊，之后從剩余的邊中再選擇權(quán)重最小的邊，要求所選的邊與已選的邊不構(gòu)成圈，重復(fù)上述步驟，直到選不出這樣的邊為止。最短路徑問(wèn)題及求解方法最短路徑問(wèn)題給定一個(gè)賦權(quán)有向圖D=(V,A)，為弧

的權(quán)重，設(shè)P是圖D中從點(diǎn)

到點(diǎn)

的一條路，定義路P的權(quán)重w(P)為路P中所有弧的權(quán)重之和。則最短路徑問(wèn)題是指從點(diǎn)

到點(diǎn)

的所有路中，找一條權(quán)重最小的路，即

，稱(chēng)

為從點(diǎn)

到點(diǎn)

的最短路徑。最短路徑問(wèn)題的求解方法(Dijkstra算法)（1）標(biāo)注；（2）找出與點(diǎn)

相鄰的點(diǎn)中距離最小的一個(gè)點(diǎn)，標(biāo)注；（3）從已標(biāo)號(hào)的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)，標(biāo)注；（4）重復(fù)步驟（3），直到點(diǎn)

被標(biāo)號(hào)為止。網(wǎng)絡(luò)最大流問(wèn)題及求解方法網(wǎng)絡(luò)最大流問(wèn)題指的是在給定網(wǎng)絡(luò)D上找出流量v(f)為最大的一個(gè)可行流。網(wǎng)絡(luò)最大流問(wèn)題的求解方法（Ford-Fulkerson算法）（1）從點(diǎn)開(kāi)始標(biāo)號(hào)。逐段檢查從一個(gè)標(biāo)號(hào)但未檢查點(diǎn)到相鄰的未標(biāo)號(hào)點(diǎn)的弧上的流量：①若在弧上有，給標(biāo)號(hào)，成為標(biāo)號(hào)且已檢查點(diǎn)；②若在弧上有，給標(biāo)號(hào)，成為標(biāo)號(hào)且已檢查點(diǎn)；重復(fù)上述步驟，當(dāng)點(diǎn)被標(biāo)號(hào)，表明得到一條從點(diǎn)到點(diǎn)的增廣鏈，轉(zhuǎn)入第②步調(diào)整過(guò)程。若所有標(biāo)號(hào)都是已檢查過(guò)的，而標(biāo)號(hào)過(guò)程進(jìn)行不下去，則算法結(jié)束。（2）按點(diǎn)及其第一個(gè)標(biāo)號(hào)，用反向追蹤的方法，找出增廣鏈。最小費(fèi)用最大流問(wèn)題及求解方法最小費(fèi)用最大流問(wèn)題給定網(wǎng)絡(luò)D=(V,A,C)，已知每一條弧的容量和單位流量費(fèi)用，尋找一個(gè)最大流f

，使流的總輸送費(fèi)用最小。最小費(fèi)用最大流問(wèn)題的求解方法（1）從可行流開(kāi)始，通常在第步得到最小費(fèi)用流。（2）構(gòu)造賦權(quán)有向圖，在中尋求從點(diǎn)到點(diǎn)

的最短路徑。（3）若不存在最短路徑，則為最小費(fèi)用最大流；若存在最短路徑，則在原網(wǎng)絡(luò)D中得到相應(yīng)的增廣鏈。（4）在增廣鏈上對(duì)做流量調(diào)整，可得新的可行流，再對(duì)進(jìn)行步驟（2）的操作。旅行商問(wèn)題及求解方法旅行商問(wèn)題旅行商問(wèn)題是從給定的賦權(quán)圖中找出一個(gè)最小權(quán)(Hamilton圈)的問(wèn)題。Hamilton圈指的是包含圖G的每個(gè)頂點(diǎn)的圈。旅行商問(wèn)題的求解方法旅行商問(wèn)題可以寫(xiě)成整數(shù)規(guī)劃問(wèn)題：8.2使用Lingo軟件求解圖與網(wǎng)絡(luò)分析問(wèn)題例8.1用Lingo軟件求解所示網(wǎng)絡(luò)圖的最小支撐樹(shù)。model:sets:node/1..5/:v;edge(node,node):d,x;endsetsdata:d=0129999999999105299999250179999921069999999999760;enddata（1）打開(kāi)Lingo軟件，在編輯窗口中輸入下列代碼：N=@size(node);min=@sum(edge:d*x);@for(node(k)|k#gt#1:@sum(node(i)|i#ne#k:x(i,k))=1;@for(node(j)|j#gt#1#and#j#ne#k:v(j)>=v(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k);););@sum(node(j)|j#gt#1:x(1,j))>=1;@for(edge:@bin(x););@for(node(k)|k#gt#1:@bnd(1,v(k),99999);v(k)<=n-1-(n-2)*x(1,k););end（2）單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到結(jié)果。由求解結(jié)果可知，最小支撐樹(shù)由邊(v1,v2)、(v2,v4)、(v4,v3)、(v4,v5)組成，最小支撐樹(shù)的總長(zhǎng)為10。該問(wèn)題中有30個(gè)變量，而最優(yōu)解中只有其中的4個(gè)變量取非零值。從求解結(jié)果中尋找非零值較困難。我們可以選擇“LINGO”→“Solution”菜單命令彈出對(duì)話(huà)框，在“Attribute(s)orRowName(s)”下拉列表中選擇變量X，勾選“NonzeroVarsandBindingRowsOnly”復(fù)選框，然后單擊“OK”按鈕，則解報(bào)告中只顯示非零值最優(yōu)解。例8.2用Lingo軟件求解所示的從點(diǎn)s到點(diǎn)t的最小費(fèi)用最大流。（1）在編輯窗口中輸入下列代碼：model:sets:node/s,v1,v2,v3,t/:d;edge(node,node)/s,v1s,v2v1,v3v1,tv2,v1v2,v3v3,t/:b,c,f;endsetsdata:d=11000-11;b=4161232;c=108275104;enddatamin=@sum(edge:b*f);@for(node(i)|i#ne#1#and#i#ne#@size(node):@sum(edge(i,j):f(i,j))-@sum(edge(j,i):f(j,i))=d(i));@sum(edge(i,j)|i#eq#1:f(i,j))=d(1);@for(edge:@bnd(0,f,c));end（2）單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到結(jié)果。由求解結(jié)果可知，(s,v1)的流量為3，(s,v2)的流量為8，(v1,v3)的流量為0，(v1,t)的流量為7，(v2,v1)的流量為4，(v2,v3)的流量為4，(v3,t)的流量為4。最小費(fèi)用為55。例8.3（旅行商問(wèn)題）一位游客從A城市出發(fā)，去往B、C、D和E四個(gè)城市旅游，最后返回A城市，各城市之間的距離如表所示。問(wèn)該游客如何安排出游路線(xiàn)可以使總行程最短？各城市之間的距離單位：km（1）在編輯窗口中輸入下列代碼：model:sets:city/A,B,C,D,E/:c;line(city,city):d,x;endsetsdata:d=013517768130607067516005736777057020686736200;enddatan=@size(city);min=@sum(line:d*x);@for(city(k):@sum(city(i)|i#ne#k:x(i,k))=1;@sum(city(j)|j#ne#k:x(k,j))=1;);@for(line(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:c(i)-c(j)+n*x(i,j)<=n-1);@for(line:@bin(x));end（2）單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到結(jié)果。（3）選擇“LINGO”→“Solution”菜單命令，彈出對(duì)話(huà)框，在“Attribute(s)orRowName(s)”下拉列表中選擇變量X，勾選“NonzeroVarsandBindingRowsOnly”復(fù)選框，然后單擊“OK”按鈕，顯示非零值解。8.3使用WinQSB軟件求解圖與網(wǎng)絡(luò)分析問(wèn)題用WinQSB軟件求解圖與網(wǎng)絡(luò)分析問(wèn)題時(shí)，需要調(diào)用“NetworkModeling”模塊，該模塊中有七個(gè)子塊，能求解網(wǎng)絡(luò)流問(wèn)題、運(yùn)輸問(wèn)題、分配問(wèn)題、最短路徑問(wèn)題、最大流問(wèn)題、最小支撐樹(shù)問(wèn)題和旅行商問(wèn)題。WinQSB軟件求解網(wǎng)絡(luò)模型是基于表格的建模方式，且可以在圖上顯示求解結(jié)果（圖形解）。例8.4用WinQSB軟件求解所示網(wǎng)絡(luò)圖的最小支撐樹(shù)。（1）選擇“開(kāi)始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話(huà)框，選擇問(wèn)題的類(lèi)型，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話(huà)框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入節(jié)點(diǎn)間權(quán)重。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，得到結(jié)果。（4）選擇“Results”→“GraphicSolution”菜單命令，得到例8.4的最小支撐樹(shù)的網(wǎng)絡(luò)圖。由求解結(jié)果可知，最小支撐樹(shù)由邊(A,B)，(B,C)，(C,E)，(D,E)，(D,F)組成，最小支撐樹(shù)的總長(zhǎng)為15。例8.5用WinQSB軟件求解下圖從點(diǎn)到點(diǎn)的最短路徑。（1）選擇“開(kāi)始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話(huà)框，選擇問(wèn)題的類(lèi)型，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話(huà)框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入節(jié)點(diǎn)間權(quán)重。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話(huà)框，選擇求解最短距離的起、訖點(diǎn)。（4）單擊“Solve”按鈕，得到結(jié)果。（5）選擇“Results”→“GraphicSolution”菜單命令，顯示點(diǎn)v1到各點(diǎn)的最短路徑的網(wǎng)絡(luò)圖。由求解結(jié)果可知，點(diǎn)v1到點(diǎn)v9的最短路徑為v1→v3→v6→v5→v9，最短距離是14。例8.6用WinQSB軟件求解下圖的網(wǎng)絡(luò)最大流。（1）選擇“開(kāi)始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話(huà)框，選擇問(wèn)題的類(lèi)型，輸入問(wèn)題的標(biāo)題和節(jié)點(diǎn)數(shù)，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話(huà)框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入各邊容量。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話(huà)框，選擇出發(fā)點(diǎn)和終點(diǎn)。（4）單擊“Solve”按鈕，得到結(jié)果。（5）選擇“Results”→“GraphicSolution”菜單命令，顯示點(diǎn)s到點(diǎn)t的最大流量。由求解結(jié)果可知，(s,v1)的流量為7，(s,v2)的流量為7，(v1,v2)的流量為2，(v1,v3)的流量為5，(v2,v4)的流量為9，(v3,t)的流量為5，(v4,t)的流量為9，最大流量為14。例8.7（旅行商問(wèn)題）一位游客從A城市出發(fā)，去往B、C、D和E四個(gè)城市旅游，最后返回A城市，各城市之間的距離如表所示。問(wèn)該游客如何安排出游路線(xiàn)可以使總行程最短，

用WinQSB軟件求解。各城市之間的距離單位：km

（1）選擇“開(kāi)始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話(huà)框，選擇問(wèn)題的類(lèi)型，輸入問(wèn)題的標(biāo)題和城市個(gè)數(shù)，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話(huà)框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入各城市之間的距離。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話(huà)框，選擇求解模型方法。（4）單擊“Solve”按鈕，得到結(jié)果。（5）選擇“Results”→“GraphicSolution”菜單命令，顯示該游客出游的最短路線(xiàn)的圖形。由求解結(jié)果可知該游客出游的最短路線(xiàn)為A→C→E→D→B→A，總行程為190km。8.4使用MATLAB軟件求解圖與網(wǎng)絡(luò)分析問(wèn)題對(duì)于求解圖與網(wǎng)絡(luò)分析問(wèn)題，MATLAB軟件優(yōu)化工具箱也沒(méi)有提供相應(yīng)的可直接調(diào)用的函數(shù)。本節(jié)通過(guò)編程用Kruskal算法求解最小支撐樹(shù)問(wèn)題；用Dijkstra算法求解最短路徑問(wèn)題；用Ford-Fulkerson算法求解網(wǎng)絡(luò)最大流問(wèn)題。例8.8用MATLAB軟件求所示網(wǎng)絡(luò)圖的最小支撐樹(shù)。（1）創(chuàng)建一個(gè)新的“.m”文件，在編輯窗口中輸入下列代碼：function[x,f]=NETPexample1()b=[112233445;233445566;561572344];[B,i]=sortrows(b',3);B=B';m=size(b,2);n=6;t=1:n;k=0;T=[];c=0;fori=1:mift(B(1,i))~=t(B(2,i))k=k+1;T(k,1:2)=B(1:2,i);c=c+B(3,i);tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2