运筹学第九章_网络计划教材教学课件.ppt

累加所需人力资源数, 工作(1, 4) 与(2, 3) 共需10人/日, 所以工作(1, 6) 要移出 [2, 3] 时间段。 如图所示: 以后各时间段类似处理, 经过几次调整, 可得到下图: 此时人力资源需求量已满足不超过10人的限制, 总工期未受影响, 必要时总工期可能会延迟。 注: 由于编号及调整规则只是一种原则, 所以调整结果常常是较好方案, 不一定是工期最短方案。 由于求精确解有时繁难, 网络优化中多采用这类近似算法. 优化的几种方法。 一、把串联工作改为平行工作或平行交叉工作。 二、利用时差。 三、有限资源的合理分配。 四、最低成本日程。 一、把串联工作改为平行工作或平行交叉工作 为了缩短整个任务的完工期，达到时间优化的目标，可以研究关键路线上串联的每一个工作有无可能改为平行或交叉进行的工作，以缩短工期。 1 2 3 4 12 市场调研 1 2 3 4 5 6 4 4 4 (调1) (调2) (调3) 二、利用时差 由于网络中的非关键路工作都有时差，所以这些工作在开工时间上，具体工时上都具有一定的弹性。 为了缩短任务的总工期，可以考虑放慢非关键工作的进度，减少这些工作的人力、资源，转去支援关键工作，以使关键工作的工时缩短来达到目的。 三、最低成本日程（时间——费用优化） 时间和费用双目标优化，一般来讲二者是矛盾的。通过计算网络计划的不同完工期相应的总费用，以求得成本最低的日程安排就是“最低成本日程”，又称“工期－成本”优化。 费用：直接费用和间接费用 直接费用：建造工程本身所需材料、人工等 间接费用：工程所需管理费用、设备租金 直接费用与工作所需工时关系为： 常用成本斜率 表示 其中工作( i, j ) 的正常工时为 ,所需费用为 特急工时为 ,所需费用为 表示了工作( i, j ) 从正常工时每缩短一个单位时间所需增加的费用 下面通过例子说明最低成本日程的计算方法 例 已知网络计划各工作的正常工时、特急工时及 相应费用如表，网络图如下。 设正常工时下，任务总间接费用为18000元，工期每缩短一天，间接费用可节约330元。 求最低成本日程。 工作 正常工时 特急工时 成本斜率 Cij(元/ d） 时间（d） 费用（元） 时间（d） 费用（元） ? ? 24 5000 16 7000 250 ? ? 30 9000 18 102000 100 ? ? 22 4000 18 4800 200 ? ? 26 10000 24 10300 150 ? ? 24 8000 20 9000 250 ? ? 18 5400 18 5400 / ? ? 18 6400 10 6800 50 24 1 2 3 4 5 6 24 30 22 26 18 18 T(0) = 74 最低成本日常计算步骤: 1 从关键工作中选出缩短工时所需直接费用最少的方案,并确定该方案可能缩短的天数 按照工作的新工时,重新计算网络计划的关键路径 计算由于缩短工时所增加的直接费用 重复上述三个步骤,直到工期不能再缩短为止 分析过程如下所示: 第一次调整 工作 正常工时 特急工时 成本斜率 Cij(元/ d） 时间（d） 费用（元） 时间（d） 费用（元） ? ? 24 5000 16 7000 250 ? ? 22 4000 18 4800 200 ? ? 24 8000 20 9000 250 ? ? 18 6400 10 6800 50 1 2 3 4 5 6 24 30 22 26 18 18 ? ? 26 10000 24 10300 150 ? ? 18 5400 18 5400 / ? ? 30 9000 18 102000 100 18 24 工作 正常工时 特急工时 成本斜率 Cij(元/ d） 时间（d） 费用（元） 时间（d） 费用（元） ? ? 24 5000 16 7000 250 ? ? 22 4000 18 4800 200 ? ? 24 8000 20 9000 250 ? ? 18 6400 10 6800 50 1 2 3 4 5 6 24 22 26 18 18 ? ? 26 10000 24 10300 150 ? ? 18 5400 18 5400 / ? ? 30 9000 18 102000 100 18 T(1) = 64 T(1) - T(0) = 10 即关键路径只缩短了10天, 这意味着1?3没有必要减少12天, 工作(1, 3) 应取 30 – 10 = 20(天) 24 工作 正常工时 特急工时 成本斜率 Cij(元/ d） 时间（d） 费用（元） 时间（d） 费用（元） ? ? 24 5