1、 图与网络分析图与网络分析 (Graph Theory and Network Analysis)赵芳玲 图论是运筹学的一个重要分支，它是建立图论是运筹学的一个重要分支，它是建立和处理和处理离散类离散类数学模型的一个重要工具数学模型的一个重要工具。用图。用图论的方法往往能帮助人们解决一些用其它方法论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的年欧拉所发表的一篇关于解决著名的“哥尼斯哥尼斯堡七桥问题堡七桥问题”的论文。由于的论文。由于这种数学模型和方这种数学模型和方法直观形象，富有启发性和趣
2、味性，法直观形象，富有启发性和趣味性，深受人们深受人们的青睐。到目前为止，已被广泛地应用于系统的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。用了图论模型方法。图与网络分析图与网络分析(Graph Theory and Network Analysis)图的基本知识图的基本知识最短路问题最短路问题 树及最小生成树树及最小生成树最大流问题最大流问题最小费用最大流问题最小费用最大流问题第五节第五节 最小费用最大流问题最小费用最大流
3、问题在考虑一个运输系统中的运输量的同时，往往还要在考虑一个运输系统中的运输量的同时，往往还要考虑运输费用，希望给出从发货站到收货站的运输考虑运输费用，希望给出从发货站到收货站的运输量最大、费用最小的运输方案。这就是最小费用最量最大、费用最小的运输方案。这就是最小费用最大流问题。大流问题。一、最小费用最大流的基本概念一、最小费用最大流的基本概念1 1、单位流量费用、单位流量费用设设 是一个网络，对于每一条弧是一个网络，对于每一条弧 ，除容量，除容量 外，还给定一个数外，还给定一个数 ，称作弧，称作弧 上的单位流上的单位流量费用。量费用。DAa )(ac0)(aba2 2、带费用的网络、带费用的网
4、络 规定了费用的网络称作规定了费用的网络称作带费用的网络带费用的网络，记作记作 ，其中，其中 是顶点集合，是顶点集合，是弧集合，是弧集合，是容量集合，是容量集合，是费用函数，是费用函数，为发为发点，点，为收点。为收点。,tsvvbcAVD VAcbsvtv设设 是是 上的可行流，称上的可行流，称 为可为可行流行流 的费用。的费用。D Aaafabfb)()()(ff3 3、可行流、可行流 的费用的费用 f4 4、流量为流量为v v 的最小费用流的最小费用流 把把D上所有流量等于上所有流量等于v 的可行流中费用最小的可行的可行流中费用最小的可行流称作流称作流量为流量为v 的最小费用流的最小费用流
5、。5 5、最小费用最大流、最小费用最大流 当当 是是 中最大流的流量时，流量为中最大流的流量时，流量为 的最小的最小费用流称作最小费用最大流。所谓最小费用最大费用流称作最小费用最大流。所谓最小费用最大流问题（流问题（minimal costmaximal flow minimal costmaximal flow problemproblem）是求给定带费用的网络上的最小费用）是求给定带费用的网络上的最小费用最大流。最大流。*vD*v二、最小费用最大流的求法二、最小费用最大流的求法1 1、由图编写程序、由图编写程序2 2、由、由lingo8.0lingo8.0软件求最小费用最大流软件求最小费用
6、最大流例例11 11 现需要将城市现需要将城市s s 的石油通过管道运送到城市的石油通过管道运送到城市t t,中间有中间有4 4个中转站个中转站v v1,1,v v2,2,v v3 3 和和v v4 4。由于输油管道。由于输油管道的长短不一或地质等原因，使每条管道上运输费用的长短不一或地质等原因，使每条管道上运输费用也不相同。城市与中转站的连接以及管道的容量、也不相同。城市与中转站的连接以及管道的容量、单位运费如下图所示，求从城市单位运费如下图所示，求从城市s s 到城市到城市t t 的最小的最小费最大流。费最大流。(2,1)(9,2)(5,5)v1v2v3v4 s t(8,2)(7,8)(9
7、,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;endsetsdata: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;enddatamin=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);
8、sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:bnd(0,f,c);END s,ti,tivsi,vdAi,j,cfdfffbffiijijiAj,iVjjiAi,jVjijAi,jijij 0,)(0 t.smin)()()(其中其中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
9、.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)v1v2v3v4 s t(8,8)(7,6)(9,9)(6,0)(5,5)(10,9)例例12 12 求下图带费用的网络求下图带费用的网络D D 中中V VS S 到到V VT T 的最小费用的最小费用最大流。图中弧旁的数字是最大流。图中弧旁的数字是b biji
10、j,c,cijij。解解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;endsetsdata:c=15 15 10 10 5 10 10 10;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
11、);ENDGlobal 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.00000030)(*fv2 2、再求其最小费用、再求其最小费用MODEL
12、: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;endsetsdata:d=30 0 0 0 -30;b=4 2 6 5 5 8 1 5;c=15 15 10 10 5 10 10 10;enddatamin=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);fo
13、r(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.00000030)(*fv285)(*f
14、b例例 1313 某贸易公司在每个月的月初订购货物，订购某贸易公司在每个月的月初订购货物，订购后能及时到货、进库并供应市场。货物与当月售出后能及时到货、进库并供应市场。货物与当月售出，则不必付存贮费。当月未出售的货物，盘点后转，则不必付存贮费。当月未出售的货物，盘点后转入下月，每件要付库存费入下月，每件要付库存费6 6个单位。库存的最大贮量个单位。库存的最大贮量是是120120件。预测件。预测1 1月到月到6 6月的订购价格和需求量如下：月的订购价格和需求量如下：月份月份 1 2 3 4 5 6 1 2 3 4 5 6需求量需求量50 55 50 45 40 3050 55 50 45 40
15、30价格价格70 67 65 80 84 8870 67 65 80 84 88假设假设1 1月初的库存量为零，要求月初的库存量为零，要求6 6月底的库存量也为月底的库存量也为零，不允许缺货。试做出零，不允许缺货。试做出6 6个月的订货计划，使成个月的订货计划，使成本最低。本最低。解：解：用用 表示第表示第 个月初进货后的状态，个月初进货后的状态，。表示进货，表示进货，表示销售。于是，可用网络来描表示销售。于是，可用网络来描述这个问题。但是在这个网络中，顶点述这个问题。但是在这个网络中，顶点 具有容量具有容量，即仓库的最大存贮量。如图，即仓库的最大存贮量。如图7-227-22所示，所示，ivi
16、61 isvtviv弧旁的数字是弧旁的数字是 ，其中，其中 是单位成本（是单位成本（订购价格或库存费），订购价格或库存费），是货物的最大流通是货物的最大流通量（订购、销售或转入下月）。顶点内的数字量（订购、销售或转入下月）。顶点内的数字是它的容量（最大库存量）。是它的容量（最大库存量）。于是，我们的问于是，我们的问题是要求这个网络的最小费用的最大流。题是要求这个网络的最小费用的最大流。这个这个网络可以化成与它等价的不带顶点容量的网络网络可以化成与它等价的不带顶点容量的网络，如图，如图7-237-23所示。所示。它的最小费用最大流（在图它的最小费用最大流（在图7-237-23中用带括号的数字标在
17、弧旁）就给出了所中用带括号的数字标在弧旁）就给出了所需的最优订购方案：需的最优订购方案：1 1月至月至6 6月的订购量分别是月的订购量分别是5050，5555，120120，0 0，1515，3030。（见下页附图）（见下页附图）ijijbc,ijbijc练习练习求下列网络的最小费用最大流及其流量和费求下列网络的最小费用最大流及其流量和费用。图中弧旁的数字是用。图中弧旁的数字是 。ijijcb,附答案：附答案：5)(fv37)(fba a 流流量量,费用费用 18)(fv171)(fbb b 流流量量,费用费用 总总 结结1 1、赋权图赋权图 最小生成树最小生成树避圈法避圈法。最短路最短路matlabmatlab。2 2、赋权有向图赋权有向图 最短路最短路matlabmatlab。3 3、网络网络 最大流最大流lingo8.0lingo8.04 4、带费用的网络带费用的网络 最小费用最大流最小费用最大流lingo8.0lingo8.0),(EVG ),(AVD )v,vc,(ts，AVD ,tsvvbcAVD Thanks
