欢迎来到天天文库
浏览记录
ID：40290462
大小：107.50 KB
页数：4页
时间：2019-07-30
《第八讲 图与网络模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第八讲图与网络模型问题1最大流问题某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道的容许流量（容量）也是不一样的。的单位为万加仑/小时。如果使用这个网络系统从采地向销地运送石油，问每小时能运送多少加仑石油？63522241263v1v2v7v4v3v6v5方案表述每条弧上的流为多少决策变量设弧上的流量为约束条件目标函数数学模型为Excel求解问题2最小费用最大流问题及其数学模型由于输油管道的长短不一，所以上例中每段管道除了有不同的流量限制外，还有不同的单位流量的费用，的单位为万加仑/小时，的单位为百元
2、/万加仑。如图。从采地向销地运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v7v3v6(6,3)v5v4本问题的数学模型为很显然，此问题可以推广为给定流量的最小费用流问题。类似地，可以考虑限制费用的最大流问题。问题3（有向）最短路问题v2v3v4v132521v6v517535问题转换将路长（弧长）看作费用，求一个流值为1的最小费用流问题4（无向）最短路问题v2v3v4v132521v6v517535
此文档下载收益归作者所有
