《运筹学》课程授课教案（讲稿）第21讲 网络图的调整与优化

课程名称：《运筹学》第_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 与关键路线，计算相应工程费用

内容二、在各关键路线上所有可压缩的工序中，各确定一个本线路上费用率最低的工序作为压缩工序，这些压缩工序之集合用1表示一般可由1）构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为M表示压缩费用率很大）2）求此网络最小截3.）选择最小截上工序同时进行压缩Zq(i,j)=若(q-p),三.计算这些压缩工序上费用率之和H则表示压缩工期将引起工程费用上升，若（q-p)0时为止最低成本工期确定步骤1.绘制网络图，计算工序总时差压缩4.确定压缩时间tR（i,j)，确定TE与关键路线，计t=minta,py算相应工程费用aB=minRi,DIR.+0)2.在各关键路线上各确定一个本线路上费用率最低的工序作为压缩工序，这些压缩工序之集合用1表示是3.计算这些压缩工序上费否最低成用率之和若（q-p)<0本工期Zgi,j)=g(LJEI

内 容 二、在各关键路线上所有可压缩的工序中，各确定一个本线路上费用率最低的工序作 为压缩工序，这些压缩工序之集合用 I 表示.一般可由 1）.构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋权为 M,表示压缩费用 率很大） 2）.求此网络最小截 3.）选择最小截上工序同时进行压缩

内容例：下图表示由l、m、n、o、Fp、q、r七道工序组成的网络图及有关时间参数，工程有关费用由下表给出，正常工期T=60天，试确定赶工期问题中最低成本工期m?315Yo10／n0p1425154上2040(10工序正常工序时间（天）赶进度工序时间（天）正常完工进度直接费用（元）各工序费用率（元/天）1010800I112m153000180810120n200025180150060151530001P20205001915150T402000合计112800间接费用200[循环1]第一步，建立网路图，如下图所示，确定各工序总时差R(i,ji)，见表2，关键路线由q和r二道工序组成，工序时间T=60天。SsAm13斤2515AX10n/1025]p0/6020Y7142515600209r2020-4010方案1：工期为60天(正常工期)的费用：S，=12800+200*60=24800元工序总时差R(,D工字总时差R,D12520p025qm025n200第二步，关键路线上只能缩短工序，则1工序为压缩工序第三步，r工序费用率q/-150，(qr-p)=-50<0。可进一步压缩。第四步，确定压缩时间t，显然有r工序上压缩时间20天，得新工序时间

内 容 第二步，关键路线上只能缩短 r 工序，则 r 工序为压缩工序。 第三步，r 工序费用率 q r=150， (q r - p) = -50 < 0。可进一步压缩。 第四步，确定压缩时间 t，显然有 r 工序上压缩时间 20 天，得新工序时间

内容[循环2]第一步，建立网路图(图3)，确定各工序总时差R(i,j)，见表3，有两条关键路线（7)-（10)-(14)和（7)-（12)-（14），完工期为40天3015m132511101525/10n1025P 60)0 (60)1440/0V712251514001Q 20R (150)202020(10)图31方案2：工期为40天的工程费用：S2=12800+150*20+200*40=23800元工序工序总时差R(,D总时差R(,D501R表350mq50nr00第二步，在关键路线网络上确定最小割为o工序(7，12)和r工序（10，14）并将其作为压缩工序；第三步，压缩工序费用率总和为q=[q(7,12)+q(10,14)]=210此时，(q-p)>0，所以不能在压缩工期，任何压缩都将引起总费用上升最低成本工期为40天，相应费用23800元。[本讲小结】今天我们给大家重点介绍了工期优化、工程费用分析，希望大家回去再好好看看书上的内容[本讲课程的作业］复习本讲内容

内 容 第二步，在关键路线网络上确定最小割为 o 工序(7，12)和 r 工序(10，14）并将其作为 压缩工序； 第三步，压缩工序费用率总和为 q = [q (7，12) + q (10，14)] = 210 此时，(q - p) > 0，所以不能在压缩工期，任何压缩都将引起总费用上升. 最低成本工期为 40 天，相应费用 23800 元。 [本讲小结] 今天我们给大家重点介绍了工期优化、工程费用分析，希望大家回去再好好 看看书上的内容 [本讲课程的作业] 复习本讲内容