34-图与网络分析 （Graph Theory and Network Analysis）.pptVIP

* 图与网络分析 (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个中转站v1,v2,v3 和v4。由于输油管道的长短不一或地质等原因，使每条管道上运输费用也不相同。城市与中转站的连接以及管道的容量、单位运费如下图所示，求从城市s 到城市t 的最小费最大流。 (2,1) (9,2) (5,5) v1 v2 v3 v4 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