课程名称：《运筹学》第_21_讲次授课题目网络图的调整与优化本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，能够对网络计划中的工期、工程费用进行优化分析。[重点及难点】工期优化分析、费用优化分析。内容[本讲课程的引入]网络图的调整及其优化简称网络优化，是指在一定约束条件和目标下，对网络计划进行逐步调整、完善以达到预定要求的过程。从便于分析的角度，常把网络优化分为工期优化、费用优化和资源优化，而实际问题往往是工期、费用、资源等问题交织在一起，需要综合分析。[本讲课程的内容]1、工期优化问题：在当前网络计划的计算工期不满足要求工期，需要在一定约束条件和目标下，对网络计划进行逐步调整，完善以达到预定要求的过程。（保证质量，尽量缩短工期）思路：1.向关键工序要时间2.在非关键工序挖潜力赶工期问题中，只有压缩关键工序才能引起总工期缩短。若网络图中同时有几条关键路线，则几条关键路线必须同时在各自线路上压缩一个关键工序，才能缩短总工期压缩工期步骤：一选择压缩工序二.确定压缩量一，选择压缩工序的步骤1.构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为M表示压缩费用率很大）2.求此网络最小截3.选择最小截上工序同时进行压缩
课程名称：《运筹学》 第 21 讲次 授课题目 网络图的调整与优化 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，能够对网络计划中的工期、工程费用进行优化分析。 [重点及难点] 工期优化分析、费用优化分析。 内 容 [本讲课程的引入] 网络图的调整及其优化简称网络优化，是指在一定约束条件和目标下，对网络计划 进行逐步调整、完善以达到预定要求的过程。从便于分析的角度，常把网络优化分为工 期优化、费用优化和资源优化，而实际问题往往是工期、费用、资源等问题交织在一起， 需要综合分析。 [本讲课程的内容] 1、工期优化 问题：在当前网络计划的计算工期不满足要求工期，需要在一定约束条件和目标下，对网络计 划进行逐步调整，完善以达到预定要求的过程。（保证质量，尽量缩短工期） 思路：1.向关键工序要时间 2.在非关键工序挖潜力 赶工期问题中，只有压缩关键工序才能引起总工期缩短。若网络图中同时有几条关键路线，则几 条关键路线必须 同时在各自线路上压缩一个关键工序，才能缩短总工期 压缩工期步骤： 一.选择压缩工序 二.确定压缩量 一.选择压缩工序的步骤 1.构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为 M,表示压缩费用率很大） 2.求此网络最小截 3.选择最小截上工序同时进行压缩
内容二压缩量确定：1.压缩量t不超过关键工序上允许压缩限度2.压缩量不超过关键路长与次关键路长之差值（一般限制压缩量不超过非关键工序最小总时差），即压缩量t由下式确定：t =min(α, β)α= min(t(i,j)-t(i, j))(i.j)elβ=min(R(i,j)IR(i,j)+0)例：下图是某工程施工网络，图中单箭线→表示普通工序，箭线上的tij(Cij，di)中，为工序时间，Cii为该工序上每压缩一天所需的费用，di为可压缩天数。3(4,2)6JNL1(3,0)1(3,0)3(4,2)5(1,4)10(4,9)5(5,4) C3CFAD 7(2,6)8(3,7)10T8(7,7)4(2.3)B8GE5(4,4)5(1,4)P1(4,0)M953(8,2)（1）关键路线与工期（2）工期压缩为18天，应如何选择压缩工序和压缩天数？（3）工期压缩到17天，通过在（1)中所选定的压缩工序上压缩3天能否达到目的？解：(1).计算关键路、工期、总时差
内 容 二.压缩量确定： 1.压缩量 t 不超过关键工序上允许压缩限度 2.压缩量不超过关键路长与次关键路长之差值（一般限制压缩量不超过非关键工序 最小总时差）,即压缩量 t 由下式确定： 例：下图是某工程施工网络，图中单箭线表示普通工序，箭线上的 tij(Cij, dij)中，tij 为工序时间，Cij 为该工序上每压缩一天所需的费用，dij 为可压缩天数。 （1）关键路线与工期 （2）工期压缩为 18 天，应如何选择压缩工序和压缩天数？ （3）工期压缩到 17 天，通过在(1)中所选定的压缩工序上压 缩 3 天能否达到目的？ 解： (1).计算关键路、工期、总时差 min{ ( , )| ( , ) 0} min{ ( , ) ( , )} min{ , } ( , ) R i j R i j t i j t i j t i j I
内容3(4,2)63/10L1(3.0)1(3.0)H103(4.2)5(1.4)10(49)5(5.4(3112.0)D8(3.7)0208(7.7)4(2.3)$812BGE12/P5(4,4)5(1.4)K1(4.0)M9753(8,2)1958关键路线：C-F,A--DG,BEG工期T=20天A工序LJNPMKH-总时差233131311112（2）构建关键路线网络（赋权值为费用率），确定最小割，选择压缩工序15(1,4)565,4310(4,9)AF72.0)DT8(3,7)10108(7.7)4(2,3)1B48G1用最大流标号法得最小割为(C,D,E)，所以选择在工序C,D,E上压缩时间根据非关键工序的总时差和压缩工序的限制，确定压缩量α=min(dc,dp,d)=3β=2得压缩量为T=min(α,β)=2在C.D.E工序上各压缩两天，使总工期压缩至18天(3)工期压缩2天后，关键路线已发生变化，所以不能在(1)中选中的压缩工序压缩三天以达到工期成为17天的目的。重复上述步骤，得新的网络，重新确定关键路线和非关键路线的总时差，如图
内 容 （2）构建关键路线网络(赋权值为费用率)，确定最小割，选择压缩工序 (3)工期压缩 2 天后，关键路线已发生变化，所以不能在⑴中选中的压缩工序压缩三天 以达到工期成为 17 天的目的。重复上述步骤，得新的网络，重新确定关键路线和非关键 路线的总时差，如图
容内153(4,2)4612J8L1(3.0)1(3.0)H8/53(4.2)3(1,2)10(4,9)5(5,4)(37CF318D 5(2,4)S8(3,7)10)188(7.7)82(2,1)04810GEP5(4,4)105(1,4)K1(4,0)M9563(8,2)1758PM工序HLJN总时差31199311继续构建关键路线网路，确定最小割为C.D,E.K，作为压缩工序。确定压缩量3(1,2)565.4310(4,9)CEAD 5(2,4)8(3,7)￥108(7.7)22,1)(8GE5(4,4)I5(1,4) + K-51根据非关键工序的总时差和压缩工序的限制，确定压缩量α=min(dc，dp，dg，d）=1最小时差β=3，得压缩量为T=min(α,β)=1在C.D.E.K工序上各压缩1天，使总工期压缩至17天2、工程费用分析编制工程网络计划时，不仅要考虑工期时间，还应考虑工程造价对一个工程来说，无论是以考虑工程费用为主，还是以控制时间进度为主，都必须对工程计划进行时间一一费用分析，从而可综合考虑制定最优的计划
内 容 2、工程费用分析 编制工程网络计划时，不仅要考虑工期时间，还应考虑工程造价 对一个工程来说，无论是以考虑工程费用为主，还是以控制时间进度为主，都 必须对工程计划进行时间——费用分析，从而可综合考虑制定最优的计划
容内费用概念直接费用：分解到每道工序，主要指人工、材料、燃料等直接用于一项工序的费用。，工序直接费用率：指一道工序缩短单位时间所需增加的费用直接费用率9=赶进度工时费用一正常工序时间费用正常工序时间－赶进度工序时间间接费用：与整个项目相关的费用，指管理人员的工资、办公、采购等并非直接用于完成工程任务的费用。。间接费用率p：整个项目的工期每提前单位时间可节约的费用工程的时间一费用关系图压缩工期会增加直接费用，但减少了间接费用延长工期会增加间接费用，但可能减少直接费用总费用曲线由同费用总费甩工期下的直接费用和间接费用相加得到直接费用曲线（工程的时间一费用曲线）间接费用曲线T工期时间最低成本工期因此只有当压缩关键工序时间增加的直接费用小于由此导致工期缩短而节约的间接费用时，这一压缩才进行。最低成本工期的确定：q(i,j)一工序(i,j)的直接费用率(ij)一工序(i,j)的工序时间可缩短下限，即赶进度时间P一单位时间的间接费用率确定最低成本工期的步骤：一、绘制网络图，计算工序总时差R（i，j)，确定TE与关键路线，计算相应工程费用
内 容 最低成本工期的确定： q (i, j)—工序(i, j)的直接费用率 (i, j)—工序(i, j)的工序时间可缩短下限，即赶进度时间 p—单位时间的间接费用率 确定最低成本工期的步骤： 一、绘制网络图，计算工序总时差 R (i, j)，确定 TE 与关键路线，计算相应工程费用