资源描述：
《图与网络分析 (Graph Theory and Network Analysis).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图与网络分析(GraphTheoryandNetworkAnalysis)赵芳玲图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。图与
2、网络分析(GraphTheoryandNetworkAnalysis)图的基本知识最短路问题树及最小生成树最大流问题最小费用最大流问题第五节最小费用最大流问题在考虑一个运输系统中的运输量的同时，往往还要考虑运输费用，希望给出从发货站到收货站的运输量最大、费用最小的运输方案。这就是最小费用最大流问题。一、最小费用最大流的基本概念1、单位流量费用设是一个网络，对于每一条弧，除容量外，还给定一个数，称作弧上的单位流量费用。2、带费用的网络规定了费用的网络称作带费用的网络，记作，其中是顶点集合，是弧集合，
3、是容量集合，是费用函数，为发点，为收点。设是上的可行流，称为可行流的费用。3、可行流的费用4、流量为v的最小费用流把D上所有流量等于v的可行流中费用最小的可行流称作流量为v的最小费用流。5、最小费用最大流当是中最大流的流量时，流量为的最小费用流称作最小费用最大流。所谓最小费用最大流问题（minimalcost–maximalflowproblem）是求给定带费用的网络上的最小费用最大流。二、最小费用最大流的求法1、由图编写程序2、由lingo8.0软件求最小费用最大流例11现需要将城市s的石油通过
4、管道运送到城市t,中间有4个中转站v1,v2,v3和v4。由于输油管道的长短不一或地质等原因，使每条管道上运输费用也不相同。城市与中转站的连接以及管道的容量、单位运费如下图所示，求从城市s到城市t的最小费最大流。(2,1)(9,2)(5,5)v1v2v3v4st(8,2)(7,8)(9,3)(6,4)(5,6)(10,7)附程序MODEL:sets:nodes/s,1,2,3,4,t/:d;arcs(nodes,nodes)/s,1s,21,21,32,43,23,t4,34,t/:b,c,f;e
5、ndsetsdata:d=140000-14;b=285231647;c=8759925610;enddatamin=@sum(arcs:b*f);@for(nodes(i)
6、i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i));@sum(arcs(i,j)
7、i#eq#1:f(i,j))=d(1);@for(arcs:@bnd(0,f,c));ENDGlobaloptimalsolution
8、foundatiteration:3Objectivevalue:205.0000VariableValueReducedCostF(S,1)8.000000-1.000000F(S,2)6.0000000.000000F(1,2)1.0000000.000000F(1,3)7.0000000.000000F(2,4)9.0000000.000000F(3,2)2.000000-2.000000F(3,T)5.000000-7.000000F(4,3)0.00000010.00000F(4,T)9
9、.0000000.000000(2,2)(9,7)(5,1)v1v2v3v4st(8,8)(7,6)(9,9)(6,0)(5,5)(10,9)例12求下图带费用的网络D中VS到VT的最小费用最大流。图中弧旁的数字是bij,cij。解1、先求其最大流MODEL:sets:nodes/s,1,2,3,t/;arcs(nodes,nodes)/s,1s,2s,31,t2,12,t2,33,t/:c,f;endsetsdata:c=151510105101010;enddatamax=flow;@for(
10、nodes(i)
11、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)
12、i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));ENDGlobaloptimalsolutionfoundatiteration:4Objectivevalue:30.00000F(S,1)10.000000.000000F(S,2)10.00
