图与网络分析 (Graph Theory and Network Analysis).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图与网络分析,(,Graph Theory and Network Analysis),赵芳玲,图论是运筹学的一个重要分支，它是建立和处理,离散类,数学模型的一个重要工具,。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到,1736,年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于,这种数学模型和方法直观形象，富有启发性和趣味性，,深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。,图与网络分析,(,Graph Theory and Network Analysis),图的基本知识,最短路问题,树及最小生成树,最大流问题,最小费用最大流问题,第五节 最小费用最大流问题,在考虑一个运输系统中的运输量的同时，往往还要考虑运输费用，希望给出从发货站到收货站的运输量最大、费用最小的运输方案。这就是最小费用最大流问题。,一、最小费用最大流的基本概念,1,、单位流量费用,设 是一个网络，对于每一条弧 ，除容量 外，还给定一个数 ，称作弧 上的单位流量费用。,2,、带费用的网络,规定了费用的网络称作,带费用的网络,，,记作 ，其中 是顶点集合，是弧集合，是容量集合，是费用函数，为发点，为收点。,设 是 上的可行流，称 为可行流 的费用。,3,、可行流,的费用,4,、,流量为,v,的最小费用流,把,D,上所有流量等于,v,的可行流中费用最小的可行流称作,流量为,v,的最小费用流,。,5,、最小费用最大流,当 是 中最大流的流量时，流量为 的最小费用流称作最小费用最大流。所谓最小费用最大流问题（,minimal cost,maximal flow problem,）是求给定带费用的网络上的最小费用最大流。,二、最小费用最大流的求法,1,、由图编写程序,2,、由,lingo8.0,软件求最小费用最大流,例,11,现需要将城市,s,的石油通过管道运送到城市,t,中间有,4,个中转站,v,1,v,2,v,3,和,v,4,。由于输油管道的长短不一或地质等原因，使每条管道上运输费用也不相同。城市与中转站的连接以及管道的容量、单位运费如下图所示，求从城市,s,到城市,t,的最小费最大流。,(2,1),(9,2),(5,5),v,1,v,2,v,3,v,4,s,t,(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,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:b,c,f;,endsets,data:,d=14 0 0 0 0-14;,b=2 8 5 2 3 1 6 4 7;,c=8 7 5 9 9 2 5 6 10;,enddata,min=,sum(arcs:b,*f);,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,)=,d(i,);,sum(arcs(i,j)|i,#,eq,#1:f(i,j)=d(1);,for(arcs:bnd(0,f,c);,END,Global optimal solution found at iteration:3,Objective value:205.0000,Variable Value Reduced Cost,F(S,1)8.000000 -1.000000,F(S,2)6.000000 0.000000,F(1,2)1.000000 0.000000,F(1,3)7.000000 0.000000,F(2,4)9.000000 0.000000,F(3,2)2.000000 -2.000000,F(3,T)5.000000 -7.000000,F(4,3)0.000000 10.00000,F(4,T)9.000000 0.000000,(2,2),(9,7),(5,1),v,1,v,2,v,3,v,4,s,t,(8,8),(7,6),(9,9),(6,0),(5,5),(10,9),例,12,求下图带费用的网络,D,中,V,S,到,V,T,的最小费用最大流。图中弧旁的数字是,b,ij,c,ij,。,解,1,、先求其最大流,MODEL:,sets:,nodes/s,1,2,3,t/;,arcs(nodes,nodes,)/,s,1 s,2 s,3 1,t 2,1 2,t 2,3 3,t/:c,f;,endsets,data:,c=15,15,10,10,5 10,10,10,;,enddata,max=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);,END,Global optimal solution found at iteration:4,Objective value:30.00000,F(S,1)10.00000 0.000000,F(S,2)10.00000 0.000000,F(S,3)10.00000 0.000000,F(1,T)10.00000 -1.000000,F(2,1)0.000000,0.000000,F(2,T)10.00000 -1.000000,F(2,3)0.000000,0.000000,F(3,T)10.00000 -1.000000,2,、再求其最小费用,MODEL:,sets:,nodes/s,1,2,3,t/:d;,arcs(nodes,nodes,)/,s,1 s,2 s,3 1,t 2,1 2,t 2,3 3,t/:,b,c,f,;,endsets,data:,d=30 0 0 0 -30;,b=4 2 6 5 5 8 1 5;,c=15,15,10,10,5 10,10,10,;,enddata,min=,sum(arcs:b,*f);,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,)=,d(i,);,sum(arcs(i,j)|i,#,eq,#1:f(i,j)=d(1);,for(arcs:bnd(0,f,c);,END,Global optimal solution found at iteration:6,Objective value:285.0000,F(S,1)10.00000 0.000000,F(S,2)15.00000 -3.000000,F(S,3)5.000000 0.000000,F(1,T)10.00000 -4.000000,F(2,1)0.000000 6.000000,F(2,T)10.00000 0.000000,F(2,3)5.000000 0.000000,F(3,T)10.00000 -2.000000,例,13,某贸易公司在每个月的月初订购货物，订购后能及时到货、进库并供应市场。货物与当月售出，则不必付存贮费。当月未出售的货物，盘点后转入下月，每件要付库存费,6,个单位。库存的最大贮量是,120,件。预测,1,月到,6,月的订购价格和需求量如下：,月份,1 2 3 4 5 6,需求量,50 55 50 45 40 30,价格,70 67 65 80 84 88,假设,1,月初的库存量为零，要求,6,月底的库存量也为零，不允许缺货。试做出,6,个月的订货计划，使成本最低。,解：,用 表示第 个月初进货后的状态，。表示进货，表示销售。于是，可用网络来描述这个问题。但是在这个网络中，顶点 具有容量，即仓库的最大存贮量。如图,7-22,所示，,弧旁的数字是 ，其中 是单位成本（订购价格或库存费），是货物的最大流通量（订购、销售或转入下月）。顶点内的数字是它的容量（最大库存量）。,于是，我们的问题是要求这个网络的最小费用的最大流。,这个网络可以化成与它等价的不带顶点容量的网络，如图,7-23,所示。,它的最小费用最大流（在图,7-23,中用带括号的数字标在弧旁）就给出了所需的最优订购方案：,1,月至,6,月的订购量分别是,50,，,55,，,120,，,0,，,15,，,30,。（见下页附图）,练习,求下列网络的最小费用最大流及其流量和费用。图中弧旁的数字是 。,附答案：,a,流,量,费用,b,流,量,费用,总 结,1,、,赋权图,最小生成树,避圈法,。,最短路,matlab,。,2,、,赋权有向图,最短路,matlab,。,3,、,网络,最大流,lingo8.0,4,、,带费用的网络,最小费用最大流,lingo8.0,Thanks,