运筹学第六章网络计划.ppt

《运筹学第六章网络计划.ppt》由会员分享，可在线阅读，更多相关《运筹学第六章网络计划.ppt（66页珍藏版）》请在三一办公上搜索。

1、6.1 网络计划图的绘制 6.2 时间参数计算与关键路线确定 6.3 网络图的调整及优化,第六章 网络计划（工程计划问题）,1.问题的一般提法：,设有一项工程，可分为若干道工序，已知各工序间的先后关系以及各工序所需时间t。,问：,（1）工程完工期T？,（2）工程的关键工序有哪些？,（3）若工序时间T具有随机性，则期望完工期TE=?完工期为某天的可能性多大？,（4）费用优化和资源平衡。,2.解法,关键路径法（CPM方法）,计划评审法（PERT方法）,相同点：,不同点：,PERT法：注重于对工程安排的评价与审查。,CPM方法：注重于时间、成本和资源的优化；,均是用网络表示工程项目，以确定关键路线。

2、,6.1 网络计划图的绘制,1.绘图顺序：按工序先后从左至右,2.网络图的组成要素,（1）弧（实箭线）,表示工序，,（2）顶点（结点）：,表示相邻工序时间分界点，称为事项，,（3）相邻弧：,表示工序的前后衔接关系，称为紧前（或紧后）关系。,A是B的紧前工序，B是A的紧后工序。,A,（4）虚工序（虚箭线）,为表示工序前后衔接关系的需要而增加的。,3.绘图规则：,（1）图中不能有缺口，多重边和回路。,（缺口：有几个总开工事项或几个总完工事项）,处理方法：在5、6之间加道虚工序,A,（多重边：两点之间有多于一条边）处理方法：增加虚工序,（回路：工序循环进行，永远不能完成不允许）,（）,（）,（）,（

3、）,（）,（2）网络图中的事项要从左至右统一编号，每道工序 的箭尾事项号应小于箭头事项号。,正确,错误,（3）尽量避免箭杆交叉。,处理方法：先画草图，再整理。,4.绘图准备工作,（1）确定目标,（以谁为主）,时间资源费用,（2）工程任务的分解和分析；,分析工程由哪些工序组成并列出全部工序及代号清单。,（3）确定各工序之间先后顺序及衔接关系；,要确定每道工序开工之前有哪些工序必须先期完成。,（4）确定各工序时间。,要确定每道工序的完成所需时间。,例1（P13例）某工厂进行技术改造的工作表如下：,1,6.2 时间参数计算与关键路线确定CPM方法,一、求完工期T（标号从前往后）,表示第i个事项最早在

4、第20天才开始。,25,17,31,31=max25+6,17+3,表示第10个事项最早在第31天开始。之所以取最大，因为在第20天，L工序已完成，但k工序未完成。,tE(n),二、求关键路（关键工序）（标号从后往前）,tL(i)=,mintL(j)-t(i,j),10,4,8,4=min10-6,8-3,表示第5个事项最晚第4天开始。之所以取最小，保证时间最长的工序K能完工。,表示这道工序的松弛时间。,如,R(i,j)=25-3-21=1,表示A工序最晚结束时间在第25天，最早开工时间在第21天，工时为3天，故有1天的松弛量。,3.关键工序,工序时差为0的工序（R(i,j)=0）,如：,25

5、-3-22=0,表示A工序的开工和结束时间不能延后，否则整个工期延后一关键工序。,4.关键路,由关键工序组成的由起点到终点的路。,例2 求例1的关键工序及关键路。,0,5.5,3,25.5,29.5,31.5,0,5.5,3,25.5,29.5,31.5,RA=3.5,RB=0,RC=0,RD=16.5,RE=0,RF=0,RG=0,总工期:T=31.5（周）,2.关键工序时间之和=完工期T,关键工序：B-C-E-F-G,所有时间参数,(j)最早完成时间=(i)最早开始时间-t(i,j)(i)最迟完成时间=(j)最迟开始时间-t(i,j)工序(i,j)的总时差=(j)最迟开始时间-t(i,j)

6、-(i)最早开始时间工序(i,j)的自由时差=(j）最早开始时间-(i）最早完成时间,例3（P136）某项课题研究工作分解的作业表如下。根据此表绘制此项科研工作的网络图，计算时间参数，并确定关键路线。,0,4,14,14,11,26,31,35,35,0,4,14,26,31,35,35,14,14,关键工序：A-C-C-E-G-H-I,6.3 网络图的调整及优化,6.3.1 缩短工程工期问题工期优化,所谓工期优化，就是在编制网络计划时，如何加快工程进度，缩短工程的工期。一般可以从以下两个方面进行：,（1）压缩关键工序的工序时间,对关键工序增加新设备，采用新工艺，新技术等措施；或对工序时间较长

7、的关键工序采用平行作业或交叉作业等措施，以达到提高工效、缩短关键工序时间的目的。,（2）在非关键工序上尽量挖掘潜力,利用非关键工序的时差进行合理调度，抽调人力、物力支援关键工序，缩短关键工序时间。,6.3.2 工程的时间费用分析工期-成本优化（费用优化）,所谓工期成本优化，就是在编制网络计划中，如何使工程的完成既快又省。,一.费用构成,1.直接费用,工资、设备、原材料等（直接与完成工序有关的费用）,称 为直接（赶工）费用率,（表示缩短工序一天，工期增加的直接费用）,即直接费用率=平均单位时间的赶工费用,2.间接费用,管理费等（不直接参加生产的费用）,称单位时间的间接费用为间接费用率。,总费用=

8、直接费用+间接费用,时间,二.求最低成本工期,方法：,1.求出正常工期和关键工序（用CPM方法）,2.比较关键工序的直接费用率与间接费用率,（1）若直接费用率间接费用率,则正常工期为最低成本工期。,（2）若存在直接费用率间接费用率,则在关键工序上压缩，先压缩直接费用率最小的方案，并确定该方案可能缩短的时间。t=min,=min压缩工序的正常时间-赶工时间=min所有非关键工序的时差,（3）按照工作的新工时，重新计算网络计划的关键 路线及关键工序。,（4）再比较关键工序的直接费用率与间接费用率。,不断重复，直到使总费用上升为止。（直接费用率间接费用率）,注：若压缩引起出现多于一条新的关键路线时，

9、需同时压缩各关键路线.,（因为不同时压，则工期不能缩短，工期=关键工序上工时之和）,例4 设某工程有关资料如表：,间接费用率为5,求最低成本工期。,解：,（1）求工期及关键工序。,0,7,3,12,12,7,3,0,工期：T=12,关键工序：A-C-D,（2）因为直接费用率不全5，故应在关键工序上压缩,先压缩C（直接费用率最小）,压一天能节省费用为5-4=1=3（C的可压天数），=R24=2 故t=2,压缩方案：,C压缩2天，可减少费用（5-4）*2=2,此时网络图为：,关键路有两条：,A-B,A-C-D,工期T=10RA=RB=RC=RD=0,若再各压缩1天,则应压缩B、C（同时压）,此时的

10、直接费用率将是3+4=75,故最低成本工期为10天。,注：,（1）有时资料未给可压缩时间，但给了正常工作时间及最短工作时间。则压缩时间=正常工作时间-最短工作时间。,（2）当网络图中工作很多，关键路线又不止一条，用观察法来确定缩短工时所需直接费用增加最少的方案比较困难，这时可以使用求网络最大流的标号法来解决。,方法：,将问题化为：在全部以关键工序组成的网络上，每边容量使用本工作的直接费用率（若本工作已不能缩短工时，容量应标）求网络的最大流，当求出最大流时所得到的最小截，就是增加直接费用最少的方案。,工作组合（2，4）（2，3）为费用最低方案。B C,三.求规定工期的最小成本方案,间接费用是确定

11、了的，无需考虑，只需考虑直接费用尽量小。,方法：,1.求出正常工期和关键路线,2.在关键工序上压，先压缩直接费用率最小的，压缩天数也应为t=min,.当出现多于一条的关键路线时要同时压，直到满足规定为止。,例5 建筑公司要装水管线的工程，有关资料：,（1）按正常情况，画出施工网络图，找出关键路，求完工期。,（2）现提出这项工程要60天完成，求使总应急费用最小的方案。,0,11.7,29.7,14.9,36.9,44.6,61.4,68.6,68.6,61.4,44.6,35.6,36.9,36.9,11.7,0,正常工期TE=68.6天,关键工序a-c-f-g-h,解：（1）,（2）将每道工序

12、的直接费用率计算如下：,1）先压f,=2.7;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故=3.2。因此,t=2.7,0,11.7,29.7,14.9,36.9,41.9,58.7,65.9,65.9,58.7,41.9,32.9,36.9,36.9,11.7,0,工期TE=65.9,关键工序：a-c-f-g-h,2）再压h,=2.2;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故=3.2.因此，t=2.2,0,11.7,29.7,14.9,36.9,41.9,58.7,63.7,63.7,58.7,41.9,32.9,36.9,36.9,11.7,0,工期TE=

13、63.7,关键工序：a-c-f-g-h,3）再压c,=3.7;而Rb=22,Rd=3.2,Re=3.2,Ri=9.0故=3.2.因此，t=3.2,0,11.7,29.7,14.9,33.7,38.7,55.5,60.5,60.5,55.5,38.7,29.7,33.7,33.7,11.7,0,工期TE=60.560,关键工序：a-d-e-g-h a-c-f-g-h,4）可同时压c,e各0.5天,=0.5;而Rb=18.8,Rc=3.0故=3.0.因此，t=0.5,0,11.7,29.7,14.9,33.2,38.2,55.0,60,60,55.0,38.2,29.7,33.2,33.2,11.

14、7,0,工期TE=60,关键工序：1）a-c-f-g-h,2）a-d-e-g-h,所以，工期60天时,总应急最小的方案为：,增加的最小应急费用,6.3.3 工程的时间资源优化（工期资源优化）,所谓工期资源优化，就是在有限资源的情况下，如何合理地调配人力、材料、设备、能源等资源，使之既符合客观条件限制，又尽量不误工期（将资源适当调整使资源利用得以平衡）。,方法：,1.计算工程每单位时间内所需资源量。,2.作出初始进度横道表,3.进行资源均衡调整求得新进度。,4.评价工程进度计划对资源利用的均衡程度（计算单位时间内资源利用量的方差）。,例6 已知某工程有关资料如表：,（1）绘制工程网络图，求出工期

15、与关键路线。,（2）调整网络，使资源尽量平衡（不能延误工期）,解：（1）,0,2,2,4,7,11,11,7,4,2,4,0,工期为11天,关键工序：C-F-G-H,（2）,a）画出横道表,b)调整,调整原则：,先找出那些具有最大总时差的工序在不拖延整个工程完工期的情况下，尽量往后延。,RA=11-4-0=7,RB=4-2-0=2,RE=7-3-2=3,RD=4-2-0=2,方案：,1）可将A排在8-11周中。,2）将B，E整体后移2周：,B排在3，4周,E排在5、6、7周,调整后结果，如下表：,10 10 10 10 10 10 10 10 10 10 10,注：,1.若对劳动力有具体的要求

16、，如每周不超过多少，还 可进一步调。,2.资源平衡结果不一定唯一，也不一定特别平衡。,C）评价：,利用方差公式：,其中：,TE总工期,=10,初始横道表中：,=44.727,修订后进度计算表中：,故修订后资源就更均衡了。,6.3.4 工程完工期的概率分布,一.确定平均工序时间t(i,j)的三时估计法,设工序最乐观时间为aij,设工序最保守时间为bij,设工序最可能时间为mij,求均值,求方差,说明（华罗庚）：,由实际工作情况表明，工作进行时出现最顺利和最不顺利情况都比较少，更多的是在最可能完成时间内完成。,设工时出现m的可能性两倍于出现a或b的可能性,应用加权平均法,则平均期望工时：,工时的方

17、差：,二.期望工期TE,=关键路上工序平均时间之和,工期的方差2,=关键路上工序方差之和,三.求工程在某天内完工的概率,（因为完工期为关键路线上各工序时间之和，由中心极限定理易知）,例7 某工程网络图如下：,估计工程在40天内完成的概率。,解：,（1）计算每一工序平均期望工时t(i,j),并确定关键工序。,0,12.83,20.66,21,30.33,31.33,42.5,42.5,30.33,31.5,21.17,20.66,12.83,0,关键工序：A-B-D-G,（2）计算关键工序的方差。,TE,=12.83+7.83+9.67+12.17,=1.96,=1-0.8997,=0.1003

18、,=42.5,四.求完工可能性达到95%的工期,天津大学1999年博士生入学试题,（15%）某工程可分为14道工序，有关资料如下表：,（1）请画出该工程的网络图，按正常时间求出完工期和关键路。,（2）如果要求工程在46周完成，求总赶工费用最小的赶工方案。,（3）（2）中的问题能否采用LP的方法解决？若能，请建立此问题的LP模型（不解）。,解：（1）,完工期TE=49,关键路：A-B-C-E-H-G-I-L-M,（2）计算每道工序的直接费用率。,要压缩9周（在关键工序上压）,1）先压I,=2;RD=9,RF=11,RJ=5,RK=1,RN=5,故=1所以t=1,完工期TE=48,关键路：A-B-C-E-H-G-I-L-M,2）再压I，=1;RD=9,RF=11,RJ=5,RK=1,RN=5,故=1所以t=1,完工期TE=47,关键路：A-B-C-E-H-G-I-L-M,3）再压B，=2;RD=9,RF=11,RJ=5,RK=1,RN=5,故=1所以t=1,完工期TE=46,关键路：A-B-C-E-H-G-I-L-M最小赶工方案如图所示。,（3）（2）中的问题能用线性规划的方法解决。,设决策变量Xi为工序AN的压缩时间（i=114）,