Page 235 - 数学建模算法与应用

第八章 图与网络模型及方法应用

例 23 所涉及的问题就是计划网络的优化问题，这时需要压缩关键路径来减
少最短工期。

（一）计划网络优化的数学表达式
设 xi 是事件 i 的开始时间，t ij 是作业 (i， j) 的计划时间，m ij 是完成作业 (i，
j) 的最短时间， y ij 是作业 (i， j) 可能减少的时间，c ij 是作业 (i， j) 缩短一天增加
的费用，因此有

设 d 是要求完成的天数，1 为最初事件，n 为最终事件，所以有 而

问题的总目标是使额外增加的费用最小，即目标函数为 由此得到相
应的数学规划问题：

（二）计划网络优化的求解
用 LINGO 软件求解例 23，程序如下：

model：
sets：
events/1..8/：x；

operate(events，events)/1 2，1 3，1 4，2 5，3 4，3 5，4 6，5 6，
5 7，5 8，6 7，6 8，7 8/：t，m，c，y；
endsets
data：

t=5 10 11 4 4 0 15 21 25 35 0 20 15；
m=5 8 8 3 4 0 15 16 22 30 0 16 12；
c=0 700 400 450 0 0 0 600 300 500 0 500 400；

d=49；
enddata
min=@sum(operate：c*y)；

225