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