教 案 （16） 授课日期 2006年 月 日 课题 网络计划优化  课时 教学 目标 通过本节学习，学生要掌握网络图优化的方法。  教学 重点 网络图优化的方法。  教学 难点 网络图优化的方法。  课型 讲 授 授课时数 2  更新、补充 删减内容   使用 教具   课外 作业   课后 体会   复习：网络计划的概念；网络图的绘制方法；网络图的时间计算。 网络计划的优化 网络计划的优化是指在一定约束条件下，按既定目标对网络计划进行不断改进，以寻求满意方案的过程。 网络计划的优化目标应按计划任务的需要和条件选定，包括工期目标、费用目标和资源目标。根据优化目标的不同，网络计划的优化可分为工期优化、费用优化和资源优化三种。 一、工期优化 所谓工期优化，是指网络计划的计算工期不满足要求工期时，通过压缩关键工作的持续时间以满足要求工期目标的过程。 (一)工期优化方法 网络计划工期优化的基本方法是在不改变网络计划中各项工作之间逻辑关系的前提下，通过压缩关键工作的持续时间来达到优化目标。在工期优化过程中，按照经济合理的原则，不能将关键工作压缩成非关键工作。此外，当工期优化过程中出现多条关键线路时，必须将各条关键线路的总持续时间压缩相同数值；否则，不能有效地缩短工期。 网络计划的工期优化可按下列步骤进行： (1)确定初始网络计划的计算工期和关键线路。 (2)按要求工期计算应缩短的时间△T： △T=Tc-Tr 式中 Tc——网络计划的计算工期； Tr——要求工期。 (3)选择应缩短持续时间的关键工作。选择压缩对象时宜在关键工作中考虑下列因素： ①缩短持续时间对质量和安全影响不大的工作； ②有充足备用资源的工作； ③缩短持续时间所需增加的费用最少的工作。 (4)将所选定的关键工作的持续时间压缩至最短，并重新确定计算工期和关键线路。若被压缩的工作变成非关键工作，则应延长其持续时间，使之仍为关键工作。 (5)当计算工期仍超过要求工期时，则重复上述(2)～(4)，直至计算工期满足要求工期或计算工期已不能再缩短为止。 (6)当所有关键工作的持续时间都已达到其能缩短的极限而寻求不到继续缩短工期的方案，但网络计划的计算工期仍不能满足要求工期时，应对网络计划的原技术方案、组织方案进行调整，或对要求工期重新审定。 注意:一般情况下,双代号网络计划图中箭线下方括号外数字为工作的正常持续时间，括号内数字为最短持续时间；箭线上方括号内数字为优选系数，该系数综合考虑质量、安全和费用增加情况而确定。选择关键工作压缩其持续时间时，应选择优选系数最小的关键工作。若需要同时压缩多个关键工作的持续时间时，则它们的优选系数之和(组合优选系数)最小者应优先作为压缩对象。 二、工期—成本优化 寻求成本最低的优化工期，可以原定时间（或正常时间）为基础，通过不断压缩关键线路的时间，并计算不同工期下的总成本加以比较，选出最优的网络计划。 项目总成本是项目的直接费用与间接费用之和。一般来说，在正常工期T0和加速（赶工）工期Ts之间，若缩短工期将引起直接费用的增加和间接费用的减少，反之，则相反。如图7.3.3所示： ???  由于各工作的费用不相同，缩短公式所需追加的费用也不同。因此，在缩短项目总工期时，首先应选择费用增加最少的关键工序予以工期压缩。为此可因如一个指标，赶工费用率e (i,j)： ??? e (i,j)＝(m (i,j)－M (i,j))/(D (i,j)－d (i,j)) ??? 式中，D是正常持续时间，d为缩短后的持续时间，M是D相应的直接费用，m是d对应的直接费用。这些数据对本优化问题而言，是前定数据，其中d可根据事先确定每道工序要求且实际可能缩短的工期，再从D中减去而确定。e (i,j)反映工序 (i, j) 缩短单位持续时间所需增加的费用数额。 ??? 下面我们介绍一种被称为“最低费用率加快法”的解决工期—成本优化问题的通常方法，我们通过例7.3.2来说明此方法的具体步骤。 ??? [例7.3.2]? 某工程任务的网络图如图7.3.4所示，当任务按原定24天完成时，所需直接费用为32500元，间接费用6000元，每减少一天工程工期，可节约间接费用1000元，各工序直接费用增长率如表7.3.5所示。现要求缩短工期，试求工期较短而费用最少的优化方案。 ???  图中粗黑线工序串联成关键路线。打“*”的数字表示不能缩减的工序的工期。 表7.3.5 工期—成本优化输入数据表 工序 D（天） M（元） d（天） m（元） D－d e（元/天）  ①→② 1 1000 1 1000 0 不能缩减  ②→③ 4 2100 3 2800 1 700  ②→④ 8 4000 6 5600 2 800  ③→④ 6 5000 4 6000 2 500  ③→⑥ 9 5400 7 6000 2 300  ④→⑤ 4 5000 1 11000 3 2000  ④→⑥ 5 1500 4 2500 1 1000  ⑤→⑦ 3 1500 3 1500 0 不能缩减  ⑥→⑦ 7 6000 6 7500 1 1500  ⑦→⑧ 1 1000 1 1000 0 不能缩减  解: 关键路线的时间决定着整个项目的完工期，要缩短工期，必须从关键路线上压缩的工序着手，并且首先选择赶工费用率e最低的工序。 第一次压缩: 唯有一条关键路线时的压缩原则：选择最小赶工费mjne(i,j)的关键工序作压缩。 ??? 由图7.3.4可见，唯有一条关键路线，本例中mjne(i,j)的关键工序为③→④，由表7.3.5 D－d列可知，该工序可缩短2日。这时，直接费用为： ??? 32500+500×2＝33500（元） 间接费用为： ??? 6000-2000=4000（元） 总工期缩短为22日后，网络图（图7.3.5）出现了3条关键路线： 第一条：①→②→③→④→⑥→⑦→⑧ ??? 第二条：①→②→④→⑥→⑦→⑧ ??? 第三条：①→②→③→⑥→⑦→⑧ ??? 工序③→④仍位于关键线路之中，故上述赶工是可行的正确选择。重新计算时间参数后可将网络图绘成图7.3.5  这时表7.3.5调整为表7.3.6表7.3.6 工序 D（天） M（元） d（天） m（元） D－d e（元/天）  ①→② 1 1000 1 1000 0 不能缩减  ②→③ 4 2100 3 2800 1 700  ②→④ 8 4000 6 5600 2 800  ③→④ 4 5000 4 6000 0 不能缩减  ③→⑥ 9 5400 7 6000 2 300  ④→⑤ 4 5000 1 11000 3 2000  ④→⑥ 5 1500 4 2500 1 1000  ⑤→⑦ 3 1500 3 1500 0 不能缩减  ⑥→⑦ 7 6000 6 7500 1 1500  ⑦→⑧ 1 1000 1 1000 0 不能缩减  第二次压缩: ??? 有多条关键路线时的压缩原则：选择“最小赶工割集”mjn∑e(i,j)的关键工序集作压缩。 ??? “割集”是网络最优化问题中的概念。一个割集是网络图中的若干条弧组成的集合，它使得网络图若“取掉”这些弧，则不再存在将始点与终点连接的路线。 ??? “最小赶工割集”的定义：由可压缩关键工序组成的（赶工）割集，并且是全部这样的（赶工）割集中赶工费用率之和∑e(i,j)中最小的，即取mjn∑e(i,j)的（赶工）割集。 ??? 对于本例中网络图7.3.5的全部（赶工）割集，及其赶工费用率之和∑e(i,j)如图7.3.6所示: ???  ??? 可见最小赶工割集是关键工序集：{③→⑥，④→⑥}。由表7.3.6知，可同时压缩的工期是一天。这时，直接费用为： ??? 33500+300+1000＝34800（元） 间接费用为： ??? 4000-1000=3000（元） ??? 总工期缩短为21日后，网络图（图7.3.7）仍出现了3条关键路线（同前），而且工序③→④，③→⑥，④→⑥仍位于关键线路之中，故上述赶工是可行的正确选择。重新计算时间参数后可将网络图绘成图7.3.7 ???  这时表7.3.6调整为表7.3.7： 工序 D（天） M（元） d（天） m（元） D－d e（元/天）  ①→② 1 1000 1 1000 0 不能缩减  ②→③ 4 2100 3 2800 1 700  ②→④ 8 4000 6 5600 2 800  ③→④ 4 5000 4 6000 0 不能缩减  ③→⑥ 8 5400 7 6000 1 300  ④→⑤ 4 5000 1 11000 3 2000  ④→⑥ 4 1500 4 2500 0 不能缩减  ⑤→⑦ 3 1500 3 1500 0 不能缩减  ⑥→⑦ 7 6000 6 7500 1 1500  ⑦→⑧ 1 1000 1 1000 0 不能缩减  总结：网络图的优化方法。