运筹学课件ch11网络计划

,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,第,十,一,章,网络计划,章节大纲,工程计划网络图的绘制,网络时间的计算,关键路线与网络优化,一、工程计划网络问题（关键路径法）,问题的一般提法,设：有一项工程，分为若干道工序；已知各工序,间的先后关系，以及各工序所需时间,t,。,问：,（,1,）工程完工期,T=,？,（,2,）,工程的关键工序有哪些？,2.,解法,关键路径法（,CPM,）,（,1,）,绘制工程网络图,（,2,）求完工期（用标号法）,（,3,）求关键路（用标号法）,1.1,网络计划,图,网络计划图的基本思想是：,首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用,节点、箭线来构成网络图,。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。,网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（,CPM,）和计划评审技术（,PERT,）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。,1.1,网络计划,图,工 序,在网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（,i-j,）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如下图：,箭尾事项,箭头事项,工序之间的关系,紧前工序：,紧排在本工作之前的工作；,且开始或完成后，才能开始本工作,。,紧后工序：,紧排在本工作之后的工作；,本工作开始或结束后，才能开始或结束的工作。,虚工序：,不占用时间和不消耗人力，资金等的虚设的工作。虚工序只表示相邻工序之间的逻辑关系。,网络图的要求,相邻节点只能是一个工序的相关事项；,网络图中不能有缺口和回路,应改正为,T,S,1,2,3,4,A,B,C,1,2,3,4,5,6,D,A,B,C,E,1,）顺序：按工序先后从左至右；,2,）图中,弧（箭线）,：表示工序；,顶点（结点）,：表示相邻工序的时间分,界点，称事项，用 表示。,相邻弧,：表示工序前后衔接关系，称紧,前（后）工序；,3,）要求：图中不得有缺口、回路和多重边。,i,缺口：多个始点或多个终点的现象。,（应当只有一个始点和终点）,绘制工程网络图,处理方法：增加虚工序。,多重边：两点间有多于一条的边。,A,B,处理方法：增加虚工序。,A,A,B,例,1,为筹建某餐馆，需制定计划。将工程分为,14,道工序，各工序需时及先后关系如下表。试求该工程完工期,T,及关键路径。,回路：方向一致的闭合链。,工序,内容,紧前工序,所需,天数,A,购买炉灶及材料,10,B,购买室内设备,3,C,招集工人,1,D,选择开业地点,2,E,申请许可得到执照,D,7,F,修理门窗、粉刷墙壁,E,3,G,砌,炉灶、水池,A,、,F,5,H,接通上下水道,G,4,I,安装室内设备,B,、,H,4,J,做好室内装饰,B,、,H,3,K,购进米面及副食品,I,、,J,6,L,张贴开业广告,G,3,M,人员训练,C,、,I,4,N,开业前操作试验,K,、,L,7,工序,A,B,C,D,E,F,G,H,I,J,K,L,M,N,紧前工序,_,_,_,_,D,E,A,F,G,B,H,B,H,I,J,G,C,I,K,L,所需,天数,10,3,1,2,7,3,5,4,4,3,6,3,4,7,1,C,B,A,D,2,E,3,F,4,G,5,H,6,I,J,7,I,8,K,L,9,I,M,10,N,11,网络计划图的时间参数计算,网络图中工作的时间参数。它们是,：,工作持续时间,(,D,),；,工作最早开始时间（,ES,）；,工作最早完成时间（,EF,）；,工作最迟开始时间（,LS,）；,工作最迟完成时间（,LF,）；,工作总时差（,TF,）；,工作自由时差（,FF,）。,工作持续时间,(D),作业时间,T,i-j,单时估计法（定额法）,每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间；,工作持续时间,Q,工作的工作量。以时间单位表示,如小时,;,或以体积，重量，长度等单位表示；,R,可投入人力和设备的数量；,S,每人或每台设备每工作班能完成的工作量；,n,每天正常工作班数。,或具有类似工作的持续时间的历史统计资料时，可以根据这些资料，,采用分析对比的方法确定所需工作的持续时间。,三时估计法,在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是：,乐观时间。在一切都顺利时，完成工作需要的最少时间，记作,a,。,最可能时间。在正常条件下，完成工作所需要时间。记作,m,。,悲观时间。在不顺利条件下，完成工作需要最多时间，记作,b,。,显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续时间值：,工作最早开始时间,ES,和工作最早完成时间,EF,工作的最早开始时间,ES,是紧前工序最早结束时间。,ES=TE,（,i,）,EF=,ES+t,ij,工作最迟开始时间,LS,与工作最迟完成时间,LF,工作的最迟完成时间,LF,是工作在不影响工期下最迟结束时间。,LF=TL,（,j,）,LS=LF-,TL(j,),最后一项工作的最迟完成时间,LF,等于其最早完成时间,EF,x,y,事件最早可能发生时间,Te,i,事件最迟必须发生时间,Tl,网络时间的图示法,1.,节点时间（事件时间）,事件最早可能发生时间,TE,：顺向求和取大,事件最迟必须发生时间,TL,：反向求差取小,T,E,（,j,）,=,Max(T,E,(i)+t,ij,),T,L,（,i,）,j,i,箭尾事项,箭头事项,A,（,D,）,t,ij,a,b,c,d,Max(+),Min(-),T,E,（,1,）,=,0,T,L,（,i,）,=,Min(T,L,(j)-t,ij,),T,L,（,n,）,=,TE(n,),T,E,(i,),ES,LS,EF,LF,开始,完成,可能,必须,最早,最迟,a,d,-t,ij,a,+t,ij,d,j,i,箭尾事项,箭头事项,A,（,D,）,t,ij,a,b,c,d,2.,工序时间,工序,A,3.,工作时差：,指工作有机动时间。,工作总时差,TF,（,i-j,）,在不影响工期的前提下，工作所具有的机动时间,j,i,箭尾事项,箭头事项,A,（,D,）,t,ij,a,b,c,d,a,d,-t,ij,a,+t,ij,d,工序,A,总时差为零的工序即关键工序,LS-ES=LF-EF,j,i,箭尾事项,箭头事项,A,（,D,）,t,ij,a,b,c,d,（,2,）工作单时差,EF,（,i-j,）,在不影响其紧后工作,最早开始,的前提下，工序最早可能完工时间所具有机动时间,a,d,-t,ij,a,+t,ij,d,工序,A,j,i,箭尾事项,箭头事项,A,（,D,）,t,ij,a,b,c,d,（,3,）工作自由时差,FF,（,i-j,）,在不影响其紧后工作的,最迟开始,的前提下，工作所具有机动时间,a,d,-t,ij,a,+t,ij,d,工序,A,（,2,）求完工期（用标号法）,1,）标出各事项的,最早开始,时间 ，,-,给始点 标 ；,-,给任意点,标,E,j,=Max,以 为箭头的各箭之,“箭尾,+,箭长,t,ij,”,1,0,j,E,j,j,2),终点 的 中的,T,即完工期。,n,T,1,C(1),B(3),A(10),D(2),2,E(7),3,F(3),4,G(5),5,H(4),6,I(4),J(3),7,I(0),8,K(6),L(3),9,I,(0),M(4),10,N(7),11,0,2,9,12,17,21,25,25,31,25,38,顺向求和取其大,（,3,）求关键路（用标号法）,2,）计算各工序 的,时差,R(i,j)=,的,-,t,ij,-,的 。,i,j,j,i,1,）标出各事项的最晚开始时间 ，,-,给终点 标 ；,-,给任意点 标,L,i,=Min,以,为箭尾的各箭之“箭头,-,箭长,t,ij,”,n,i,L,i,i,T,3,）关键路径：由,R(i,j)=0,的,关键工序组成的由 至 的路。,n,1,9,1,C(1),B(3),A(10),D(2),2,E(7),3,F(3),4,G(5),5,H(4),6,I(4),J(3),7,I(0),8,K(6),L(3),I,(0),M(4),10,N(7),11,0,2,9,12,17,21,25,25,31,25,38,38,25,34,25,21,31,17,12,9,2,0,M,in(25,34),反向求差取其小,工序,箭尾节点,i,所需天数,箭头节点,j,ES,EF,LS,LF,总时差,d-t-a,单时差,c-t-a,自由时差,d-t-b,a,b,c,d,A,0,0,10,12,12,0,10,2,12,2,2,2,B,0,0,3,21,21,0,3,19,21,19,18,18,C,0,0,1,25,34,0,1,33,34,33,24,33,D,0,0,2,2,2,0,2,0,2,0,0,0,E,2,2,7,9,9,2,9,2,9,0,0,0,F,9,9,3,12,12,9,12,9,12,0,0,0,G,12,12,5,17,17,12,17,12,17,0,0,0,H,17,17,4,21,21,17,21,17,21,0,0,0,I,21,21,4,25,25,21,25,21,25,0,0,0,J,21,21,3,25,25,21,24,22,25,1,1,1,K,25,25,6,31,31,25,31,25,31,0,0,0,L,17,17,3,31,31,17,20,28,31,11,11,11,M,25,34,4,38,38,25,29,34,38,9,9,0,N,31,31,7,38,38,31,38,31,38,0,0,0,ES,LS,EF,LF,1,7,9,11,8,10,6,2,3,4,5,A(10),B(3),C(1),D(2),E(7),F(3),G(5),H(4),I(4),J(3),L(3),K(6),M(4),N(7),ES,LS,EF,LF,完工期,T=38,（,天）；,关键路：,D-E-F-G-H-I-K-N,。,由本例,可见：,关键工序 头尾皆有,=,，但反之未必。,关键工序时间之和,=,工期,T,。,二、工序时间不确定的工程计划网络问题 （计划评审技术,PERT,）,=,关键工序的平均工序时间之和；,=,关键工序时间方差之和。,例,2,某工程可分为,11,项工作，有关资料如下表：,工作,紧前,工作,工序时间,a,m,b,A,B,C,D,E,F,G,H,I,J,K,-,-,-,A,B,B,C,C,G,、,H,D,、,E,F,、,I,、,J,1,1,1,1,2,3,2,1,1,1,4,2,2,2,10.5,5,6,3,2,4,2,4,3,3,3,17,14,15,10,9,7,9,4,（,1,）画出施工网络图，确定关键路线及完工期,T,E,；,（,2,）,估计工程在,20,周内完工的概率。,工作,紧前,工作,工序时间,a,m,b,A,B,C,D,E,F,G,H,I,J,K,-,-,-,A,B,B,C,C,G,、,H,D,、,E,F,、,I,、,J,1,1,1,1,2,3,2,1,1,1,4,2,