图论模型的LINGO算法.ppt

《图论模型的LINGO算法.ppt》由会员分享，可在线阅读，更多相关《图论模型的LINGO算法.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、优优 化化 建建 模模图论与网络模型图论与网络模型优优 化化 建建 模模 最短路问题最短路问题(Shortest Path Problems)和最大流问和最大流问题题(Maxiumum Flow Problems)是图论另一类与优化是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有解决的方法，如最短路问题的求解方法有Dijkstra算算法，最大流问题的求解方法有标号算法。这里主要讨法，最大流问题的求解方法有标号算法。这里主要讨论的是如何用论的是如何用LINGO软件来求解最短路和最大流问软件来求解最短

2、路和最大流问题，对于题，对于LINDO软件的求解方法，作者可以根据模软件的求解方法，作者可以根据模型自己设计相应的程序，作为型自己设计相应的程序，作为LINDO软件的训练和软件的训练和问题的练习问题的练习.最短路问题和最大流问题最短路问题和最大流问题优优 化化 建建 模模7.2.1 最短路问题最短路问题 例例7.7 （最短路问题）（最短路问题） 在图在图 7-3中，用点表示城中，用点表示城市，现有市，现有 共共7个城市个城市.点与点之间的连线点与点之间的连线表示城市间有道路相连表示城市间有道路相连.连线旁的数字表示道路的长连线旁的数字表示道路的长度度.现计划从城市现计划从城市 到城市到城市 铺

3、设一条天然气管道，铺设一条天然气管道，请设计出最小价格管道铺设方案请设计出最小价格管道铺设方案. 12123, ,AB B C C C DAD 例例7.7的本质是求从城市的本质是求从城市 到城市到城市 的一条最短路的一条最短路.AD优优 化化 建建 模模1. 最短路问题的数学表达式最短路问题的数学表达式 假设有向图有假设有向图有n个顶点，现需要求从顶点个顶点，现需要求从顶点1到顶点到顶点n的最短路的最短路.设设0-1决策变量为决策变量为xij, 当当xij=1, 说明弧说明弧(i,j)位于顶点位于顶点1至顶点至顶点j的最短路上；否则的最短路上；否则xij=0. 其数学其数学规划表达式为规划表达

4、式为( , )11( , )( , )min ; (14)1,1,. . 1, ; (15)0,1, . 0,( , ).ijiji jEnnijjijji jEj iEijxis txxininxi jE (16)优优 化化 建建 模模 2. 最短路问题的求解过程最短路问题的求解过程 前面我们接触到了最短路问题的求解，当时的求前面我们接触到了最短路问题的求解，当时的求解方法是按照解方法是按照Dijkstra算法设计的，下面介绍的方法算法设计的，下面介绍的方法是按照规划问题是按照规划问题(14)-(15)设计的设计的. 例例7.8 (继例继例7.7) 求例求例7.7中，从城市中，从城市A到城市

5、到城市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

6、 roads lists the roads 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=

7、size(cities); ! The number of cities; 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的个数，这里的计算结果是的个数，这里的计算结果是 , 这样编这样编写方法目的在于

8、提高程序的通用性写方法目的在于提高程序的通用性.22句表示目标句表示目标函数函数(14), 即求道路的最小权值即求道路的最小权值.23, 24句表示约束句表示约束(15) 中中 的情况，即最短路中中间点的约束的情况，即最短路中中间点的约束条件条件.25句表示约束中句表示约束中 的情况，即最短路中的情况，即最短路中起点的约束起点的约束.7n 1,iin1i 约束约束(15)中中 的情况，也就是最短路中终点的的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前情况，没有列在程序中，因为终点的约束方程与前个方程相关个方程相关.当然，如果你将此方程列入到当然，如果你将此方程列入到L

9、INGO程序中，计算时也不会出现任何问题，因为程序中，计算时也不会出现任何问题，因为LINGO in优优 化化 建建 模模 软件可以自动删除描述线性规划可行解中的多软件可以自动删除描述线性规划可行解中的多余方程余方程. LINGO软件计算结果（仅保留非零变量）如下软件计算结果（仅保留非零变量）如下Global optimal solution found at iteration: 0 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.0

10、00000 X( C1, D) 1.000000 0.000000 即最短路是即最短路是 , 最短路长为最短路长为6个单位个单位.11ABCD优优 化化 建建 模模 例例7.9 (设备更新问题设备更新问题) 张先生打算购买一辆张先生打算购买一辆新轿车新轿车，轿车的售价是轿车的售价是12万元人民币万元人民币.轿车购买后，轿车购买后，每年的各种保险费养护费等费用由表每年的各种保险费养护费等费用由表7-5所示所示.如果如果在在5年之内，张先生将轿车售出，并再购买新年年之内，张先生将轿车售出，并再购买新年.5年之内的二手车销售价由表年之内的二手车销售价由表7-6所示所示.请你帮助张先请你帮助张先生设计

11、一种购买轿车的方案，使生设计一种购买轿车的方案，使5年内用车的总费年内用车的总费用最少用最少. 表表7-5 轿车的维护费轿车的维护费车龄车龄/年年01234费用费用/万元万元245912优优 化化 建建 模模表表7-6 二手车的售价二手车的售价车龄车龄/年年12345售价售价/万元万元76210 分析：分析： 设备更新问题是动态规划设备更新问题是动态规划 的一的一 类类 问问题（事实上，最短路问题也是动态规划的一类问题（事实上，最短路问题也是动态规划的一类问题）题）, 这里借助于最短路方法解决设备更新问题这里借助于最短路方法解决设备更新问题. 解：解： 用用6个点（个点（1，2，3，4，5，6

12、）表示各年）表示各年的开始，各点之间的边从边表示左端点开始年至的开始，各点之间的边从边表示左端点开始年至表示右端点结束所花的费用，这样构成购车消费表示右端点结束所花的费用，这样构成购车消费的网络图，如图图的网络图，如图图7.4所示所示.优优 化化 建建 模模 记记 表示第表示第 年开始到年开始到 年结束购车的年结束购车的总销费总销费, 即即ijci1j 1ijcijij在 第 年 到 第年 结 束 轿 车 的 维 护 费 用 +在 年 开 始 新 车 的 购 买 费 用 -在 第 年 开 始 二 手 的 销 售 人优优 化化 建建 模模由此得到1 21 31 41 51 62 32 42 52

13、 63 43 53 621 277 ,241 261 2 ,2451 212 1,24951 213 1,24951 2104 4 ,21 277 ,241 261 2 ,2451 212 1,24951 213 1,21 277 ,241 261 2 ,2451 21cccccccccccc4 54 65 62 1,21 277 ,241 261 2 ,21 277 .ccc优优 化化 建建 模模写出相应的写出相应的LINGO程序，程序名：程序，程序名： exam0709.lg4MODEL: 1sets: 2 nodes/1.6/; 3 arcs(nodes, nodes)|&1 #lt#

14、&2: c, x; 4endsets 5data: 6 c= 7 12 21 31 44 7 7 12 21 31 8 7 12 21 9 7 12 10 7;优优 化化 建建 模模 11enddata 12n=size(nodes); 13min=sum(arcs:c*x); 14for(nodes(i) | i #ne# 1 #and# i #ne# n: 15 sum(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句中句中&1 #1t# &2是逻辑运

15、算语是逻辑运算语句，表示所说明的变量只有行小于列的部分，因句，表示所说明的变量只有行小于列的部分，因此所说明的矩阵是上三角阵此所说明的矩阵是上三角阵.优优 化化 建建 模模 LINGO软件的计算结果（仅保留非零变量）如下软件的计算结果（仅保留非零变量）如下 Global optimal solution found at iteration: 0 Objective value: 31.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 0.000000 X( 2, 4) 1.000000 0.000000 X( 4, 6) 1.000000

16、 0.000000即第即第1年初购买轿车，第年初购买轿车，第2年初卖掉，再购买新车，年初卖掉，再购买新车，到第到第4年初卖掉，再购买新车使用到第年初卖掉，再购买新车使用到第5年末，总费年末，总费用用31万元万元.优优 化化 建建 模模 当然，上述方案不是唯一的，例如还有当然，上述方案不是唯一的，例如还有 和和 , 但无论何种方案，总费用均是但无论何种方案，总费用均是31万万.1 3 5 6 1 3 4 6 例例7.10（无向图的最短路问题）求图（无向图的最短路问题）求图7-5中中 到到的最短路的最短路.1v11v 分析：不论是例分析：不论是例7.7、 例例7.9还是第三章的例还是第三章的例3.

17、5处理的问题均属于有向图的最短路问题，本例是处处理的问题均属于有向图的最短路问题，本例是处理无向图的最短路问题，在处理方式上与有向图的理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别最短路有一些差别.优优 化化 建建 模模 解：解： 对于无向图的最短路问题，可以这样理对于无向图的最短路问题，可以这样理解，从点解，从点 到点到点 和点和点 到点到点 的边看成有向弧，其的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种前面介绍有向图的最短路问题来编程序，但按照这种方法编写方法编写L

18、INGO程序相当边（弧）增加了一倍程序相当边（弧）增加了一倍.这里这里选择邻接矩阵和赋权矩阵的方法编写选择邻接矩阵和赋权矩阵的方法编写LINGO程序程序.1viviv11v优优 化化 建建 模模写出相应的写出相应的LINGO程序，程序名：程序，程序名：exam0710.lg4MODEL: 1sets: 2 cities/1.11/; 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

19、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 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

20、 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 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(citi

21、es(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优优 化化 建建 模模 在上述程序中在上述程序中，第，第6行到第行到第16行给出了图的邻行给出了图的邻接矩阵接矩阵 ， 到到 和和 到到 的边按单向的边按单向计算，其余边双向计算计算，其余边双向计算.第第17行到第行到第27行给出了图行给出了图的赋权矩阵的赋权矩阵 , 注意：由于有了邻接矩阵注意：由于有了邻接矩阵 ，两，两点无道路连接时，权值可以定义为点无道路连接时，权值可以定义为0.其它的处理方其它的处理方法基

22、本上与有向图相同法基本上与有向图相同.P1v234,vvv8910,vvv11vWP用用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) 1.000000 0.000000 X( 5, 6) 1.000000 0.0000

23、00 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 即最短路径为即最短路径为1256371011, 最短路长度最短路长度.为为13优优 化化 建建 模模 7.2.2 最大流问题最大流问题 例例7.11（最大流问题）（最大流问题） 现需要将城市现需要将城市s的石油通过管道运送到城市的石油通过管道运送到城市t，中间有，中间有4个中个中转站转站 和和 , 城市与中转站的连接以城市与中转站的连接以及管道的容量如图及管道的容量如图

24、7-6所示，求从城市所示，求从城市s到城到城市市t的最大流的最大流.123,v v v4v优优 化化 建建 模模 图图7-6给出的有一个源和一个汇的网络给出的有一个源和一个汇的网络. 网络网络 中每一条边中每一条边 有一个容量有一个容量 , 除此之外除此之外, 对边对边 还有一个通过边的流还有一个通过边的流(Flow), 记为记为 . 显然显然, 边边 上的流量上的流量 不会超过该边上的容量不会超过该边上的容量 , 即即G( , )u v( , )c u v( , )u v(,)fu v( , )u v(,)fu v( , )c u v0(,)(,) (1 7 )fu vc u v优优 化化

25、建建 模模称满足不等式（称满足不等式（17）的网络）的网络 是相容的是相容的. 对于所有中间顶点对于所有中间顶点, 流入的总量应等于流出的流入的总量应等于流出的总量总量 , 即即:G( , )c u v( , )( , ) (18)v Vv Vf u vf v u 一个网络一个网络 的流量的流量(Value of flow)值定义为从源值定义为从源流出的总流量流出的总流量, 即即Gs( )( , ) (19)v VV ff s v 由式由式(18)和和(19)式可以看出式可以看出, 的流量值也为流入的流量值也为流入汇汇 的总流量的总流量,即即:ft优优 化化 建建 模模()(,) ( 2 0

26、)vVVffvt( ),( , )( , )0, (21)( ),.V fvsf v Vf V vV vs vtV fvt当当当 称满足式(21)的网络 为守恒的.G优优 化化 建建 模模 定义定义7.6 如果流如果流 满足不等式满足不等式(17)和式和式(21), 则称流则称流 是可行的是可行的. 如果存在可行流如果存在可行流 , 使使得对所有的可行流得对所有的可行流 均有均有fff*f*()()VfVf则称则称 为最大流为最大流(Maximum Flow).*f 2. 最大流问题的数学规划表示形式最大流问题的数学规划表示形式 通过上述推导得到最大流的数学规划表达式通过上述推导得到最大流的数

27、学规划表达式( ,)(, )m ax ; (2 2 ),s.t. , (2 3)0, , 0, ( ,). ffijjifjVjVijAj iAijijvvisffvitis tfcijA (2 4 )优优 化化 建建 模模3. 最大流问题的求解方法最大流问题的求解方法 下面用例子说明，如何用下面用例子说明，如何用LINGO软件求解最大流软件求解最大流问题问题. 例例7.12 （继例（继例7.11）用）用LINGO软件求解例软件求解例7.11. 解：解：写出相应的写出相应的LINGO程序，程序名程序，程序名:m0712.lg4.MODEL: 1sets: 2 nodes/s,1,2,3,4,t

28、/; 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优优 化化 建建 模模 6data: 7 c = 8 7 5 9 9 2 5 6 10; 8enddata 9max = flow; 10for(nodes(i) | i #ne# s #and# i #ne# t: sum(arcs(j,i):f(j,i)= sum(arcs(i,j):f(i,j); 11 for(nodes(i) | i #eq# s: sum(arcs(i,j):f(i,j)= flow; 12 for(nodes

29、(i) | i #eq# t: sum(arcs(j,i):f(j,i)= -flow; 13for(arcs:bnd(0, f, c); End 程序的第程序的第10到到 12行表示约束行表示约束(23), 第第13行表示行表示有界约束有界约束(24).优优 化化 建建 模模LINGO软件的计算结果（只保留流值软件的计算结果（只保留流值 ）如下）如下:fGlobal optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.00000

30、0 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的值对应弧上的值对应弧上的流，如

31、图的流，如图7-7所示所示, 其中网络中的第一个数为容其中网络中的第一个数为容量，第二个数为流量量，第二个数为流量. 在上面的程序中，采用稀疏集的编写方法，下面在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络用稀疏集的编写方法，更便于推广到复杂网络.优优 化化 建建 模模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

32、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 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(node

33、s(j): p(j,i)*f(j,i); 23sum(nodes(i):p(1,i)*f(1,i) = flow; 24for(arcs:bnd(0, f, c); END优优 化化 建建 模模在上述程序中，由于使用了邻接矩阵，当两点之间在上述程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零无弧时，定义弧容量为零.计算结果与前面程序的结计算结果与前面程序的结果完全相同，这里就不再列出了果完全相同，这里就不再列出了.优优 化化 建建 模模 7.2.3 最小费用最大流问题最小费用最大流问题 例例7.13（最小费用最大流问题）（续例（最小费用最大流问题）（续例7.11）由）由于输油管道的

34、长短不一，或地质等原因，使每条管于输油管道的长短不一，或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小最大流外，还需要考虑输油管道输送最大流的最小费用，图费用，图7-8所示是带有运费的网络，其中第所示是带有运费的网络，其中第1个数个数字是网络的容量，第字是网络的容量，第2个数字是网络的单位运费个数字是网络的单位运费.优优 化化 建建 模模 例例7.13所提出的问题就是最小费用最大流问题所提出的问题就是最小费用最大流问题(Minimum-cost maximum flow)，即考虑网络在最大

35、，即考虑网络在最大流情况下的最小费用流情况下的最小费用.例例7.12虽然给出了例虽然给出了例7.11最大流最大流一组方案，但它是不是关于费用的最优方案呢？这一组方案，但它是不是关于费用的最优方案呢？这还需要进一步讨论还需要进一步讨论.1. 最小费用流的数学表达式最小费用流的数学表达式 优优 化化 建建 模模( , );ijiji jAc f( 2 5 )( , )( , ),ijjiij Vj Vi jAj iAffd( 2 6 )0, ( ,).ijijfuijA(27),0, .fifvisdvitis t(28)min s.t. 其中其中 当当 为网络的最大流进，数学规划为网络的最大流进

36、，数学规划 表表示的就是最小费用最大流问题示的就是最小费用最大流问题.fv(25) (28)优优 化化 建建 模模2. 最小费用流的求解过程最小费用流的求解过程 例例7.14（继例（继例7.13）用）用LINGO软件求解例软件求解例7.13. 解：解： 按照最小费用流的数学规划写出相应的按照最小费用流的数学规划写出相应的LINGO程序，程序名：程序，程序名： exam0714.lg4.MODEL: 1sets: 2 nodes/s,1,2,3,4,t/:d; 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u,

37、f; 5endsets 6data: 7 d = 14 0 0 0 0 -14;优优 化化 建建 模模 8 c = 2 8 5 2 3 1 6 4 7; 9 u = 8 7 5 9 9 2 5 6 10; 10enddata 11min=sum(arcs:c*f); 12for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): 13 sum(arcs(i,j):f(i,j) - sum(arcs(j,i):f(j,i)=d(i); 14sum(arcs(i,j)|i #eq# 1 : f(i,j)=d(1); 15for(arcs:bnd(0,f,u)

38、; END 程序的第程序的第 11行是目标函数行是目标函数(25), 第第12, 13, 14行是约行是约束条件束条件(26), 第第15行是约束的上下界行是约束的上下界(27).优优 化化 建建 模模LINGO软件的计算结果（仅保留流值软件的计算结果（仅保留流值 )如下如下:fGlobal 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,

39、 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, T) 9.000000 0.000000因此，最大流的最小费用是因此，最大流的最小费用是205单位单位.而原最大流而原最大流费用为费用为210单位，原方案并不是最优的单位，原方案并不是最优的.优优 化化 建建 模模计划评审方法（计划评审方法（Program Evaluation and Review Technique,

40、简写为简写为PERT）和关键路线法（）和关键路线法（Critial Path Method, 简写为简写为CPM）是网络分析的重要组成部分，）是网络分析的重要组成部分，它广泛用系统分析和项目管理它广泛用系统分析和项目管理.计划评审与关键路线方计划评审与关键路线方法是在法是在20世纪世纪50年代提出并发展起来的，年代提出并发展起来的，1956年，美国年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法了关键路线法.1958年，美国海军武装部在研制年，美国海军武装部在研制“北极北极星星”导弹计划时，由于导弹的研制系统过于庞大、复杂，导

41、弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法为找到一种有效的管理方法，设计了计划评审方法.由由于于PERT与与CPM即有着相同的目标应用，又有很多相同即有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为的术语，这两种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法，在国内称为统筹方法(Scheduling Method).计划评审方法和关键路线法计划评审方法和关键路线法 优优 化化 建建 模模7.4.1计划网络图计划网络图 例例7.19 某项目工程由某项目工程由11项作业组成（分别用项作业组成（分别用代

42、号代号A, B, , J, K表示），其计划完成时间及作业表示），其计划完成时间及作业间相互关系如表间相互关系如表7-8所示，求完成该项目的最短时所示，求完成该项目的最短时间间.例例7.19就是计划评审方法或关键路线法需要解决的问题就是计划评审方法或关键路线法需要解决的问题.优优 化化 建建 模模1. 计划网络图的概念计划网络图的概念 定义定义 7.11 称任何消耗时间或资源的行动为作称任何消耗时间或资源的行动为作业业.称作业的开始或结束为事件，事件本身不消耗称作业的开始或结束为事件，事件本身不消耗资源资源. 在计划网络图中通常用圆圈表示事件，用箭在计划网络图中通常用圆圈表示事件，用箭线表示作

43、业，如图线表示作业，如图7-12所示，所示，1, 2, 3表示事件，表示事件，A, B表示作业。由这种方法画出的网络图称为计划表示作业。由这种方法画出的网络图称为计划网络图。网络图。优优 化化 建建 模模定义定义7.12 在计划网络图中，称从初始事件到在计划网络图中，称从初始事件到最终事件的由各项作业连贯组成的一条路为路最终事件的由各项作业连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路线。具有累计作业时间最长的路线称为关键路线。线。由此看来，例由此看来，例7.19就是求相应的计划网络图中就是求相应的计划网络图中的关键路线。的关键路线。优优 化化 建建 模模 (1)任何作业在网络中

44、用唯一的箭线表示，任任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件何作业其终点事件的编号必须大于其起点事件. (2)两个事件之间只能画一条箭线，表示一项两个事件之间只能画一条箭线，表示一项作业作业.对于具有相同开始和结束事件的两项以上作对于具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业业，要引进虚事件和虚作业.(3) 任何计划网络图应有唯一的最初事件和唯任何计划网络图应有唯一的最初事件和唯一的最终事件一的最终事件.(4) 计划网络图不允许出现回路计划网络图不允许出现回路.(5) 计划网络图的画法一般是从左到右，从上计划网络图的画法一般是从左到右，从上到

45、下，尽量作到清晰美观，避免箭头交叉到下，尽量作到清晰美观，避免箭头交叉.2. 建立计划网络图应注意的问题建立计划网络图应注意的问题优优 化化 建建 模模7.4.2计划网络图的计算计划网络图的计算以例以例7-19的求解过程介绍计划网络图的计算的求解过程介绍计划网络图的计算方法方法.1. 建立计划网络图建立计划网络图首先建立计划网络图首先建立计划网络图.按照上述规则，建立例按照上述规则，建立例7.19的计划网络图，如图的计划网络图，如图7-13所示所示.优优 化化 建建 模模2. 写出相应的规划问题写出相应的规划问题 设是事件的开始时间，设是事件的开始时间，1为最初事件，为最初事件，n为为最终事件

46、最终事件.希望总的工期最短，即极小化希望总的工期最短，即极小化 .设设是作业是作业 的计划时间，因此，对于事件的计划时间，因此，对于事件 与事件与事件 有不等式：有不等式： ixi1nxxijt( , )i jijjiijxxt由此得到相应的数学规划问由此得到相应的数学规划问题题优优 化化 建建 模模 3. 问题求解问题求解 例例7.20(继例继例7.19) 用用LINDO软件求解例软件求解例7.19 解：解： 按照数学规划问题（按照数学规划问题（7.37）-（7.39）编写）编写INDO程序，程序名：程序，程序名：exam0720.ltxmin x8 - x1subject to2) x2

47、- x1 = 53) x3 - x1 = 104) x4 - x1 = 115) x5 - x2 = 4优优 化化 建建 模模6) x4 - x3 = 47) x5 - x3 = 08) x6 - x4 = 159) x6 - x5 = 2110) x7 - x5 = 2511) x8 - x5 = 3512) x7 - x6 = 013) x8 - x6 = 2014) x8 - x7 = 15end优优 化化 建建 模模LINDO软件的计算结果如下：软件的计算结果如下：LP OPTIMUM FOUND AT STEP 9 OBJECTIVE FUNCTION VALUE 1) 51.000

48、00 VARIABLE VALUE REDUCED COST X8 51.000000 0.000000 X1 0.000000 0.000000 X2 5.000000 0.000000 X3 10.000000 0.000000 X4 14.000000 0.000000 X5 10.000000 0.000000 X6 31.000000 0.000000 X7 36.000000 0.000000优优 化化 建建 模模ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 -1.000000 4) 3.0000

49、00 0.000000 5) 1.000000 0.000000 6) 0.000000 0.000000 7) 0.000000 -1.000000 8) 2.000000 0.000000 9) 0.000000 -1.000000 10) 1.000000 0.000000 11) 6.000000 0.000000 12) 5.000000 0.000000 13) 0.000000 -1.000000 14) 0.000000 0.000000 NO. ITERATIONS= 9优优 化化 建建 模模 计算结果给出了各个项目的开工时间，如计算结果给出了各个项目的开工时间，如 , 则则

50、作业作业A、B、C的开工时间均是第的开工时间均是第0天天; 作业作业E的开的开工时间是第工时间是第5天天; 则作业则作业D的开工时间是第的开工时间是第10天天; 等等等等.每个作业只要按规定的时间开工，整个项每个作业只要按规定的时间开工，整个项目的最短工期为目的最短工期为51天天.10 x 25,x 310,x 尽管上述尽管上述LINDO程序给出相应的开工时间和整个程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并项目的最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开没有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工时间等工时间