数学建模方法研讨课(11,4,12)3.ppt

1、7.2 最短路问题和最大流问题,本节内容导航 本节概述 7.2.1 最短路问题 7.2.2 最大流问题 7.2.3最小费与最大流问题,本节内容概述 最短路问题(Shortest Path Problems)和最大流问题(Maxiumum Flow Problems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有Dijkstra算法，最大流问题的求解方法有标号算法.这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题，对于LINDO软件的求解方法，作者可以根据模型自己设计相应的程序，作为LINDO软件的训练和问题的练习.,返 回 导

2、航,例 (最短路问题) 在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路. 下图表示的是公路网, 节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离(百公里). 那么,货车从城市S出发到达城市T,如何选择行驶路线,使所经过的路程最短?,分析,假设从S到T的最优行驶路线 P 经过城市C1, 则P中从S到C1的子路也一定是从S到C1的最优行驶路线; 假设 P 经过城市C2, 则P中从S到C2的子路也一定是从S到C2的最优行驶路线. 因此, 为得到从S到T的最优行驶路线, 只需要先求出从S到Ck(k=1,2)的最优行驶路线, 就可以方便地得到从S到T的最优行驶路线.

3、同样,为了求出从S到Ck(k=1,2)的最优行驶路线, 只需要先求出从S到Bj(j=1,2)的最优行驶路线; 为了求出从S到Bj(j=1,2)的最优行驶路线, 只需要先求出从S到Ai (i=1,2,3)的最优行驶路线. 而S到Ai(i=1,2,3)的最优行驶路线是很容易得到的(实际上, 此例中S到Ai(i=1,2,3)只有唯一的道路),分析,此例中可把从S到T的行驶过程分成4个阶段,即 SAi (i=1,2或3), Ai Bj(j=1或2), Bj Ck(k=1或2), Ck T. 记d(Y,X)为城市Y与城市X之间的直接距离(若这两个城市之间没有道路直接相连，则可以认为直接距离为)，用L(X

4、)表示城市S到城市X的最优行驶路线的路长:,本例的计算,所以, 从S到T的最优行驶路线的路长为20. 进一步分析以上求解过程, 可以得到从S到T的最优行驶路线为 S A3 B2 C1 T.,这种计算方法在数学上称为动态规划(Dynamic Programming),本例的LINGO求解,“CITIES”(城市):一个基本集合(元素通过枚举给出),L:CITIES对应的属性变量(我们要求的最短路长),“ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。,D:稀疏集合

5、ROADS对应的属性变量(给定的距离),本例的LINGO求解,从模型中还可以看出：这个LINGO程序可以没有目标函数，这在LINGO中，可以用来找可行解(解方程组和不等式组)。,在数据段对L进行赋值，只有L(S)=0已知，后面的值为空(但位置必须留出来，即逗号“，”一个也不能少，否则会出错)。如果这个语句直接写成“L=0；”，语法上看也是对的，但其含义是L所有元素的取值全部为0，所以也会与题意不符。,本例的LINGO求解,虽然集合CITIES中的元素不是数字，但当它以CITIES(I)的形式出现在循环中时，引用下标I却实际上仍是正整数，也就是说I指的正是元素在集合中的位置(顺序)，一般称为元素

6、的索引(INDEX)。,在for循环中的过滤条件里用了一个函数“index”, 其作用是返回一个元素在集合中的索引值，这里index(S)=1(即元素S在集合中的索引值为1)，所以逻辑关系式“I#GT#index(S)”可以可以直接等价地写成“I#GT#1” 。这里index(S)实际上还是index(CITIES,S)的简写，即返回S在集合CITIES中的索引值。,本例的LINGO求解结果,从S到T的最优行驶路线的路长为20(进一步分析，可以得到最优行驶路线为S A3 B2 C1 T)。,本例中定义稀疏集合ROADS的方法是将其元素通过枚举给出，有时如果元素比较多，用起来不方便。另一种定义稀

7、疏集合的方法是“元素过滤”法，能够从笛卡儿积中系统地过滤下来一些真正的元素。,7.2.1 最短路问题,例7.7 （最短路问题） 在图 7-3中，用点表示城市，现有 共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市 到城市 铺设一条天然气管道，请设计出最小价格管道铺设方案.,例7.7的本质是求从城市 到城市 的一条最短路.为便于讨论，下面给出有关概念的明确定义.,返 回 导 航,1. 图的基本概念,定义7.2 (子图与赋权图),定义7.3 (迹和路以及圈),定义7.4（邻接矩阵和赋权矩阵）如果 , 则称 与 邻接, 具有 个顶点的图的邻接矩阵(Adjac

8、ency Matrix)是一个 阶矩阵 , 其分量为,个顶点的赋权图的赋权矩阵是一个阶 矩阵,其分量为,定理7.1 如果存在 到 的途径, 则一定存 在 到 的路. 如果图 的顶点个数为 , 则这 个路的长度小于等于 .,2. 最短路问题的数学表达式,假设图有 个顶点，现需要求从顶点1到顶点 的最短路.设决策变量为 , 当 , 说明弧 位于顶点1至顶点 的路上；否则. 其数学规划表达式为,3. 最短路问题的求解过程,在第三章中（例3.5）我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，下面介绍的方法是按照规划问题 设计的.,例7.8 (继例7.7) 求例7.7中，

9、从城市A到城市D的 最短路.,解：写出相应的LINGO程序，程序名: exam0708.lg4.,MODEL: 1! We have a network of 7 cities. We want to find 2 the length of the shortest route from city 1 to city 7; 3,4sets: 5 ! Here is our primitive set of seven cities; 6 cities/A, B1, B2, C1, C2, C3, D/; 7 8 ! The Derived set roads lists the roads

10、that 9 exist between the cities; 10 roads(cities, cities)/ 11 A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 12 C1,D C2,D C3,D/: w, x; 13endsets 14 15data: 16 ! Here are the distances that correspond,17 to above links; 18 w = 2 4 3 3 1 2 3 1 1 3 4; 19enddata 20 21n=size(cities); ! The number of citie

11、s; 22min=sum(roads: w*x); 23for(cities(i) | i #ne# 1 #and# i #ne# n: 24 sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i); 25sum(roads(i,j)|i #eq# 1 : x(i,j)=1; END,在上述程序中， 21句中的n=size(cities)是计 算集cities的个数，这里的计算结果是 , 这样编 写方法目的在于提高程序的通用性.22句表示目标 函数(14), 即求道路的最小权值.23, 24句表示约束 (15) 中 的情况，即最短路中中间点的约束 条件.

12、25句表示约束中 的情况，即最短路中 起点的约束.,约束(15)中 的情况，也就是最短路中终点的 情况，没有列在程序中，因为终点的约束方程与前 个方程相关.当然，如果你将此方程列入到LINGO 程序中，计算时也不会出现任何问题，因为LINGO,软件可以自动删除描述线性规划可行解中的多 余方程.,LINGO软件计算结果（仅保留非零变量）如下,Global optimal solution found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X

13、( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000,即最短路是 , 最短路长为6个单位.,例7.9 (设备更新问题) 张先生打算购买一辆新轿车，轿车的售价是12万元人民币.轿车购买后，每年的各种保险费养护费等费用由表7-5所示.如果在5年之内，张先生将轿车售出，并再购买新年.5年之内的二手车销售价由表7-6所示.请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少.,表7-5 轿车的维护费,表7-6 二手车的售价,分析： 设备更新问题是动态规划 的一 类 问 题（事实上，最短路问题也是动态规划的一类问 题）,这里借助于最短路

14、方法解决设备更新问题.,解： 用6个点（1，2，3，4，5，6）表示各年的开始，各点之间的边从边表示左端点开始年至表示右端点结束所花的费用，这样构成购车消费的网络图，如图图7.4所示.,记 表示第 年开始到 年结束购车的总销费, 即,由此得到,写出相应的LINGO程序，程序名： exam0709.lg4,MODEL: 1sets: 2 nodes/1.6/; 3 arcs(nodes, nodes)|,11enddata 12n=size(nodes); 13min=sum(arcs:c*x); 14for(nodes(i) | i #ne# 1 #and# i #ne# n: 15 sum(

15、arcs(i,j):x(i,j) = sum(arcs(j,i):x(j,i); 16sum(arcs(i,j)|i #eq# 1 : x(i,j)=1; END,程序中的第3句中 3 roads(cities, cities): p, w, x; 4endsets 5data: 6 p = 0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0 0 0 0 0 0 8 0 1 0 1 1 1 1 0 0 0 0 9 0 0 1 0 0 0 1 0 0 0 0 10 0 1 1 0 0 1 0 1 1 0 0,11 0 0 1 0 1 0 1 0 1 0 0 12 0 0 1

16、1 0 1 0 0 1 1 0 13 0 0 0 0 1 0 0 0 1 0 1 14 0 0 0 0 1 1 1 1 0 1 1 15 0 0 0 0 0 0 1 0 1 0 1 16 0 0 0 0 0 0 0 0 0 0 0; 17 w = 0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0 0 0 0 19 8 6 0 7 5 1 2 0 0 0 0 20 1 0 7 0 0 0 9 0 0 0 0 21 0 1 5 0 0 3 0 2 9 0 0 22 0 0 1 0 3 0 4 0 6 0 0,23 0 0 2 9 0 4 0 0 3 1 0 24 0

17、 0 0 0 2 0 0 0 7 0 9 25 0 0 0 0 9 6 3 7 0 1 2 26 0 0 0 0 0 0 1 0 1 0 4 27 0 0 0 0 0 0 0 9 2 4 0; 28enddata 29n=size(cities); 30min=sum(roads:w*x); 31for(cities(i) | i #ne# 1 #and# i #ne# n: 32 sum(cities(j): p(i,j)*x(i,j) 33 =sum(cities(j): p(j,i)*x(j,i); 34sum(cities(j): p(1,j)*x(1,j)=1; END,在上述程序中

18、，第6行到第16行给出了图的邻接矩阵 ， 到 和 到 的边按单向计算，其余边双向计算.第17行到第27行给出了图的赋权矩阵 , 注意：由于有了邻接矩阵 ，两点无道路连接时，权值可以定义为0.其它的处理方法基本上与有向图相同.,用LINGO软件求解，得到（仅保留非零变量） Global optimal solution found at iteration: 2 0 Objective value: 13.00000 Variable Value Reduced Cost,X( 1, 2) 1.000000 0.000000 X( 2, 5) 1.000000 0.000000 X( 3, 7)

19、 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 3) 1.000000 0.000000 X( 7, 10) 1.000000 0.000000 X( 9, 11) 1.000000 0.000000 X( 10, 9) 1.000000 0.000000,即最短路径为, 最短路长度.,为13, 7.2.2 最大流问题,例7.11（最大流问题） 现需要将城市s的石油通过管道运送到城市t，中间有4个中转站 和 , 城市与中转站的连接以及管道的容量如图7-6所示，求从城市s到城市t的最大流.,返 回 导 航,图7-6给出的有一个源和一个汇的网

20、络. 网络 中每一条边 有一个容量 , 除此之外, 对边 还有一个通过边的流(Flow), 记为 . 显然, 边 上的流量 不会超过该边上的容量 , 即,称满足不等式（17）的网络 是相容的. 对于所有中间顶点, 流入的总量应等于流出的 总量 , 即:,一个网络 的流量(Value of flow)值定义为从源 流出的总流量, 即,由式(18)和(19)式可以看出, 的流量值也为流入 汇 的总流量,即:,称满足式(21)的网络 为守恒的.,定义7.6 如果流 满足不等式(17)和式 (21), 则称流 是可行的. 如果存在可行流 , 使 得对所有的可行流 均有,则称 为最大流(Maximum

21、Flow).,2. 最大流问题的数学规划表示形式 通过上述推导得到最大流的数学规划表达式,3. 最大流问题的求解方法,下面用例子说明，如何用LINGO软件求解最大流 问题. 例7.12 （继例7.11）用LINGO软件求解例7.11. 解：写出相应的LINGO程序，程序名:m0712.lg4.,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; 5endsets,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 a

22、rcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; 5endsets 6data: 7 c = 8 7 5 9 9 2 5 6 10; 8enddata 9max = flow;,程序的第10到 12行表示约束(23), 第13行表示 有界约束(24).,LINGO软件的计算结果（只保留流值 ）如下:,Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.0

23、0000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000,因此，该网络的最大流为14，F的值对应弧上的流，如图7-7所示, 其中网络中的第一

24、个数为容量，第二个数为流量.,在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络.,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes): p, c, f; 4endsets 5data: 6 p = 0 1 1 0 0 0 7 0 0 1 1 0 0 8 0 0 0 0 1 0 9 0 0 1 0 0 1 10 0 0 0 1 0 1 11 0 0 0 0 0 0;,12 c = 0 8 7 0 0 0 13 0 0 5 9 0 0 14 0 0 0 0

25、9 0 15 0 0 2 0 0 5 16 0 0 0 6 0 10 17 0 0 0 0 0 0; 18enddata 19max = flow; 20for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): 21 sum(nodes(j): p(i,j)*f(i,j) 22 = sum(nodes(j): p(j,i)*f(j,i); 23sum(nodes(i):p(1,i)*f(1,i) = flow; 24for(arcs:bnd(0, f, c); END,在上述程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零.计算结果与前面程

26、序的结果完全相同，这里就不再列出了., 7.2.3 最小费用最大流问题,例7.13（最小费用最大流问题）（续例7.11）由于输油管道的长短不一，或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，图7-8所示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费.,返 回 导 航,例7.13所提出的问题就是最小费用最大流问题(Minimum-cost maximum flow)，即考虑网络在最大流情况下的最小费用.例7.12虽然给出了例7.11最大流一组方案，但它是不是关于费用的最优方案呢？这还需要进一步讨论.,1. 最小费用流的数学表达式,min,s.t.,其中,当 为网络的最大流进，数学规划 表 示的就是最小费用最大流问题.,2. 最小费用流的求解过程,例7.14（继例7.13）用LINGO软件求解例7.13. 解： 按照最小费用流的数学规划写