运筹学清华大学.ppt

第十一章,网络计划,章节大纲,工程计划网络图的绘制网络时间的计算关键路线与网络优化,一、工程计划网络问题（关键路径法）,问题的一般提法 设：有一项工程，分为若干道工序；已知各工序 间的先后关系，以及各工序所需时间t。问：（1）工程完工期T=？（2）工程的关键工序有哪些？,2.解法关键路径法（CPM）（1）绘制工程网络图（2）求完工期（用标号法）（3）求关键路（用标号法）,1.1 网络计划图,网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。,网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。,1.1 网络计划图,工 序,在网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如下图：,箭尾事项,箭头事项,工序之间的关系,紧前工序：紧排在本工作之前的工作；且开始或完成后，才能开始本工作。紧后工序：紧排在本工作之后的工作；本工作开始或结束后，才能开始或结束的工作。虚工序：不占用时间和不消耗人力，资金等的虚设的工作。虚工序只表示相邻工序之间的逻辑关系。,网络图的要求,相邻节点只能是一个工序的相关事项；网络图中不能有缺口和回路,应改正为,T,S,1）顺序：按工序先后从左至右；2）图中弧（箭线）：表示工序；顶点（结点）：表示相邻工序的时间分 界点，称事项，用 表示。相邻弧：表示工序前后衔接关系，称紧 前（后）工序；3）要求：图中不得有缺口、回路和多重边。,缺口：多个始点或多个终点的现象。（应当只有一个始点和终点）,绘制工程网络图,处理方法：增加虚工序。,多重边：两点间有多于一条的边。,处理方法：增加虚工序。,例1 为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试求该工程完工期T及关键路径。,回路：方向一致的闭合链。,网络计划图的时间参数计算,网络图中工作的时间参数。它们是：工作持续时间(D)；工作最早开始时间（ES）；工作最早完成时间（EF）；工作最迟开始时间（LS）；工作最迟完成时间（LF）；工作总时差（TF）；工作自由时差（FF）。,工作持续时间(D)作业时间Ti-j,单时估计法（定额法）,每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间；工作持续时间,Q 工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表示；R 可投入人力和设备的数量；S 每人或每台设备每工作班能完成的工作量；n 每天正常工作班数。或具有类似工作的持续时间的历史统计资料时，可以根据这些资料，采用分析对比的方法确定所需工作的持续时间。,三时估计法,在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是：乐观时间。在一切都顺利时，完成工作需要的最少时间，记作a。最可能时间。在正常条件下，完成工作所需要时间。记作m。悲观时间。在不顺利条件下，完成工作需要最多时间，记作b。,显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续时间值：,工作最早开始时间ES和工作最早完成时间EF工作的最早开始时间ES是紧前工序最早结束时间。ES=TE（i）EF=ES+tij工作最迟开始时间LS与工作最迟完成时间LF 工作的最迟完成时间LF是工作在不影响工期下最迟结束时间。LF=TL（j）LS=LF-TL(j)最后一项工作的最迟完成时间LF等于其最早完成时间EF,工序(i,j)的时间参数,事件最早可能发生时间Te,i,事件最迟必须发生时间Tl,网络时间的图示法,1.节点时间（事件时间）,事件最早可能发生时间TE：顺向求和取大事件最迟必须发生时间TL：反向求差取小,TE（j）=Max(TE(i)+tij),TE（1）=0,TL（i）=Min(TL(j)-tij),TL（n）=TE(n),TE(i),2.工序时间,工序A,3.工作时差：指工作有机动时间。,工作总时差TF（i-j）在不影响工期的前提下，工作所具有的机动时间,工序A,总时差为零的工序即关键工序,LS-ES=LF-EF,（2）工作自由时差FF（i-j）在不影响其紧后工作最早开始的前提下，工序最早可能完工时间所具有机动时间,工序A,（3）工作安全时差SF（i-j）在不影响其紧后工作的最迟开始的前提下，工作所具有机动时间,工序A,（2）求完工期（用标号法）,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,顺向求和取其大,（3）求关键路（用标号法）,9,Min(25,34),反向求差取其小,完工期T=38（天）；关键路：D-E-F-G-H-I-K-N。,课堂习题,求下面网络计划图中的关键路径和完工期。要求使用标号法，给出节点的TE和TL，工序的ES、EF、LS、LF以及总时差TF和自由时差FF,小结,虚工序的网络时间也应计算，以判断其是否为关键工序。（虚工作为无机动时间的关键工作；否则该虚工作即为有机动时间的非关键工作。）关键工序有2条：ADEGI和ADFHI完工期TE为19天。,i,TE TL,TFFF,二、工序时间不确定的工程计划网络问题（计划评审技术PERT）,=关键工序的平均工序时间之和；=关键工序时间方差之和。,例2 某工程可分为11项工作，有关资料如下表：,（1）画出施工网络图，确定关键路线及完工期TE；（2）估计工程在20周内完工的概率。,期望工期TE=19；关键路：A-D-J-K。,=0.6293,工程在20周内完工的概率为0.6293。,课后作业,P307 11.1,某项工程有关资料如下表：,要求：（1）画出工程网络图，计算各时间参数及总时差，自由时差（2）确定关键工序及期望完工期；（3）估计工程在30周内完工的概率。,网络优化,时间优化缩短工程工期问题时间资源优化工程的时间费用分析,缩短工程工期,保证工程质量，同时不增加人力物力的前提下，尽量缩短工期。做法：（1）确定关键路线明确关键工序，设法缩短关键工序的时间；（2）在非关键工序上挖掘潜力；（3）多采用平行作业和交叉作业；（4）注意关键路线的变化,假设E工序时间由7缩短到5，关键线路有何变化？（注意次长路径的时间）如果工程要求在35周内完工，应对哪些工序加以改进？,