运筹学第07讲计划评审技术

1、1956年，美国年，美国杜邦公司杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划计划。这种计划借助于网络表示：各项工作与所需要的时间；各项工作的相互关系；借助于网络表示：各项工作与所需要的时间；各项工作的相互关系；分析研究工程费用与工期的相互关系；找出在编制计划时及计划执行过程中的关键分析研究工程费用与工期的相互关系；找出在编制计划时及计划执行过程中的关键路线。路线。这种方法称为这种方法称为关键路线法关键路线法（Critical Path Method）简称）简称CPM。1958年，美国海军武器部，在制定研制年，美国

2、海军武器部，在制定研制“北极星北极星”导弹计划时，同样地应用了网导弹计划时，同样地应用了网络分析方法与网络计划。它络分析方法与网络计划。它注重于对各项工作安排的评价和审查注重于对各项工作安排的评价和审查。这种计划称为。这种计划称为计划评审方法计划评审方法（Program Evaluation and Review Technique）简称为）简称为PERT。国内外应用国内外应用计划评审方法计划评审方法的实践表明，具有一系列优点，特别适用于生产技术复杂，的实践表明，具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如新产品研制开发、大型工作项目繁多、且联系

3、紧密的一些跨部门的工作计划。例如新产品研制开发、大型工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排，合理组织报表、文件流程等方面。源的安排，合理组织报表、文件流程等方面。把项目当作一个系统，采用把项目当作一个系统，采用和和的形式表示各具体活动的形式表示各具体活动的先后顺序和相互关系，以的先后顺序和相互关系，以为中心、以为中心、以为主要约束条件，找出从开工为主要约束条件，找出从开工到完工所需时间最长的到完工所需时间最长的，围绕关键路线，对系统进行统筹规划、合理安排，围绕关键路线，对系统进行统

4、筹规划、合理安排，对各项活动的完成进度严密控制，达到用对各项活动的完成进度严密控制，达到用消耗完成系统预定消耗完成系统预定目标的一种目标的一种与与。例：例：某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如表所某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如表所示。要求编制该项工程的网络计划。示。要求编制该项工程的网络计划。工工 序序 代号代号 所需时间所需时间( (天天) ) 紧后工序紧后工序 产品设计与工艺设计产品设计与工艺设计 a a6565b b，c c，d d，e e 外购配套件外购配套件 b b4545l l 下料、锻件下料、锻件 c c1010f f 工

5、装制造工装制造1 1 d d2020g g，h h 木模、铸件木模、铸件 e e4040h h 机械加工机械加工1 1 f f1818l l 工装制造工装制造2 2 g g3030k k 机械加工机械加工2 2 h h1515l l 机械加工机械加工3 3 k k2525l l 装配调试装配调试 l l3535产品设计与工艺设计产品设计与工艺设计 a65b，c，d，e 12a65b 45 c10d2040e外购配套件外购配套件 b45l 下料、锻件下料、锻件 c10f 工装制造工装制造1 d20，0g，h 木模、铸件木模、铸件 e40h 1246735a6545 c10d20e40fgl0b8

6、h机械加工机械加工1 f18l 工装制造工装制造2 g30k 机械加工机械加工2 h15l 机械加工机械加工3 k25l 装配调试装配调试 l3512467835a6545 c10d20e40f18g30h15k25l350 b任何任何需要一定的人力、物力等资源和时间的行动，它是指为了完成需要一定的人力、物力等资源和时间的行动，它是指为了完成工程项目。在工程项目。在工艺技术和组织管理上相对独立的工艺技术和组织管理上相对独立的工作或活动工作或活动。清理现场清理现场8 8（天）（天）a ai ij ji ib b需要时间的工序需要时间的工序。可能不需要人力、物力可能不需要人力、物力。：工时为：工时

7、为0的的工序工序。不需要人力、物力，不存在。表明工序间的逻辑关系。不需要人力、物力，不存在。表明工序间的逻辑关系。工序工序都有两个事项都有两个事项-开工事项、完工事项。开工事项、完工事项。（i ,j ）tijij工序（工序（i , j）的）的开工事项开工事项工序（工序（i , j）的）的完工事项完工事项只有在只有在 a 工序结束以后工序结束以后,b、c d、e工序才能开始。工序才能开始。a工序是工序是b、c、d、e 等工序的等工序的，而，而b、c、d、e等工序则是工序等工序则是工序a 的的。12467835a6545 c10d20e40f18g30h15k25l350 bn 网络图是网络图是有

8、向图有向图，按照工艺流程的顺序，规定，按照工艺流程的顺序，规定工序从左向右排列工序从左向右排列n 网络图中的网络图中的各个结点都有一个时间（各个结点都有一个时间（某一个或若干个工序开始或结束的时间），某一个或若干个工序开始或结束的时间），一般一般按各个结点的时间顺序编号按各个结点的时间顺序编号。n 为了便于修改编号及调整计划为了便于修改编号及调整计划,可以在编号过程中留出一些编号可以在编号过程中留出一些编号。n 始点编号可以从始点编号可以从1开始，也可以从开始，也可以从0开始。开始。直接直接连结两个事项的箭杆只能有一根。连结两个事项的箭杆只能有一根。123abc1243abc错误错误正确正确在

9、网络图中，除始点和终点外，其它各个结点的前后在网络图中，除始点和终点外，其它各个结点的前后都应有弧相连接，即都应有弧相连接，即图中不能有缺口，使网络图从始点经任何路线都可到达终点图中不能有缺口，使网络图从始点经任何路线都可到达终点。否则，将使某些工序失去与其紧后（或紧前）工序应有的联系否则，将使某些工序失去与其紧后（或紧前）工序应有的联系。不可能有循环现象。不可能有循环现象。否则，将使组成回路的工序永远不能结束，工程永远不能完工。否则，将使组成回路的工序永远不能结束，工程永远不能完工。1234abcd错误错误1243abc 错误错误有有2个始点，个始点，3个终点，显然是错误的个终点，显然是错误

10、的123465782431320001正确正确工序工序ABCDEFGHI紧前紧前工序工序-ABBC、DC、DE、FG工序工序时间时间466759748A,4B,6C,6D,7E,5G,7F,9H,4I,8工序工序紧前工序紧前工序a-b-c-da,bea,cfa,b,c123abc4def56工序工序工序代号工序代号所需时间所需时间紧后工序紧后工序产品设计与工艺设计产品设计与工艺设计a60b,c,d,e外购配套件外购配套件b45l下料、锻件下料、锻件c10f工装制造工装制造1d20g,h木模、铸件木模、铸件e40h机械加工机械加工1f18l工装制造工装制造2g30k机械加工机械加工2h15l机械

11、加工机械加工3k25l装配调试装配调试l35-17654328a设计设计 60D工造工造1 20G工造工造2 30K加工加工3 25E木模、铸件木模、铸件 40H加工加工2 15L装试装试 35B外购配套件外购配套件 45C下料下料 10F加工加工1 60在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条通路称为路线。终点的一条通路称为路线。12467835a6545c10d20e40f18g30h15k25l350b路线路线 路路 线线 的的 组组 成成 各工序所需的时间之和各工序所需的时间之和(天天) 1 60+4

12、5+35=140 2 60+10+18+35=123 3 60+20+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 12467835a6545c10d20e40f18g30h15k25l350b路线路线 路路 线线 的的 组组 成成 各工序所需的时间之和各工序所需的时间之和(天天) 1 60+45+35=140 2 60+10+18+35=123 3 60+20+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 12467835a6545c10d20e40f18g30h15k25l350b路线路

13、线 路路 线线 的的 组组 成成 各工序所需的时间之和各工序所需的时间之和(天天) 1 60+45+35=140 2 60+10+18+35=123 3 60+20+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 12467835a6545c10d20e40f18g30h15k25l350b路线路线 路路 线线 的的 组组 成成 各工序所需的时间之和各工序所需的时间之和(天天) 1 60+45+35=140 2 60+10+18+35=123 3 60+20+30+25+35=170 4 60+20+15+35=130 5 60+40+15+3

14、5=150 12467835a6545c10d20e40f18g30h15k25l350b路线路线 路路 线线 的的 组组 成成 各工序所需的时间之和各工序所需的时间之和(天天) 1 60+45+35=140 2 60+10+18+35=123 3 60+20+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 ：在各条路线上，完成各个工序的时间之和是不完全相等的。其中，完成：在各条路线上，完成各个工序的时间之和是不完全相等的。其中，完成各个工序需要时间最长的路线称为关键路线，或称为主要矛盾线。各个工序需要时间最长的路线称为关键路线，或称为主要矛盾

15、线。12467835a6545c10d20e40f18g30h15k25l350b路线路线 路路 线线 的的 组组 成成 各工序所需的时间之和各工序所需的时间之和(天天) 1 60+45+35=140 2 60+10+18+35=123 3 60+20+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。而缩短非关键如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。而缩短非关键路线上的各个工序所需要的时间，却不能使工程的完工时间提前。即使在一定范路线上的各个工序所需要的时间，却不能使

16、工程的完工时间提前。即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工时间。编制网络计划的基本思想就是在一个庞大的网络图中找出关键路线。对各时间。编制网络计划的基本思想就是在一个庞大的网络图中找出关键路线。对各关键工序，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。关键工序，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人力、物力等资

17、源，用在关键工序上，以达到缩短工程工期，合理利用资源等目的。力、物力等资源，用在关键工序上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各关键工序加以有效控制和调度。在执行计划过程中，可以明确工作重点，对各关键工序加以有效控制和调度。关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路线有可能变为非关键路线。而非关键路线也有可能变为关键路线。线有可能变为非关键路线。而非关键路线也有可能变为关键路线。36例：某例：某项目活动清单如下，试绘制网络图，找出关键线路，并计算其工期。

18、项目活动清单如下，试绘制网络图，找出关键线路，并计算其工期。25364106131515max6+3,15192626191515max15+4,15+3min19-3,151360min15-3,13-700661313151515151919262637例：某例：某工程作业清单如下，试绘制网络图，找出其关键线路，并计算工期。工程作业清单如下，试绘制网络图，找出其关键线路，并计算工期。例例1 为筹建某餐馆，需制定计划。将工程分为为筹建某餐馆，需制定计划。将工程分为14道工序，各工序道工序，各工序需时及先后关系如下表。试求该工程完工期需时及先后关系如下表。试求该工程完工期T及关键路径。及关键路

19、径。工序工序内容内容紧前工序紧前工序所需天数所需天数A购买炉灶及材料购买炉灶及材料10B购买室内设备购买室内设备3C招集工人招集工人1D选择开业地点选择开业地点2E申请许可得到执照申请许可得到执照D7F修理门窗、粉刷墙壁修理门窗、粉刷墙壁E3G砌炉灶、水池砌炉灶、水池A、F5H接通上下水道接通上下水道G4I安装室内设备安装室内设备B、H4J做好室内装饰做好室内装饰B、H3K购进米面及副食品购进米面及副食品I、J6L张贴开业广告张贴开业广告G3M人员训练人员训练C、I4N开业前操作试验开业前操作试验K、L7工序工序ABCDEFGHIJKLMN紧前紧前工序工序_DEAFGBHBHIJGCIKL所需

20、所需天数天数1031273544363471CBAD2E3F4G5H6IJ7I8KL9IM10N11网络计划图的时间参数计算网络图中工作的时间参数。它们是： 工作持续时间(D)； 工作最早开始时间（ES）； 工作最早完成时间（EF）； 工作最迟开始时间（LS）； 工作最迟完成时间（LF）； 工作总时差（TF）； 工作自由时差（FF）。 工作持续时间(D)作业时间Ti-j 单时估计法（定额法）v 每项工作只估计或规定一个确定的持续时间值的方法。一般具有每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工工作的工作量，劳动定额资料以及投入

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

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

23、据。可以认为：工作过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续现正常的情况。按平均意义可用以下公式计算工作持续时间值：时间值： 226;64abbmaD方差 工作最早开始时间ES和工作最早完成时间EF工作的最早开始时间ES是紧前工序最早结束时间。ES=TE（i） EF=ES+tij 工作最迟开始时间LS与工作最迟完成时间LF 工作的最迟完成时间LF是工作在不影响工期下最迟结束时间。LF=TL（j） LS=LF-TL(j) 最后一项工作的最迟完成时间

24、LF等于其最早完成时间EF工序(i, j)的时间参数xy事件最早可能发生时间Tei事件最迟必须发生时间Tl网络时间的图示法网络时间的图示法1. 节点时间（事件时间）事件最早可能发生时间TE：顺向求和取大事件最迟必须发生时间TL：反向求差取小TE（j）=Max(TE(i)+tij)TL（i）ji箭尾事项箭头事项A（D）tijabcdMax(+)Min(-)TE（1）=0TL（i）=Min(TL(j)-tij)TL（n）=TE(n)TE(i)ijESLSEFLF开始完成可能必须最早最迟ad-tija+tijdji箭尾事项箭头事项A（D）tijabcd2.工序时间工序A3.工作时差：指工作有机动时间

25、。 工作总时差TF（i-j） 在不影响工期的前提下，工作所具有的机动时间ji箭尾事项箭头事项A（D）tijabcdijdta总时差ad-tija+tijd工序A总时差为零的工序即关键工序LS-ES=LF-EFji箭尾事项箭头事项A（D）tijabcd（2）工作自由时差FF（i-j）在不影响其紧后工作最早开始的前提下，工序最早可能完工时间所具有机动时间atcFFijij)(自由时差ad-tija+tijd工序Aji箭尾事项箭头事项A（D）tijabcd（3）工作安全时差SF（i-j）在不影响其紧后工作的最迟开始的前提下，工作所具有机动时间btdij自由时差ad-tija+tijd工序A（2）求完

26、工期（用标号法）1）标出各事项的最早开始时间 ， -给始点 标 ； -给任意点 标 ,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以 为箭尾的各箭之 “箭头

27、 -箭长tij”niLiiT3）关键路径：由R(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)反向求差取其小工工序序箭尾节点箭尾节点i所需天数所需天数箭头节点箭头节点jESEFLSLF总时总时差差d-t-a单时单时差差c-t-a自由时差自由时差d-t-babcdA00101212010212222B0032121031921191818C001

28、2534013334332433D002220202000E227992929000F9931212912912000G12125171712171217000H17174212117211721000I21214252521252125000J21213252521242225111K25256313125312531000L17173313117202831111111M25344383825293438990N31317383831383138000ESLSEFLF1791181062345A(10)B(3)C(1)D(2)E(7)F(3)G(5)H(4)I(4)J(3)L(3)K(6)

29、M(4)N(7)341330003425383822991212313117172121252525253829342538383131ESLSEFLF完工期T=38（天）；关键路：D-E-F-G-H-I-K-N。由本例可见：关键工序 头尾皆有 = ，但反之未必。 关键工序时间之和=工期T。 2534253425252525课堂习题 求下面网络计划图中的关键路径和完工期。 要求使用标号法，给出节点的TE和TL，工序的ES、EF、LS、LF以及总时差TF和自由时差FF125436789A(3)B(4)C(5)D(6)F(2)H(3)E(1)G(4)I(5)小结 虚工序的网络时间也应计算，以判断其

30、是否为关键工序。（虚工作为无机动时间的关键工作；否则该虚工作即为有机动时间的非关键工作。） 关键工序有2条：ADEGI和ADFHI 完工期TE为19天。3300001100125436789B(4)C(5)D(6)F(2)H(3)E(1)G(4)I(5)0 03 39 99 910 1011 1110 1014 1419 1900000000000011A(3)iTE TLTFFF二、工序时间不确定的工程计划网络问题 （计划评审技术PERT）的区别仅在于：与CPM1.。，服从于近似认为但由中心极限定理，可也是随机的。期是随机变量，从而完工工序时间)( 2的三时估计法：确定平均工序时间，最可能时间为，最悲观时间为设工序最乐观时间为226 ,64 的方差为则工期方差期望工期=关键工序的平均工序时间之和；=关键工序时间方差之和。天内完工的概率求工程在222 (,),()() ()()1( )()2EkEEkkEkEzxTN TTTTTP TTPTTTTP ZzP Zzedx 由标准正态分布数值表可查得：例2 某工程可分为11项工作，有关资料如下表：工作紧前工作工序时间ambABCDEFGHIJK-ABBCCG、HD、EF、