第11章 图与网络优化.ppt

W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6++8+11+18=59 最早参数计算(练习) 最迟参数计算(练习) 总时差的计算(练习) 图11-31 4. 将关键路线看成最长路 如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线。设 xij 为0-1变量，当作业 (i,j) 位于关键路线上取1，否则取0。数学规划问题写成 例11.16 用最长路的方法，求解例11.15。 model: sets: events/1..8/:d; operate(events,events)/ 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/:t,x; endsets data: t=5 10 11 4 4 0 15 21 35 25 0 15 20; d=1 0 0 0 0 0 0 -1; enddata max=@sum(operate:t*x); @for(events(i):@sum(operate(i,j):x(i,j)) -@sum(operate(j,i):x(j,i))=d(i)); end 计算得到（只列出非零解）： Objective value: 51.00000 Total solver iterations: 0 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天，关键路线为1→ 3 → 5 → 6 → 8 。 从上述计算过程可以看到，在两种LINGO程序中，第二个程序在计算最短工期、关键路线时均比第一个程序方便，但在某些情况下，例如，需要优化网络计划时，第一种程序的编写方法可以更好地发挥出其优点。 11.5.3 关键路线与网络计划的优化 例11.17 （关键路线与网络计划的优化）假设例11.14所列的工程要求在49天内完成。为提前完成工程，有些作业需要加快进度、缩短工期，而加快进度需要额外增加费用。表11-4列出了例11.14中可缩短工期的所有作业和缩短一天工期额外增加的费用。现在的问题是，如何安排作业才能使额外增加的总费用最少。 500 16 20 K (6,8) 600 16 21 G (5,6) 400 12 15 J (7,8) 450 3 4 E (2,5) 300 22 25 I (5,7) 400 8 11 C (1,4) 500 30 35 H (5,8) 700 8 10 B (1,3) 缩短1天增加的费用/元 最短完成时间/天 计划完成时间/天 作业 缩短1天增加的费用/元 最短完成时间/天 计划完成时间/天 作业 表11-4 1．网络计划优化的数学表达式 设 xi 是事件 i 的开始时间，tij 是作业 (i,j) 的计划时间，mij 是完成作业 (i,j) 的最短时间，yij 是作业 (i,j) 可能减少的时间，因此有 设 d 是要求完成的天数，1为最初事件，n为最终事件，则有 而问题的总目标是使额外增加的费用最小，即目标函数为 相应的数学规划模型为 s.t. 2.网络计划优化的求解 按照以上模型求解，可以得到需要压缩工期的作业和需要多花费的费用。但如果还需要得到压缩工期后的关键路径、各作业的最早开工时间和最迟开工时间，则需要对以上模型进行修改。为了得到作业的最早开工时间，仍在目标函数中加入 ，其他处理方法与前面相同。 例11.17相应的LINGO程序清单如下。 MODEL: sets: events/1..8/:x; operate(events,events)/ !A B C D E 0