第8章 圖與網(wǎng)絡分析實驗

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

則稱之為G中一條連接點和點的鏈。若點與點相同，則稱為圈。連通圖：圖G中任意兩點之間至少有一條鏈，則稱為連通圖?；芈罚簣DG中的一條鏈，對

均有弧，則稱之為從點到點的一條

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

，則稱圖G?是圖G

的一個支撐子圖。樹：無圈的連通圖稱為樹；樹的各條邊稱為樹枝。支撐樹：圖T=(V,E?)是圖G=(V,E)的支撐子圖，如果圖T=(V,E?)同時是樹圖，則稱圖T是圖

G的一個支撐樹。最小支撐樹問題及求解方法最小支撐樹：樹枝權重總和最小的支撐樹，稱為最小支撐樹。求解方法：破圈法：在賦權連通圖G中任選一個圈，從圈中去掉一條權重最大的邊，在余下的圖中重復上述過程，直到圖中沒有圈為止。避圈法（Kruskal

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

的權重，設P是圖D中從點

到點

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

到點

的所有路中，找一條權重最小的路，即

，稱

為從點

到點

的最短路徑。最短路徑問題的求解方法(Dijkstra算法)（1）標注；（2）找出與點

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

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

，使流的總輸送費用最小。最小費用最大流問題的求解方法（1）從可行流開始，通常在第步得到最小費用流。（2）構造賦權有向圖，在中尋求從點到點

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

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

（1）選擇“開始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對話框，選擇問題的類型，輸入問題的標題和城市個數(shù)，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對話框，更改節(jié)點名，單擊“OK”按鈕，輸入各城市之間的距離。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對話框，選擇求解模型方法。（4）單擊“Solve”按鈕，得到結果。（5）選擇“Results”→“GraphicSolution”菜單命令，顯示該游客出游的最短路線的圖形。由求解結果可知該游客出游的最短路線為A→C→E→D→B→A，總行程為190km。8.4使用MATLAB軟件求解圖與網(wǎng)絡分析問題對于求解圖與網(wǎng)絡分析問題，MATLAB軟件優(yōu)化工具箱也沒有提供相應的可直接調(diào)用的函數(shù)。本節(jié)通過編程用Kruskal算法求解最小支撐樹問題；用Dijkstra算法求解最短路徑問題；用Ford-Fulkerson算法求解網(wǎng)絡最大流問題。例8.8用MATLAB軟件求所示網(wǎng)絡圖的最小支撐樹。（1）創(chuàng)建一個新的“.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