运筹学课件ch11网络计划

1、第第十一十一章章章节大纲章节大纲1.工程计划网络图的绘制工程计划网络图的绘制2.网络时间的计算网络时间的计算3.关键路线与网络优化关键路线与网络优化一、工程计划网络问题（关键路径法）一、工程计划网络问题（关键路径法）1. 问题的一般提法 设：有一项工程，分为若干道工序；已知各工序 间的先后关系，以及各工序所需时间t。 问：（1）工程完工期t=？ （2）工程的关键工序有哪些？2.解法关键路径法（cpm）（1）绘制工程网络图（2）求完工期（用标号法）（3）求关键路（用标号法）1.1 网络计划网络计划图图v 网络计划图的基本思想是：首先应用网络计划图来表示首先应用网络计划图来表示工程项目中计划要完成

2、的各项工作，完成各项工作必然工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用存在先后顺序及其相互依赖的逻辑关系；这些关系用节节点、箭线来构成网络图点、箭线来构成网络图。网络图是由左向右绘制，表示。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划

3、进行有效寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。最小的消耗取得最大的经济效果。v网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（cpm）和计划评审技术（pert）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。1.1 网络计划网络计划图图工工 序序v 在网络计划图中，用箭线表示工作，箭尾的节点表示在网络计划图中，用箭线表示工作，箭尾的节点表示工作的开

4、始点，箭头的节点表示工作的完成点。用工作的开始点，箭头的节点表示工作的完成点。用（i-ji-j）两个代号及箭线表示一项工作。在箭线上标）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如下图：记必须的信息，如下图： ji持续时间工作名称或代号箭箭尾尾事事项项箭箭头头事事项项工序之间的关系工序之间的关系v紧前工序：紧前工序：紧排在本工作之前的工作；紧排在本工作之前的工作；且开始且开始或完成后，才能开始本工作或完成后，才能开始本工作。v紧后工序：紧后工序：紧排在本工作之后的工作；紧排在本工作之后的工作；本工作本工作开始或结束后，才能开始或结束的工作。开始或结束后，才能开始或结束的工作。v虚工序

5、：虚工序：不占用时间和不消耗人力，资金等的不占用时间和不消耗人力，资金等的虚设的工作。虚工序只表示相邻工序之间的逻虚设的工作。虚工序只表示相邻工序之间的逻辑关系。辑关系。网络图的要求网络图的要求v相邻节点只能是一个工序的相关事项；相邻节点只能是一个工序的相关事项；v网络图中不能有缺口和回路网络图中不能有缺口和回路应改正为ts1234abc123456dabce1）顺序：按工序先后从左至右；2）图中弧（箭线）：表示工序； 顶点（结点）：表示相邻工序的时间分 界点，称事项，用 表示。 相邻弧：表示工序前后衔接关系，称紧 前（后）工序；3）要求：图中不得有缺口、回路和多重边。i缺口：多个始点或多个终

6、点的现象。 （应当只有一个始点和终点）绘制工程网络图绘制工程网络图处理方法：增加虚工序。多重边：两点间有多于一条的边。ab处理方法：增加虚工序。aab例例1 为筹建某餐馆，需制定计划。将工程分为为筹建某餐馆，需制定计划。将工程分为14道工序，各工序道工序，各工序需时及先后关系如下表。试求该工程完工期需时及先后关系如下表。试求该工程完工期t及关键路径。及关键路径。回路：方向一致的闭合链。1cbad2e3f4g5h6ij7i8kl9im10n11网络计划图的时间参数计算网络计划图的时间参数计算网络图中工作的时间参数。它们是网络图中工作的时间参数。它们是：v工作持续时间工作持续时间(d)(d)； v

7、工作最早开始时间（工作最早开始时间（eses）；）； v工作最早完成时间（工作最早完成时间（efef）；）；v工作最迟开始时间（工作最迟开始时间（lsls）；）；v工作最迟完成时间（工作最迟完成时间（lflf）；）；v工作总时差（工作总时差（tftf）；）；v工作自由时差（工作自由时差（ffff）。）。v工作持续时间工作持续时间(d)作业时间作业时间ti-j 单时估计法（定额法）单时估计法（定额法）v 每项工作只估计或规定一个确定的持续时间值的方法。一般具有每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工工作的工作量，劳动定额资料

8、以及投入人力的多少等，计算各工作的持续时间；作的持续时间； v 工作持续时间工作持续时间 nsrqdq 工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表示；r 可投入人力和设备的数量；s 每人或每台设备每工作班能完成的工作量；n 每天正常工作班数。或具有类似工作的持续时间的历史统计资料时，可以根据这些资料，采用分析对比的方法确定所需工作的持续时间。 三时估计法三时估计法v在不具备有关工作的持续时间的历史资料时，在较在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个

9、时间值是：时间值，然后计算其平均值。这三个时间值是：v乐观时间。在一切都顺利时，完成工作需要的最少乐观时间。在一切都顺利时，完成工作需要的最少时间，记作时间，记作a。v最可能时间。在正常条件下，完成工作所需要时间。最可能时间。在正常条件下，完成工作所需要时间。记作记作m。v悲观时间。在不顺利条件下，完成工作需要最多时悲观时间。在不顺利条件下，完成工作需要最多时间，记作间，记作b。v 显然上述三种时间发生都具有一定的概率，根据经验，显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时

10、估计的数据。可以认为：工作过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续现正常的情况。按平均意义可用以下公式计算工作持续时间值：时间值： 226;64abbmad方差v工作最早开始时间工作最早开始时间es和工作最早完成时间和工作最早完成时间ef工作的最早开始时间工作的最早开始时间es是紧前工序最早结束时间。是紧前工序最早结束时间。es=te（i） ef=es+tijv工作最迟开始时间工作最迟开始时间ls与工作最迟完成时间与工作最迟完成时间lf 工作的

11、最迟完成时间工作的最迟完成时间lf是工作在不影响工期下最迟是工作在不影响工期下最迟结束时间。结束时间。lf=tl（j） ls=lf-tl(j)最后一项工作的最迟完成时间最后一项工作的最迟完成时间lf等于其最早完成时等于其最早完成时间间efxy事件最早事件最早可能发生可能发生时间时间tei事件最迟事件最迟必须发生必须发生时间时间tl网络时间的图示法网络时间的图示法1. 节点时间（事件时间）节点时间（事件时间）事件最早可能发生时间事件最早可能发生时间te：顺向求和取大：顺向求和取大事件最迟必须发生时间事件最迟必须发生时间tl：反向求差取小：反向求差取小te（j）=max(te(i)+tij)tl（

12、i）ji箭尾箭尾事项事项箭头箭头事项事项a（d）tijabcdmax(+)min(-)te（1）=0tl（i）=min(tl(j)-tij)tl（n）=te(n)te(i)开始开始完成完成可能可能必须必须最早最早最迟最迟ji箭尾箭尾事项事项箭头箭头事项事项a（d）tijabcd2.工序时间工序时间工序工序a3.工作时差：工作时差：指工作有机动时间。指工作有机动时间。 工作总时差工作总时差tf（i-j） 在不影响工期的前提下，工作所具有的机动时间ji箭尾箭尾事项事项箭头箭头事项事项a（d）tijabcdijdta总时差工序工序a总时差为零的工序即关键工总时差为零的工序即关键工序序ls-es=lf

13、-efji箭尾箭尾事项事项箭头箭头事项事项a（d）tijabcd（2）工作单时差）工作单时差ef（i-j）在不影响其紧后工作在不影响其紧后工作最早开始最早开始的前提下，工序最早可能完工时间所具有的前提下，工序最早可能完工时间所具有机动时间机动时间atcij单时差工序工序aji箭尾箭尾事项事项箭头箭头事项事项a（d）tijabcd（3）工作自由时差）工作自由时差ff（i-j）在不影响其紧后工作的在不影响其紧后工作的最迟开始最迟开始的前提下，工作所具有机动时间的前提下，工作所具有机动时间btdij自由时差工序工序a（2）求完工期（用标号法）1）标出各事项的最早开始最早开始时间 ， -给始点 标 ；

14、 -给任意点 标 ,ej=max以 为箭头的各箭之 “箭尾 +箭长tij”10jejj2) 终点 的 中的t即完工期。nt1c(1)b(3)a(10)d(2)2e(7)3f(3)4g(5)5h(4)6i(4)j(3)7i(0)8k(6)l(3)9i(0)m(4)10n(7)110291217212525312538顺向求和取其大顺向求和取其大（3）求关键路（用标号法）2）计算各工序 的时差时差r(i,j)= 的 -tij - 的 。ijji1）标出各事项的最晚开始时间 ， -给终点 标 ； -给任意点 标 ,li=min以 为箭尾的各箭之 “箭头 -箭长tij”niliit3）关键路径：由r(

15、i,j)= 0的关键工序组成的由 至 的路。n191c(1)b(3)a(10)d(2)2e(7)3f(3)4g(5)5h(4)6i(4)j(3)7i(0)8k(6)l(3)i(0)m(4)10n(7)1102912172125253125383825342521311712920min(25,34)反向求差取其小反向求差取其小1791181062345a(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)341330003425383822991212313117172121252525253829342538383131完工期t=3

16、8（天）；关键路：d-e-f-g-h-i-k-n。由本例可见：关键工序 头尾皆有 = ，但反之未必。 关键工序时间之和=工期t。 二、工序时间不确定的工程计划网络问题二、工序时间不确定的工程计划网络问题 （计划评审技术（计划评审技术pert）的区别仅在于：与cpm1.。，服从于近似认为但由中心极限定理，可也是随机的。期是随机变量，从而完工工序时间)( 2的三时估计法：确定平均工序时间，最可能时间为，最悲观时间为设工序最乐观时间为226 ,64 的方差为则工期方差期望工期=关键工序的平均工序时间之和；=关键工序时间方差之和。天内完工的概率求工程在222 (,),()() ()()1( )()2e

17、keekkekezxtn tttttp ttpttttp zzp zzedx 由标准正态分布数值表可查得：例例2 某工程可分为某工程可分为11项工作，有关资料如下表：项工作，有关资料如下表：工作紧前工作工序时间ambabcdefghijk-abbccg、hd、ef、i、j1111232111422210.55632424333171415109794（1）画出施工网络图，确定关键路线及完工期te；（2）估计工程在20周内完工的概率。工作紧前工作工序时间ambabcdefghijk-abbccg、hd、ef、i、j1111232111422210.556324243331714151097942

18、ij2221067434340.330.330.332.672.002.001.331.331.001.3300.110.110.117.134.004.001.771.771.001.7701b(2)a(2)c(2)2d(10)e(6)35f(7)4g(4)67h(3)8i(4)j(3)9k(4)19022212561519151211117620期望工期te=19；关键路：a-d-j-k。33.00101.332.670.33 (2)22220.31 0.32 0.33 0.34 0.350.6217 0.6255 0.6293 0.6331 0.6338标准正态分布数值表=0.6293工程在20周内完工的概率为0.6293。19 20课后作业课后作业p307 11.1某项工程有关资料如下表：某项工程有关资料如下表：要求要求： （1）画出工程网络图，计算各时间参数及总时差，单时差，自由时差）画出工程网络图，计算各时间参数及总时差，单时差