第8章 图与网络分析实验

第8章图与网络分析实验8.1基础知识8.2使用Lingo软件求解图与网络分析问题8.3使用WinQSB软件求解图与网络分析问题8.4使用MATLAB软件求解图与网络分析问题8.1基础知识图与网络分析作为运筹学的分支，应用范围广泛。其理论已成为研究经济管理、计算机科学、通信理论、自动控制、系统控制和军事科学等领域相关问题的重要数学手段。图论起源于1736年瑞士著名数学家欧拉（Euler）解决的哥尼斯堡七桥问题。图是对于实际问题的数学抽象，由一些点及连接这些点的边所组成。图与网络分析这一分支通过研究图与网络的性质，结合优化知识，解决设计与管理中的实际问题。图的基本概念无向图：如果图G是由点和边（两点之间的不带箭头的连线）所构成的。有向图：如果图G是由点和弧（两点之间用箭头表示方向的连线）所构成的。简单图：无环（边e的两个端点相重）、无多重边（两点之间的边多于一条）的图。链：图G中一个以点和边交替的序列,若满足,

则称之为G中一条连接点和点的链。若点与点相同，则称为圈。连通图：图G中任意两点之间至少有一条链，则称为连通图。回路：图G中的一条链，对

均有弧，则称之为从点到点的一条

路；若点与点相同，则称为回路。若回路中的各点都不相同，则称为初等路。支撑子图：给定一个图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）从已标号的点出发，找出与这些点相邻的所有未标号点，标注；（4）重复步骤（3），直到点

被标号为止。网络最大流问题及求解方法网络最大流问题指的是在给定网络D上找出流量v(f)为最大的一个可行流。网络最大流问题的求解方法（Ford-Fulkerson算法）（1）从点开始标号。逐段检查从一个标号但未检查点到相邻的未标号点的弧上的流量：①若在弧上有，给标号，成为标号且已检查点；②若在弧上有，给标号，成为标号且已检查点；重复上述步骤，当点被标号，表明得到一条从点到点的增广链，转入第②步调整过程。若所有标号都是已检查过的，而标号过程进行不下去，则算法结束。（2）按点及其第一个标号，用反向追踪的方法，找出增广链。最小费用最大流问题及求解方法最小费用最大流问题给定网络D=(V,A,C)，已知每一条弧的容量和单位流量费用，寻找一个最大流f

，使流的总输送费用最小。最小费用最大流问题的求解方法（1）从可行流开始，通常在第步得到最小费用流。（2）构造赋权有向图，在中寻求从点到点

的最短路径。（3）若不存在最短路径，则为最小费用最大流；若存在最短路径，则在原网络D中得到相应的增广链。（4）在增广链上对做流量调整，可得新的可行流，再对进行步骤（2）的操作。旅行商问题及求解方法旅行商问题旅行商问题是从给定的赋权图中找出一个最小权(Hamilton圈)的问题。Hamilton圈指的是包含图G的每个顶点的圈。旅行商问题的求解方法旅行商问题可以写成整数规划问题：8.2使用Lingo软件求解图与网络分析问题例8.1用Lingo软件求解所示网络图的最小支撑树。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个变量，而最优解中只有其中的4个变量取非零值。从求解结果中寻找非零值较困难。我们可以选择“LINGO”→“Solution”菜单命令弹出对话框，在“Attribute(s)orRowName(s)”下拉列表中选择变量X，勾选“NonzeroVarsandBindingRowsOnly”复选框，然后单击“OK”按钮，则解报告中只显示非零值最优解。例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城市出发，去往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软件求解图与网络分析问题用WinQSB软件求解图与网络分析问题时，需要调用“NetworkModeling”模块，该模块中有七个子块，能求解网络流问题、运输问题、分配问题、最短路径问题、最大流问题、最小支撑树问题和旅行商问题。WinQSB软件求解网络模型是基于表格的建模方式，且可以在图上显示求解结果（图形解）。例8.4用WinQSB软件求解所示网络图的最小支撑树。（1）选择“开始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜单命令，生成对话框，选择问题的类型，单击“OK”按钮。（2）选择“Edit”→“NodeNames”菜单命令，弹出对话框，更改节点名，单击“OK”按钮，输入节点间权重。（3）选择“SolveandAnalyze”→“SolvetheProblem”菜单命令，得到结果。（4）选择“Results”→“GraphicSolution”菜单命令，得到例8.4的最小支撑树的网络图。由求解结果可知，最小支撑树由边(A,B)，(B,C)，(C,E)，(D,E)，(D,F)组成，最小支撑树的总长为15。例8.5用WinQSB软件求解下图从点到点的最短路径。（1）选择“开始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜单命令，生成对话框，选择问题的类型，单击“OK”按钮。（2）选择“Edit”→“NodeNames”菜单命令，弹出对话框，更改节点名，单击“OK”按钮，输入节点间权重。（3）选择“SolveandAnalyze”→“SolvetheProblem”菜单命令，弹出对话框，选择求解最短距离的起、讫点。（4）单击“Solve”按钮，得到结果。（5）选择“Results”→“GraphicSolution”菜单命令，显示点v1到各点的最短路径的网络图。由求解结果可知，点v1到点v9的最短路径为v1→v3→v6→v5→v9，最短距离是14。例8.6用WinQSB软件求解下图的网络最大流。（1）选择“开始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜单命令，生成对话框，选择问题的类型，输入问题的标题和节点数，单击“OK”按钮。（2）选择“Edit”→“NodeNames”菜单命令，弹出对话框，更改节点名，单击“OK”按钮，输入各边容量。（3）选择“SolveandAnalyze”→“SolvetheProblem”菜单命令，弹出对话框，选择出发点和终点。（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城市出发，去往B、C、D和E四个城市旅游，最后返回A城市，各城市之间的距离如表所示。问该游客如何安排出游路线可以使总行程最短，

用WinQSB软件求解。各城市之间的距离单位：km

（1）选择“开始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜单命令，生成对话框，选择问题的类型，输入问题的标题和城市个数，单击“OK”按钮。（2）选择“Edit”→“NodeNames”菜单命令，弹出对话框，更改节点名，单击“OK”按钮，输入各城市之间的距离。（3）选择“SolveandAnalyze”→“SolvetheProblem”菜单命令，弹出对话框，选择求解模型方法。（4）单击“Solve”按钮，得到结果。（5）选择“Results”→“GraphicSolution”菜单命令，显示该游客出游的最短路线的图形。由求解结果可知该游客出游的最短路线为A→C→E→D→B→A，总行程为190km。8.4使用MATLAB软件求解图与网络分析问题对于求解图与网络分析问题，MATLAB软件优化工具箱也没有提供相应的可直接调用的函数。本节通过编程用Kruskal算法求解最小支撑树问题；用Dijkstra算法求解最短路径问题；用Ford-Fulkerson算法求解网络最大流问题。例8.8用MATLAB软件求所示网络图的最小支撑树。（1）创建一个新的“.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