运筹学第二章网络计划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 网络计划,关键线路法(,critical path method,，,简称,CPM,),计划评审法(,program,evaluation,and,review,technique,，,简称,PERT,),2.1确定性网络图,2.2概率型网络图,2.3网络图的优化,2.1确定性网络图,2.1.1概念：,工序(作业、活动、工作)：指任何消耗时间或资源的行动。,紧前工序：在另一工序开始前必须完成的工序。,单代号工序图,代号,时间,工序名称,ES,LF,LS,EF,ES,一项活动可能最早开始的时间；,EF,一项活动可能最早完成的时间；,LS,在不增加整个项目的完成时间的条件下，一项活动可能开始的最晚时间；,LF,在不增加整个项目的完成时间的条件下，一项活动可能完成的最晚时间。,建筑工程网络的工序一览表,工序,工序说明,紧前工序,工序时间,工序,工序说明,紧前工序,工序时间,A,挖掘,2,H,外部上漆,E,G,9,B,打地基,A,4,I,电路铺设,C,7,C,承重墙施工,B,10,J,竖墙板,F,I,8,D,封顶,C,6,K,铺地板,J,4,E,安装外部管道,C,4,L,内部上漆,J,5,F,安装内部管道,E,5,M,安装外部管道,H,2,G,外墙施工,D,7,N,安装内部管道,K,L,6,确定性网络图：每个工序时间只有一个估计值。,2.1.2网络图,绘制,过程,1.列出工序一览表；,2.绘制网络图,开工工序,开工工序的紧后工序，用箭号相连；,所有紧前工序已绘出的工序，用箭号相连；,3.重复上述步骤 ，直至绘出所有工序节点。,建筑工程网络图,I,M,H,G,D,L,A,N,K,J,F,C,E,B,建筑工程网络图,S,T,I,M,H,G,D,L,A,N,K,J,F,C,E,B,源节点,终结点,单代号网络图的特点,1.网络图中的结点不限定只有一个开工节点或完工节点；,2.工序节点的编号不要求按时间大小编号。(最好按时间大小编号,),2.1.3 时间参数的计算,(1) 工序(结点和活动)的最早时间,(2),工序,(,结点和活动,),的最迟时间,(1) 工序的最早时间,分最早开始时间和最早结束时间。,设工序为,i,，,工序为,i,的持续时间为,D,i,，,ES,i,为工序,i,最早开始时间,，,EF,i,为工序,i,最早结束时间。,计算顺序为顺推：,ES,0,0，,EF,0,D,0,，,EF,i,ES,i,D,i,工序按时间大小编号,(2) 工序的最迟时间,分最迟开始时间和最迟结束时间。,设工序为,i,，,工序为,i,的持续时间为,D,i,，,LS,i,为工序,i,最开始时间,，,LF,i,为工序,i,最迟结束时间。,计算顺序为逆推：,LF,n,EF,n,，,LS,n,LF,n,D,n,，,LS,i,LF,i,D,i,工序按时间大小编号,(3)时差,单时差(时间间隔参数)：表示前一工序,i,最早结束至后,一项工序,j,最早开始的时间间隔。,LAG,i,-,j,ES,j,EF,i,工序,i,j,2,j,1,1.局部时差,工序,i,j,2,j,1,不影响所有紧后工序的最早开始时间，此工序可以推后的时间(机动时间,)。,2.总时差,不影响工程(任务总工期,),最早结束时间的条件,下，某工序可以推迟的时间(机动时间,),。,(4)关键路线,网络图中从始点到终点的一条路称为一条路线由全部关键活动组成的路线叫关键路线。,在网络图上从起点到终点，依次将总时差为0的各项,工序,连接起来的路线就是关键路线(项目网络图中最长的线路),总时差为0是关键路线上各项,工序,的特征，在网络图上从起点到终点，依次将总时差为0的各项,工序,连接起来的路线就是关键路线,单代号网络图时间参数的计算,计算顺序指标,工序,代号,工序,名称,紧前,工序,后续,工序,Di,ES,EF,LS,LF,TF,0,S,A,0,1,A,B,2,2,B,A,C,4,3,C,B,D,E,I,10,4,D,C,G,6,5,E,C,F,H,4,6,F,E,J,5,7,G,D,H,7,8,H,E,G,M,9,9,I,C,J,7,10,J,F,I,K,L,8,11,K,J,N,4,12,L,J,N,5,13,M,H,T,2,14,N,K,L,T,6,15,T,N,0,单代号网络图时间参数的计算,计算顺序指标,工序,代号,工序,名称,紧前,工序,后续,工序,Di,ES,EF,0,S,A,0,0,0,1,A,B,2,0,2,2,B,A,C,4,2,6,3,C,B,D,E,I,10,6,16,4,D,C,G,6,16,22,5,E,C,F,H,4,16,20,6,F,E,J,5,20,25,7,G,D,H,7,22,29,8,H,E,G,M,9,20/29=29,38,9,I,C,J,7,16,23,10,J,F,I,K,L,8,25/23=25,33,11,K,J,N,4,33,37,12,L,J,N,5,33,38,13,M,H,T,2,38,40,14,N,K,L,T,6,37/38=38,44,15,T,N,0,44,44,单代号网络图时间参数的计算,计算顺序指标,工序,代号,工序,名称,紧前,工序,后续,工序,Di,ES,EF,LS,LF,0,S,A,0,0,0,0,0,1,A,B,2,0,2,0,2,2,B,A,C,4,2,6,2,6,3,C,B,D,E,I,10,6,16,6,16/21/18=16,4,D,C,G,6,16,22,20,26,5,E,C,F,H,4,16,20,16,33/20=20,6,F,E,J,5,20,25,20,25,7,G,D,H,7,22,29,26,33,8,H,E,G,M,9,20/29=29,38,33,42,9,I,C,J,7,16,23,18,25,10,J,F,I,K,L,8,25/23=25,33,25,33,11,K,J,N,4,33,37,34,38,12,L,J,N,5,33,38,33,38,13,M,H,T,2,38,40,42,44,14,N,K,L,T,6,37/38=38,44,38,44,15,T,N,0,44,44,44,44,单代号网络图时间参数的计算,计算顺序指标,工序,代号,工序,名称,紧前,工序,后续,工序,Di,ES,EF,LS,LF,TF,0,S,A,0,0,0,0,0,0,1,A,B,2,0,2,0,2,0,2,B,A,C,4,2,6,2,6,0,3,C,B,D,E,I,10,6,16,6,16/20/18=16,0,4,D,C,G,6,16,22,20,26,4,5,E,C,F,H,4,16,20,16,33/20=20,0,6,F,E,J,5,20,25,20,25,0,7,G,D,H,7,22,29,26,33,4,8,H,E,G,M,9,20/29=29,38,33,42,3,9,I,C,J,7,16,23,18,25,2,10,J,F,I,K,L,8,25/23=25,33,25,33,0,11,K,J,N,4,33,37,34,38,1,12,L,J,N,5,33,38,33,38,0,13,M,H,T,2,38,40,42,44,4,14,N,K,L,T,6,37/38=38,44,38,44,0,15,T,N,0,44,44,44,44,0,关键路线,I,M,H,G,D,L,A,N,K,J,F,C,E,B,关键路线,S,T,I,M,H,G,D,L,A,N,K,J,F,C,E,B,10,9,8,7,6,5,3,2,4,1,10,9,8,7,6,5,3,2,4,1,S,T,注意：各工序之间的关系,工序,工序,时间,紧前,工序,后续,工序,最早时间,最迟时间,总时差,ES,EF,LS,LF,S,0,1,2,1,5,S,3,4,2,6,S,5,6,3,3,1,5,6,4,2,1,7,8,5,4,2,3,7,8,6,7,2,3,10,7,4,4,5,9,8,6,4,5,10,9,3,7,T,10,5,6,8,T,T,0,9,10,单代号网络图时间参数的计算,工序,工序,时间,紧前,工序,后续,工序,最早时间,最迟时间,总时差,ES,EF,LS,LF,S,0,1,2,0,0,1,5,S,3,4,0,5,2,6,S,5,6,0,6,3,3,1,5,6,5,8,4,2,1,7,8,5,7,5,4,2,3,7,8,6/8=8,12,6,7,2,3,10,6/8=8,15,7,4,4,5,9,7/12=12,16,8,6,4,5,10,7/12=12,18,9,3,7,T,16,19,10,5,6,8,T,15/18=18,23,T,0,9,10,19/23=23,23,单代号网络图时间参数的计算,工序,工序,时间,紧前,工序,后续,工序,最早时间,最迟时间,总时差,ES,EF,LS,LF,S,0,1,2,0,0,0,0/2=0,1,5,S,3,4,0,5,0,5/10=5,2,6,S,5,6,0,6,2,8/11=8,3,3,1,5,6,5,8,5,8/11=8,4,2,1,7,8,5,7,10,14/12=12,5,4,2,3,7,8,6/8=8,12,8,14/12=12,6,7,2,3,10,6/8=8,15,11,18,7,4,4,5,9,7/12=12,16,14,18,8,6,4,5,10,7/12=12,18,12,18,9,3,7,T,16,19,20,23,10,5,6,8,T,15/18=18,23,18,23,T,0,9,10,19/23=23,23,23,23,单代号网络图时间参数的计算,工序,工序,时间,紧前,工序,后续,工序,最早时间,最迟时间,总时差,ES,EF,LS,LF,S,0,1,2,0,0,0,0/2=0,0*,1,5,S,3,4,0,5,0,5/10=5,0*,2,6,S,5,6,0,6,2,8/11=8,2,3,3,1,5,6,5,8,5,8/11=8,0*,4,2,1,7,8,5,7,10,14/12=12,5,5,4,2,3,7,8,6/8=8,12,8,14/12=12,0*,6,7,2,3,10,6/8=8,15,11,18,3,7,4,4,5,9,7/12=12,16,14,18,2,8,6,4,5,10,7/12=12,18,12,18,0*,9,3,7,T,16,19,20,23,4,10,5,6,8,T,15/18=18,23,18,23,0*,T,0,9,10,19/23=23,23,23,23,单代号网络图时间参数的计算,10,9,8,7,6,5,3,2,4,1,S,T,单时差与总时差的区别,t,ES,t,LS,t,EF,t,LF,t,ES,t,LS,t,EF,t,LF,t,ES,t,LS,t,EF,t,LF,工序,a,a,的单时差(是否=局部时差？,),a,的总时差,工序,b,工序,c,2.2概率型网络图,在不具备定额和类似工序作业时间消耗的统计资料，且作业时间较长，未知的和难估计的因素较多的情况下，对完成工序可估计三种时间，之后计算它们的平均时间作为该工序的作业时间。,三种时间是,1.乐观时间：,t,a,2.最可能时间：,t,m,3.悲观时间：,t,b,工序的作业时间(期望,),与方差,概率型网络图假设：,1.各工序的时间分布相互随机独立；,2.关键线路一直比其他任何线路所需时间都长；,3.工程时间的概率分布是一个正态分布。,工程项目时间的概率分布（一：正态分布）,t,a,t,b,t,m,工程项目时间的概率分布（二：,分布,）,t,a,t,b,t,m,工程项目时间的概率分布（三：,分布）,t,a,t,b,t,m,若在关键线路上有,s,道工序,则工程完工时间可以,认为,是一个以,为均值，以,为方差的正态分布。,例：已知某项工程，关键线路上有,5,道关键工序，各关键工序的平均作业时间和方差如表所示。试求完成该工程的周期及完工时间为60天的概率。,工序,T,2,c,10.50,1.36,d,10.16,0.25,f,20.33,4.00,g,5.16,0.25,h,12.83,14.67,计算过程,查标准正态分布表得：0.5871。即工程在60天完成的概率为0.5871。,数据的输入,PERT,的费用优化问题的分析结果,关键线路(红色),概率型网络横道图(甘特图),A,的紧后工序为,D,、,E,，,D,的紧后工序为,H,E,的紧后工序为,K,，,PERT,的期望时间内完工的可能性分析,PERT,模拟,PERT,模拟结果,CPM/PERT,小结,第一步：列举出构成该项目的所有活动。,第二步：决定项目中每项活动的紧前活动。,第三步：预期每项活动的完成时间。,第四步：绘制网络图。,第五步：利用网络图计算工序的最早时间，令项目最后一项活动的最早完成时间为该项目所需的总时间。,第六步：利用网络图计算工序的最迟时间。,第七步：计算每项活动的总时差。,第八步：找出关键活动，确定关键线路。,第九步：利用第五、六步的信息，涉及整个项目的活动时间表。,2.3网络图的优化,1.时间资源的优化,2.时间费用的优化,1.时间资源的优化,教材,P78,例2.3,网络图中，以计算出关键线路为,A,D,E,G,总工期为11天。中为工序代号，上方标注的数字为工序工时，下方标注的数字为每天所需人力数，已知现有工人数为10人，并假设这些工人可以完成所有工序中的任何一个工序。试对此人力资源分配进行优化。,人力资源的网络计划图,A,B,D,C,F,E,G,2,6,4,9,2,7,3,3,3,5,3,4,4,1,工序代号,工序工时,工序所需人力数,工程进度表(单位：天),工序,工时,t,总时差,TF,工程进度(天),1,2,3,4,5,6,7,8,9,10,11,A,2,0,6,6,B,4,7,9,9,9,9,C,2,0,3,3,3,D,3,1,7,7,E,3,0,5,5,5,F,3,1,4,4,4,G,4,0,1,1,1,1,：为总时差，人力限制10人。,资源优化的要求：,1.优先安排关键工序所需资源；,2.利用总时差，错开各工序的开始时间，拉平资源需要量的高峰。,3.在确实受到资源限制，或者在综合考虑经济效益的条件下，也可适当推迟工程的完工时间。,按最早时间安排的各工序所需人力图,调整后的工程进度表(单位：天),工序,工时,t,总时差,TF,工程进度(天),1,2,3,4,5,6,7,8,9,10,11,A,2,0,6,6,B,4,7,9,9,9,9,C,2,0,3,3,3,D,3,1,7,7,E,3,0,5,5,5,F,3,1,4,4,4,G,4,0,1,1,1,1,：为总时差，人力限制10人。,调整后的时间安排的各工序所需人力图,2.时间费用的优化,最小直接为用的关键工序调整法：,费用分为：间接费用和直接费用。,费用与时间的关系,总费用,直接费用,间接费用,极限时间,正常时间,T,工程(工序)费用,T,：为使得工程费用最低的工程完工时间,时间,间接费用和直接费用,1.直接费用：包括直接生产工人的工资及附加费，设备能源、工具及材料消耗等直接与完成工序有关的费用。,2.间接费用：包括管理人员的工资、办公费等。,直接费用与工序所需工时的关系,直接费用,A,(,极限工序),B,(,正常工序),工时,D,i,d,i,教材,P79,例2.4,若公司能提前完成工程的话，有可能得到奖励。下表为建筑工程中每项工序的时间成本平衡的数据，现在的问题是：,1.若要用额外的资金来加速工程进度的话，怎样才能以最低的成本在40周内完工？,2.若要把工程完成时间下降到40周之内，则对一些工序进行应急处理最节省的途径是什么?,建筑工程中每项工序的时间成本平衡的数据,工序,(红色为关键工序),时间(周,),成本(万元,),每周的,应急成本,正常,应急,正常,应急,A,2,1,18,28,10,B,4,2,32,42,5,C,10,7,62,86,8,D,6,4,26,34,4,E,4,3,41,57,16,F,5,3,18,26,4,G,7,4,90,102,4,H,9,6,20,38,6,I,7,5,21,27,3,J,8,6,43,49,3,K,4,3,16,20,4,L,5,3,25,35,5,M,2,1,10,20,10,N,6,3,33,51,6,J,工期86单代号网络图时间参数的计算,计算顺序指标,工序,代号,工序,名称,紧前,工序,后续,工序,工期,D,i,ES,EF,LS,LF,TF,0,S,A,0,0,0,0,0,0,1,A,B,2,0,2,0,2,0,2,B,A,C,4,2,6,2,6,0,3,C,B,D,E,I,10,6,16,6,16/20,(18),/18=16,0,4,D,C,G,6,16,22,20 ,18,26 ,24,4,(2),5,E,C,F,H,4,16,20,16,33,(31),/20=20,0,6,F,E,J,5,20,25,20,25,0,7,G,D,H,7,22,29,26 ,24,33 ,31,4,(2),8,H,E,G,M,9,20/29=29,38,33 ,31,42 ,40,3,(2),9,I,C,J,7,16,23,18,25,2,10,J,F,I,K,L,8,6,25/23=25,33 ,31,25,34/33=33,(32/31=31),0,11,K,J,N,4,33,31,37 ,35,34 ,32,38 ,36,1,12,L,J,N,5,33,31,38 ,36,33 ,31,38 ,36,0,13,M,H,T,2,38,40,42 ,40,44 ,42,4,(2),14,N,K,L,T,6,37,(35),/38,(36),=38,(36),44 ,42,38,(36),44 ,42,0,15,T,N,0,44,42,44 ,42,44 ,42,44 ,42,0,J,工期8,6,原来的关键,路线仍未变(一条)，但总工期为42周,S,T,I,M,H,G,D,L,A,N,K,J,F,C,E,B,F,工期53单代号网络图时间参数的计算,计算顺序指标,工序,代号,工序,名称,紧前,工序,后续,工序,工期,D,i,ES,EF,LS,LF,TF,0,S,A,0,0,0,0,0,0,1,A,B,2,0,2,0,2,0,2,B,A,C,4,2,6,2,6,0,3,C,B,D,E,I,10,6,16,6,18/16/18=16,(16/16/16=16,0,4,D,C,G,6,16,22,18 ,16,24 ,22,2,(0),5,E,C,F,H,4,16,20,16,31/20=20,(29/20=20),0,6,F,E,J,5 ,3,20,25,23,20,25 ,23,0,7,G,D,H,7,22,29,24 ,22,31 ,29,2,(0),8,H,E,G,M,9,20/29=29,38,31 ,29,40 ,38,2,(0),9,I,C,J,7,16,23,18 ,16,25 ,23,2,(0),10,J,F,I,K,L,6,25,(23),/23=25,23,31,29,25 ,23,32/31=31,(30/29=29),0,11,K,J,N,4,31,29,35 ,33,32 ,30,36 ,34,1,12,L,J,N,5,31 ,29,36 ,34,31 ,29,36 ,34,0,13,M,H,T,2,38,40,40 ,38,42 ,40,2,(0),14,N,K,L,T,6,35 /36=36,(33/34=34),42 ,40,36,34,42 ,40,0,15,T,N,0,42 ,40,42 ,40,42 ,40,42 ,40,0,F,工期5,3,原来的关键,路线已改变（有三条），且总工期为40周,S,T,I,M,H,G,D,L,A,N,K,J,F,C,E,B,PERT,的费用优化问题的类型选择,PERT,的费用优化问题的数据输入,PERT,的费用优化问题的时间选择,PERT,的费用优化问题的分析结果,PERT,的费用优化问题的图表分析,PERT,的费用优化问题的关键线路分析,PERT,的费用优化问题的甘特图分析,