图与网络分析---最大流问题

图与网络分析(GraphTheoryandNetworkAnalysis)赵芳玲图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。图与网络分析(GraphTheoryandNetworkAnalysis)图的基本知识最短路问题树及最小生成树最大流问题最小费用最大流问题四、最大流问题（一）、基本概念1、网络：设一个赋权有向图D=（V,A）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）∈A,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C，Vs，Vt）。2、流量、可行流、流出量、流入量：（1）流量：是指定义在网络D上的每一条弧上的一个函数其中f(vi,vj)=fij叫做弧(vi，vj)上的流量。}{),()(jijifvvfaf（2）可行流：称满足下列条件的流为可行流：1）容量约束：对于每一个弧（vi,vj）∈A有0fijcij。2）守恒条件：对于所用的中间点),{tsvvVv有EvvEvvijjijiijff),(),(顶点vi的流入量顶点vi的流出量则称f为D上的可行流。其流量v(f)为EvvEvvsjjsjssjfffv),(),()(EvvjtEvvtjjttjfffv),(),()((发点vs)(收点vt)（5）零流弧：fij＝0的弧叫做零流弧。（6）非零流弧：fij＞0的弧为非零流弧。（3）饱和弧：可行流中fij＝cij的弧叫做饱和弧。（4）非饱和弧：可行流中fij＜cij的弧叫做非饱和弧。2vsv3v4v5v6vtv13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)例6下图给出一个可行流（容量约束、守恒条件）2vsv3v4v5v6vtv13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图中为零流弧，其余为非饱和弧、非零流弧。),(63vv例7下图给出一个可行流流量v(f)=8最大流•网络上的流量最大的可行流称作的最大流•所谓最大流问题就是求给定网络的最大流（二）最大流的算法1、由图编写程序2、由lingo8.0软件求最大流例8现需要将城市s的石油通过管道运送到城市t,中间有4个中转站v1,v2,v3和v4，城市与中转站的连接以及管道的容量如下图所示，求从城市s到城市t的最大流295v1v2v3v4st8796510295v1v2v3v4st8796510附程序MODEL:sets:nodes/s,1,2,3,4,t/;arcs(nodes,nodes)/s,1s,21,21,32,43,23,t4,34,t/:c,f;endsetsdata:c=8759925610;enddatamax=flow;@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)|i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));ENDAi,j,cfs,ti,tivsi,vffvijijffAj,iVjjiAi,jVjijf)(00,t.smax)()(程序结构1、集合定义部分（sets到endsets)2、数据输入部分（data到enddata)3、其他部分（优化目标和约束）Globaloptimalsolutionfoundatiteration:6Objectivevalue:14.00000VariableValueReducedCostFLOW14.000000.000000C(S,1)8.0000000.000000C(S,2)7.0000000.000000C(1,2)5.0000000.000000C(1,3)9.0000000.000000C(2,4)9.0000000.000000C(3,2)2.0000000.000000C(3,T)5.0000000.000000C(4,3)6.0000000.000000C(4,T)10.000000.000000F(S,1)7.0000000.000000F(S,2)7.0000000.000000F(1,2)2.0000000.000000F(1,3)5.0000000.000000F(2,4)9.000000-1.000000F(3,2)0.0000000.000000F(3,T)5.000000-1.000000F(4,3)0.0000001.000000F(4,T)9.0000000.000000Globaloptimalsolutionfoundatiteration:6Objectivevalue:14.00000VariableValueReducedCostFLOW14.000000.000000F(S,1)7.0000000.000000F(S,2)7.0000000.000000F(1,2)2.0000000.000000F(1,3)5.0000000.000000F(2,4)9.000000-1.000000F(3,2)0.0000000.000000F(3,T)5.000000-1.000000F(4,3)0.0000001.000000F(4,T)9.0000000.000000(2,0)(9,5)(5,2)v1v2v3v4st(8,7)(7,7)(9,9)(6,0)(5,5)(10,9)例9求右图中网络D的最大流。sets:nodes/s,1,2,3,t/;arcs(nodes,nodes)/s,1s,2s,31,21,t2,32,t3,t/:c,f;endsetsdata:c=57857467;enddatamax=flow;@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)|i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));ENDGlobaloptimalsolutionfoundatiteration:5Objectivevalue:18.00000VariableValueReducedCostFLOW18.000000.000000C(S,1)5.0000000.000000C(S,2)7.0000000.000000C(S,3)8.0000000.000000C(1,2)5.0000000.000000C(1,T)7.0000000.000000C(2,3)4.0000000.000000C(2,T)6.0000000.000000C(3,T)7.0000000.000000F(S,1)5.000000-1.000000F(S,2)6.0000000.000000F(S,3)7.0000000.000000F(1,2)0.0000001.000000F(1,T)5.0000000.000000F(2,3)0.0000000.000000F(2,T)6.000000-1.000000F(3,T)7.000000-1.000000F(S,1)5.000000-1.00000F(S,2)6.0000000.000000F(S,3)7.0000000.00000F(1,2)0.0000001.000000F(1,T)5.0000000.000000F(2,3)0.0000000.000000F(2,T)6.000000-1.000000F(3,T)7.000000-1.000000FLOW18.00000例10（多发点多收点网络的最大流问题）某种物资有两个产地s1和s2，三个销地，t1,t2和t3。运输系统如图7-18所示，其中v1和v2是两个中转站。所标数字是线路的最大运输能力。求从产地到销地的最大运输量。解这是一个多发点多收点的网络。为了能够用前面介绍的算法求它的最大流,需要把它化成只有一个发点和一个收点的网络.这并不困难.在网络中添一个发点vs和一个收点vt以及vs到s1,s2的弧,t1,t2,t3到vt弧．sets:nodes/vs,s1,s2,v1,v2,t1,t2,t3,vt/;arcs(nodes,nodes)/vs,s1vs,s2s1,t1s1,v1s1,v2s2,v2s2,t3v1,t1v1,t2v2,v1v2,t2v2,t3t1,vtt2,vtt3,vt/:c,f;endsetsdata:c=2727105121512863610181222;enddatamax=flow;@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)|i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));ENDGlobaloptimalsolutionfoundatiteration:10Objectivevalue:46.00000VariableValueReducedCostFLOW46.000000.000000F(VS,S1)19.000000.000000F(VS,S2)27.000000.000000F(S1,T1)10.00000-1.000000F(S1,V1)5.000000-1.000000F(S1,V2)4.0000000.000000F(S2,V2)15.000000.000000F(S2,T3)12.000000.000000F(V1,T1)8.0000000.000000F(V1,T2)0.0000000.000000F(V2,V1)3.000000-1.000000F(V2,T2)6.000000-1.000000F(V2,T3)10.000000.000000F(T1,VT)18.000000.000000F(T2,VT)6.0000000.000000F(T3,VT)22.00000-1.000000这个运输系统的最大运量为４６练习：求下图网络的最大流，最大流的流量和最小截集。图中弧旁的数字是弧的容量。20)()(maxfva36)()(maxfvb2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图csets:nodes/v1,v2,v3,v4,v5,v6,v7/;arcs(nodes,nodes)/v1,v2v1,v3v2,v5v2,v4v3,v2v3,v4v3,v6v4,v5v4,v7v4,v6v5,v7v6,v7/:c,f;endsetsdata:c=13956455544910;enddatamax=flow;@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)|i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));END2v1v3v4v5v6v7v13(11)9(9)4(0)5(5)6(6)5(4)5(4)