图论模型的LINGO算法ppt课件.ppt

图论与网络模型,最短路问题(Shortest Path Problems)和最大流问题(Maxiumum Flow Problems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有Dijkstra算法，最大流问题的求解方法有标号算法。这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题，对于LINDO软件的求解方法，作者可以根据模型自己设计相应的程序，作为LINDO软件的训练和问题的练习.,最短路问题和最大流问题,7.2.1 最短路问题,例7.7 （最短路问题） 在图 7-3中，用点表示城市，现有 共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市 到城市 铺设一条天然气管道，请设计出最小价格管道铺设方案.,例7.7的本质是求从城市 到城市 的一条最短路.,1. 最短路问题的数学表达式,假设有向图有n个顶点，现需要求从顶点1到顶点n的最短路.设0-1决策变量为xij, 当xij=1, 说明弧(i,j)位于顶点1至顶点j的最短路上；否则xij=0. 其数学规划表达式为,2. 最短路问题的求解过程,前面我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，下面介绍的方法是按照规划问题(14)-(15)设计的.,例7.8 (继例7.7) 求例7.7中，从城市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 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 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的个数，这里的计算结果是 , 这样编写方法目的在于提高程序的通用性.22句表示目标函数(14), 即求道路的最小权值.23, 24句表示约束(15) 中 的情况，即最短路中中间点的约束条件.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( 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 二手车的售价,分析： 设备更新问题是动态规划 的一 类 问题（事实上，最短路问题也是动态规划的一类问题）, 这里借助于最短路方法解决设备更新问题.,解： 用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(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是逻辑运算语句，表示所说明的变量只有行小于列的部分，因此所说明的矩阵是上三角阵.,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 0.000000,即第1年初购买轿车，第2年初卖掉，再购买新车，到第4年初卖掉，再购买新车使用到第5年末，总费用31万元.,当然，上述方案不是唯一的，例如还有 和 , 但无论何种方案，总费用均是31万.,例7.10（无向图的最短路问题）求图7-5中 到的最短路.,分析：不论是例7.7、 例7.9还是第三章的例3.5处理的问题均属于有向图的最短路问题，本例是处理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别.,解： 对于无向图的最短路问题，可以这样理解，从点 到点 和点 到点 的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写LINGO程序相当边（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.,写出相应的LINGO程序，程序名：exam0710.lg4,MODEL: 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 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 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(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,在上述程序中，第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) 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给出的有一个源和一个汇的网络. 网络 中每一条边 有一个容量 , 除此之外, 对边 还有一个通过边的流(Flow), 记为 . 显然, 边 上的流量 不会超过该边上的容量 , 即,称满足不等式（17）的网络 是相容的. 对于所有中间顶点, 流入的总量应等于流出的总量 , 即:,一个网络 的流量(Value of flow)值定义为从源流出的总流量, 即,由式(18)和(19)式可以看出, 的流量值也为流入汇 的总流量,即:,称满足式(21)的网络 为守恒的.,定义7.6 如果流 满足不等式(17)和式(21), 则称流 是可行的. 如果存在可行流 , 使得对所有的可行流 均有,则称 为最大流(Maximum 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,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(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软件的计算结果（只保留流值 ）如下:,Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 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所示, 其中网络中的第一个数为容量，第二个数为流量.,在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络.,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 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,在上述程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零.计算结果与前面程序的结果完全相同，这里就不再列出了., 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. 解： 按照最小费用流的数学规划写出相应的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, 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); END,程序的第 11行是目标函数(25), 第12, 13, 14行是约束条件(26), 第15行是约束的上下界(27).,LINGO软件的计算结果（仅保留流值 )如下:,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 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, 简写为PERT）和关键路线法（Critial Path Method, 简写为CPM）是网络分析的重要组成部分，它广泛用系统分析和项目管理.计划评审与关键路线方法是在20世纪50年代提出并发展起来的，1956年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法.1958年，美国海军武装部在研制“北极星”导弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法.由于PERT与CPM即有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法(Scheduling Method).,计划评审方法和关键路线法,7.4.1计划网络图,例7.19 某项目工程由11项作业组成（分别用代号A, B, , J, K表示），其计划完成时间及作业间相互关系如表7-8所示，求完成该项目的最短时间.,例7.19就是计划评审方法或关键路线法需要解决的问题.,1. 计划网络图的概念,定义 7.11 称任何消耗时间或资源的行动为作业.称作业的开始或结束为事件，事件本身不消耗资源. 在计划网络图中通常用圆圈表示事件，用箭线表示作业，如图7-12所示，1, 2, 3表示事件，A, B表示作业。由这种方法画出的网络图称为计划网络图。,定义7.12 在计划网络图中，称从初始事件到最终事件的由各项作业连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路线。由此看来，例7.19就是求相应的计划网络图中的关键路线。,(1)任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件. (2)两个事件之间只能画一条箭线，表示一项作业.对于具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业.(3) 任何计划网络图应有唯一的最初事件和唯一的最终事件.(4) 计划网络图不允许出现回路.(5) 计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉.,2. 建立计划网络图应注意的问题,7.4.2计划网络图的计算,以例7-19的求解过程介绍计划网络图的计算方法.1. 建立计划网络图首先建立计划网络图.按照上述规则，建立例7.19的计划网络图，如图7-13所示.,2. 写出相应的规划问题,设是事件的开始时间，1为最初事件，n为最终事件.希望总的工期最短，即极小化 .设是作业 的计划时间，因此，对于事件 与事件 有不等式：,由此得到相应的数学规划问题,3. 问题求解,例7.20(继例7.19) 用LINDO软件求解例7.19 解： 按照数学规划问题（7.37）-（7.39）编写INDO程序，程序名：,exam0720.ltxmin x8 - x1subject to2) x2 - 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.00000 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.000000 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,计算结果给出了各个项目的开工时间，如 , 则作业A、B、C的开工时间均是第0天; 作业E的开工时间是第5天; 则作业D的开工时间是第10天; 等等.每个作业只要按规定的时间开工，整个项目的最短工期为51天.,尽管上述LINDO程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工时间等.因此,我们希望将程序编写的稍微复杂一些，为我们提供更多的信息.,下面利用LINGO软件完成此项工作.,例7.21 用LINGO软件求解例7.19.,解: 按照数学规划问题(7.37)-(7.39) 编写LINGO程序只有得到整,注：实际上s_ij称谓作业(i,j)的自由时间。,编写相应的Lingo程序，程序名： exam0721.lg4,MODEL: 1sets: 2 events/1.8/: x; 3 operate(events, events)/ 4 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 5 /: s, t; 6endsets 7data: 8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9enddata 10min=sum(events : x); 11for(operate(i,j): s(i,j)=x(j)-x(i)-t(i,j); END,计算得到（只列出非零解）: Variable Value Reduced Cost X( 2) 5.000000 0.000000 X( 3) 10.00000 0.000000 X( 4) 14.00000 0.000000 X( 5) 10.00000 0.000000 X( 6) 31.00000 0.000000 X( 7) 35.00000 0.000000 X( 8) 51.00000 0.000000 S( 1, 4) 3.000000 0.000000 S( 2, 5) 1.000000 0.000000 S( 4, 6) 2.000000 0.000000 S( 5, 8) 6.000000 0.000000 S( 6, 7) 4.000000 0.000000 S( 7, 8) 1.000000 0.000000,由此，可以得到所有作业的最早开工时间和最迟开工时间，如表7-9所示，方括号中第1个数字是最早开工时间，第2个数字是最迟开工时间.,从上述表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路线上，因此可以画出计划网络图中的关键路线，如图7-14粗线所示.关键路线为 13568.,4： 将关键路线看成最长路,如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线 .,设为 变量，当作业 位于关键路线上取1;否则取0. 数学规划问题写成:,例7.22 用最长路的方法求解例7.19.,解： 按数学规划(7.40)-(7.42)写出相应的INGO程序，程序名：exam0722.lg4.,MODEL: 1sets: 2 events/1.8/: d; 3 operate(events, events)/ 4 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 5 /: t, x; 6endsets 7data:,8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9 d = 1 0 0 0 0 0 0 -1; 10enddata 11max=sum(operate : t*x); 12for(events(i): 13 sum(operate(i,j): x(i,j) - sum(operate(j,i): x(j,i) 14 =d(i); 15); END,计算得到（只列出非零解):,Objective value: 51.00000 Variable Value Reduced Cost X( 1, 3) 1.000000 0.000000 X( 3, 5) 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 8) 1.000000 0.000000,即工期需要51天，关键路线为13568. 从上述计算过程可以看到，在两种LINGO程序中，第二个程序计算在计算最短工期、关键路线均比第一个程序方便，但在某些情况下，例如，需要优化计划网络时，第一种程序的编写方法可以更好地发挥出其优点.,7.4.3 关键路线与计划网络的优化,例7.23 （关键路线与计划网络的优化）假设例7.19中所列的工程要求在49天内完成.为提前完成工期，有些作业需要加快进度、缩短工期，而加快进度需要额外增加费用.表7-10列出例7-19中可缩短工期的所有作业和缩短一天额外增加的费用.现在的问题是，如何安排作业才能使额外增加的总费用最少.,例7.23所涉及的问题就是计划网络的优化问题，这时需要压缩关键路径来减少最短工期.,1. 计划网络优化的数学表达式,设 是事件 的开始时间， 是作业 的计划时间, 是完成作业 的最短时间， 是作业 可能减少的时间，因此有,设 是要求完成的天数， 为最初事件， 为最 终事件,所以有 而问题的总目标是使额外增加的费用最小，即目标函数为 . 由此得到相应的数学规划问题,2. 计划网络优化的求解,例7.24 用LINDO软件求解例7.23 解：按照数学规划问题(7.43)-(7.47)编写LINDO程序，程序名：exam0724.ltx.,min 700 y13 + 400 y14 + 450 y25 + 600 y56 + 300 y57 + 500 y58 + 500 y68 + 400 y78 subject to2) x2 - x1 = 53) x3 - x1 + y13 = 104) x4 - x1 + y14 = 115) x5 - x2 + y25 = 46) x4 - x3 = 47) x5 - x3 = 08) x6 - x4 = 159) x6 - x5 + y56 = 2110) x7 - x5 + y57 = 2511) x8 - x5 + y58 = 35,12) x7 - x6 = 013) x8 - x6 + y68 = 2014) x8 - x7 + y78 = 1515) x8 - x1 = 49endsub y13 2sub y14 3 sub y25 1sub y56 5sub y57 3sub y58 5sub y68 4sub y78 3,LINDO软件的计算结果如下：,LP OPTIMUM FOUND AT STEP 23 OBJECTIVE FUNCTION VALUE 1) 1200.000 VARIABLE VALUE REDUCED COST Y13 1.000000 0.000000 Y14 0.000000 400.000000 Y25 0.000000 450.000000 Y56 0.000000 100.000000 Y57 0.000000 100.000000 Y58 0.000000 500.000000 Y68 1.000000 0.000000 Y78 0.000000 200.000000,X2 5.000000 0.000000 X1 0.000000 0.000000 X3 9.000000 0.000000 X4 13.000000 0.000000 X5 9.000000 0.000000 X6 30.000000 0.000000 X7 34.000000 0.000000 X8 49.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 -700.000000 4) 2.000000 0.000000 5) 0.000000 0.000000,6) 0.000000 0.000000 7) 0.000000 -700.000000 8) 2.000000 0.000000 9) 0.000000 -500.000000 10) 0.000000 -200.000000 11) 5.000000 0.000000 12) 4.000000 0.000000 13) 0.000000 -500.000000 14) 0.000000 -200.000000 15) 0.000000 700.000000 NO. ITERATIONS= 23,作业(1,3)(B)压缩一天的工期，作业(6,8)(K)压缩一天工期，这样可以在49天完工，需要多花费1200元. 如果需要知道压缩工期后的关键路径，则需要稍复杂一点的计算.,例7.25 用LINGO软件求解例7.23, 并求出相应的关键路径、各作业的最早开工时间和最迟开工时间. 解：为了得到作业的最早开工时间，仍在目标函数中加入 , 其他处理方法与前面相同.,写出相应的LINGO程序，程序名： exam0725.lg4.,MODEL: 1sets: 2 events/1.8/: x; 3 operate(events, events)/ 4 ! A B C D E 0 F G H I 0 J K; 5 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 6 /: s, t, m, c, y; 7endsets 8data: 9 t = 5 10 11 4 4 0 15 21 35 25 0 15 20;,10 m = 5 8 8 4 3 0 15 16 30 22 0 12 16; 11 c = 0 700 400 0 450 0 0 600 500 300 0 400 500; 12 d = 49; 13enddata 14min=mincost+sumx; 15mincost=sum(operate:c*y); 16sumx=sum(events: x); 17for(operate(i,j): s(i,j)=x(j)-x(i)+y(i,j)-t(i,j); 18n=size(events); 19x(n)-x(1)=d; 20for(operate:bnd(0,y,t-m); END,计算结果得到（只列出非零解）:,Variable Value Reduced Cost MINCOST 1200.000 0.000000 SUMX 149.0000 0.000000 X( 2) 5.000000 0.000000 X( 3) 9.000000 0.000000 X( 4) 13.00000 0.000000 X( 5) 9.000000 0.000000 X( 6) 30.00000 0.000000 X( 7) 34.00000 0.000000 X( 8) 49.00000 0.000000 S( 1, 4) 2.000000 0.000000,S( 4, 6) 2.000000 0.000000 S( 5, 8) 5.000000 0.000000 S( 6, 7) 4.000000 0.000000 Y( 1, 3) 1.000000 0.000000 Y( 6, 8) 1.000000 0.000000,计算结果与LINDO相同.作业(1,3)（B）减少一天,作业(6,8)(K)减少一天，最小增加费用为1200元. 按照前面的方法，计算出所有作业的最早开工时间和最迟开工时间，见表7-11所示.,当最早开工时间与最迟开工时间相同时，对应的作业就在关键路线上，图7-15中的粗线表示优化后的关键路线.从图7-15可能看到，关键路线不只一条.,