计划评审方法和关键路线法课件课件

1、运筹学OPERATIONS RESEARCH2022/7/261第七章 计划评审技术和关键路线法（Program Evaluation and Review Technique，Critical Path Method ） 1 PERT 网络图 3关键路线和网络计划的优化 4完成作业的期望时间和 在规定时间内实现事件的概率 2 PERT 网络图的计算2022/7/262甘特图（横道图）20世纪初，H.L.甘特创造了“甘特法”，将各项工作任务按其起迄时刻用一条粗线表示在有时间坐标的图表上。横道图能清楚地表明各项任务的进度安排，对提高管理水平作用明显。2022/7/2631234目标实际进度报告日

2、期月份设计封面印刷校样打印长条校样制图设计版式活动编辑加工 图书出版甘特图资料来源：斯蒂芬P罗宾斯管理学，中国人民大学出版社1997年出版2022/7/264关于工厂建设甘特图 时间一月二月三月四月五月六月设计选址建设设备安装调试开工活动报告日期以纵轴展示计划项目，横轴展示时间刻度。计划进度实际进度2022/7/2652022/7/2662022/7/2672022/7/2682022/7/269甘特图（横道图）横道图法的缺点：不能显示各工作之间的内在联系和逻辑关系；不能清晰地显示影响整个工程的关键因素。2022/7/2610123456 总之，利用网络计划技术法编制计划，可以有效的利用人财物

3、，用最少的劳动消耗，达到预定的目标。 利用网络理论制定计划，并对计划进行评价、审定的一种计划编制方法。回家蒸饭烧水择菜洗、切菜炒菜吃饭本章又叫网络计划技术：又称统筹法2022/7/2611王先生每天早晨必须在7点45分离家上班，上班前的活动如下：起床后立即打开煤气烧水（水烧开需10分钟），然后马上穿衣服，5分钟即完，接着就去取牛奶（来回共需5分钟）。取回牛奶后立即开始煮牛奶（10分钟即开），同时完成洗漱（5分钟即毕），最后是喝完牛奶（需5分钟）出门去上班。如果王先生家只有一个灶头（热源），他必须在什么时候起床？2022/7/2612123564穿烧取煮喝洗55101055关键线路1-2-3-5

4、-6或1-3-5-6;时间25分2022/7/2613 本章是综合运用计划评审技术和关键路线法的一种比较先进的计划管理方法。二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。 关键路线法（CRM）：是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。研究费用与工期的相互关系。 1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系，通过网络分析研究工程费用与工期的相互关系，并找出在编制计划时及计划执行过程中的关键路线。这种方法称为关键路线法（Critical

5、Path Method）简称CPM。2022/7/2614 计划评审技术（PERT）：是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。 1958年，美国海军武器部，在制定研制“北极星”导弹计划时，同样地应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法（Program Evaluation and Review Technique）简称为PERT。能直观清晰的反映计划各部门或各项工作之间的相互联系和制约；反映某一部门或某项工作在全局中的地位和影响，便于发现薄弱环节以采取措施。 鉴于这两种方法的差别，所以，CPM主要应用于以往在 类似工程中已

6、取得一定经验的承包工程；PERT更多地应用 于研究与开发项目。2022/7/2615 在这两种方法得到应用推广之后，又陆续出现了类似的最低成本估算计划法、产品分析控制法、人员分配法、物资分配和多种项目计划制定法等等。虽然方法很多，各自側重的目标有所不同。但它们都应用的是CPM和PERT的基本原理和基本方法。 国内外应用网络计划的实践表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如新产品研制开发、大型工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排，合理组织报表、文件流程等方面。 二十世纪六十年代我国开始应用CP

7、M与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术或网络方法，又按照网络计划的主要特点统筹安排，把这些方法称为统筹方法，华罗庚先生在这项技术的引进与推广方面作出了很大努力。 2022/7/2616 统筹方法的基本原理2通过对网络图时间参数的计算，找出关键工作、关键线路；3利用优化原理，改善网络计划的初始方案，以选择最优方案；4在网络计划的执行过程中进行有效的控制和监督，保证合理地利用资源，力求以最少的消耗获取最佳的经济效益和社会效益.1利用网络图的形式表达一项工程中各项工作的先后顺序及逻辑关系；2022/7/26177.1 PERT 网络图一、基本概念1、作业（或叫工序、活动）：

8、任何消耗时间或资源的行动。它是指为了完成工程项目,在工艺技术和组织管理上相对独立的工作或活动。一项工程由若干个作业组成，作业可以划分得较粗或较细。作业用箭线“”表示。权表示为完成某个工序所需要的时间或资源等数据，通常标注在箭线下面或其它合适的位置上。与某道工序前面直接相连的工序称为紧前工序；其后直接相连的后继工序为紧后工序。2145361h4h5h2h3h3h2h2022/7/26182、事件（也称事项，结点）：（1）它是一个或若干个工序的开始或结束的标志，是相邻工序在时间上的分界点。 （2）事件用圆圈和里面的数字表示，数字表示结点的编号，如，等。箭尾结点表示工序的开始，箭头结点表示工序的完成

9、。（3）事件本身不消耗时间或资源，或相对于作业，消耗量可忽略不计。 （4）作业的起点事件、终点事件：（i,j )；最初事件、最终事件（唯一）2145361h4h5h2h3h3h2h2022/7/2619125 作业a： （1，2） 事项：1，2 一般如果起点事件为i，终点事件为j，将该作业记为（i,j）。ija2022/7/26203、路线：PERT 网络图中由最初事件到最终事件的各项作 业连贯组成的一条路。 路的长度：完成该路上各项作业持续时间的长度和。 关键路线：由最初事件到最终事件的各项作业累计时间最 长的路。它决定网络图上所有作业需要的最短时间。路线1，2，5，6 8小时路线1，3，5

10、，6 11小时 关键路线路线1，4，5，6 7小时2145361h4h5h2h3h3h2h2022/7/26214.网络图：由工序、事项及时间参数所构成的有向图即为网络图。比较上一章的网络图。 2022/7/2622二、建立 PERT 网络图的准则和注意事项为正确反映工程中各个工序的相互关系,在绘制网络图时，应遵循以下准则：1、作业（i,j)用唯一箭线表示，起点事件（箭尾事件）编号 小于终点事件（箭头事件）的编号。2、两个事件之间只能用一条箭线，表示一项作业，具有相同开始和结束的不同作业，需引进虚事件和虚作业。213122022/7/2623如图1的画法是错误的，图2的画法是正确的。 1231

11、342abcabc图1图2即一个工序用确定的两个相关事项表示，某两个相邻结点只能是一个工序的相关事项。在计算机上计算各个结点和各个工序的时间参数时，相关事项的两个结点只能表示一道工序，否则将造成逻辑上的混乱。2022/7/26243、各项作业间的几种关系及图上表示方法（1）作业 a 结束后可以开始 b, c ；（2）作业 c 在 a,b 结束后才可以开始；（3）作业 a,b 结束后可以开始 c,d ；（4）作业 c 在 a 结束后即可以开始， d 在 a,b 结束后才 可以开始。2143abc2143abc52143abcd(1) (2) (3) 52143abcd6(4) 虚箭线表示虚活动，

12、不消耗资源，不占用时间2022/7/2625 (5) a完成后进行b，c完成后进行e; a,c完成后进行dadcbe2022/7/2626 (6) a,b 均完成后进行c ；b,d 均完成后进行e132564acbde2022/7/26274、虚工序。为了用来表达相邻工序之间的衔接关系，而实际上并不存在而虚设的工序。虚工序不需要人力、物力等资源和时间。只表示某工序必须在另外一个工序结束后才能开始。用虚箭线表示，表示工时为0。2022/7/26285、任何PERT网络图有唯一的最初事件和唯一的最终事件 在网络图中，为表示工程的开始和结束，只能有一个最初事件（始点）和一个最终事件（终点）。也就是除

13、始点和终点外，其它各个结点的前后都应有弧相连接，即图中不能有缺口，使网络图从始点经任何路线都可到达终点。否则，将使某些工序失去与其紧后（或紧前）工序应有的联系。 当工程开始时有几个工序平行作业，或在几个工序结束后完工，用一个始点、一个终点表示。若这些工序不能用一个始点或一个终点表示时，可用虚工序把它们与始点或终点连起来。52143abcd52143abcd62022/7/26291243578692022/7/26301243578691243578692022/7/26316、网络图中不能有回路。 在本章讨论的网络图中不能有回路，即不可能有循环现象。否则，将使组成回路的工序永远不能结束，工程

14、永远不能完工。在如下网络图中出现的情况，显然是错误的。1234abcd2022/7/26327、方向的规定。PERT 网络图的布局一般是从左到右，从上到下，尽量避免箭线交叉。因此，事件编号应从始结点开始，从左向右，从上到下排列；箭头标号大于箭尾标号，直到终结点。1243abdecf1324cfabde2022/7/26338、网络图的步局。在网络图中，尽可能将关键路线布置在中心位置，并尽量将联系紧密的工作布置在相近的位置。为使网络图清楚和便于在图上填写有关的时间数据与其它数据，弧线尽量用斜线或水平线或具有一段水平线的折线。2022/7/2634三、PERT 网络图的合并与简化若干局部网络图合并

15、成一个大的全局网络图合并后的网络图需简化 2022/7/2635四、PERT 网络图改错例1：12543A E B C D F 2022/7/263612653A E B C F 4D 12543A E B C D F 2022/7/263712873A E B C G 5D 4F 6例2：2022/7/263812873A E B C G 5D 4F 612654A E B C G D 3F 2022/7/263913764A E B C G D 5F 2例3：2022/7/264013764A E B C G D 5F 21254A E B C G D 3F 2022/7/26411245

16、A E B C G D 3F 例4：2022/7/26421245A E B C G D 3F 1253A E B C G D 4F 2022/7/2643五、绘制 PERT 网络图绘制网络图的学习方法： 亲自画几个，从易到难，画几个之后，就会知道其中的规律。2022/7/2644例1：工序ABCDEFGHI紧前工序-ABBC、DC、DE、FG 2022/7/2645A BCDEGFHI工序ABCDEFGHI紧前工序-ABBC、DC、DE、FG2022/7/2646工序ABCDEFG紧前工序-ACBCDEF例2 工序明细表如下图：2022/7/2647工序ABCDEFG紧前工序-ACBCDEF

17、142AB3567CDEFG28312443例2 工序明细表如下图：2022/7/2648工序ABCDEFGH紧前工序A,BA,BBCCD,E,F例3：某工程的工序一览表如下，试绘制网络图。2022/7/2649工序ABCDEFGH紧前工序A,BA,BBCCD,E,F例3：某工程的工序一览表如下，试绘制网络图。132456A2BCDEFGH2022/7/2650工序ABCDEFGH紧前工序-A BCDDDE、F、G例4：某工程的工序一览表如下，试绘制网络图。2022/7/2651工序ABCDEFGH紧前工序-A BCDDDE、F、G234598671ABCDGFEH2022/7/2652工序a

18、 bcdef紧前工序-a-a、ccb、d、e例5：2022/7/2653工序a bcdef紧前工序-a-a、ccb、d、e123456acbdef2022/7/2654工序a bcdef紧前工序-abacabc例6：2022/7/2655工序紧前工序a-b-c-da,bea,cfa,b,c123abc4def562022/7/2656例7：某工程的工序一览表如下，试绘制网络图。工序a bcdef紧后工序bcdeff-2022/7/2657例7：某工程的工序一览表如下，试绘制网络图。工序a bcdef紧后工序bcdeff-234561abcdfe2022/7/2658例8：某工程的工序一览表如下

19、，试绘制网络图。工序紧后工序ac,dbc,d,ecfdgegf-2022/7/2659工序紧后工序ac,dbc,d,ecfdgegf-132456abcefdg例8：某工程的工序一览表如下，试绘制网络图。2022/7/2660例9：某工程的工序一览表如下，试绘制网络图。工序紧后工序ad,ebd,e,fcgdheifigjh-i-j-2022/7/2661工序紧后工序ad,ebd,e,fcgdheifigjh-i-j-25671bge34acf8hijd例9：某工程的工序一览表如下，试绘制网络图。2022/7/2662例10：某工程的工序一览表如下，试绘制网络图。工序紧后工序a ebf,g,ic

20、hdieifjg-hji-j-2022/7/2663工序紧后工序a ebf,g,ichdieifjg-hji-j-2571bge34ac8ij3dfh例10：某工程的工序一览表如下，试绘制网络图。2022/7/26643E12467835A2B8C4D1J5F3H7G2I60091011作业ABCDEFGHIJ紧前作业/ABBACEFDFGHI作业时间2341832765例112022/7/2665例：某项工程由11项作业组成，其计划完成时间及作业间相 互关系如表。绘制箭线式网络图计算各项时间作业计划完成时间/天紧前作业作业计划完成时间/天紧前作业A5-G21B，EB10-H35B，EC11-

21、I25B，ED4BJ15F，G， IE4AK20F，GF15C，D7.2 PERT 网络图的计算2022/7/2666F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20 虚箭线表示虚活动，不消耗资源，不占用时间。2022/7/26671、作业的最早开始时间TES (i，j) 任何一个工序都必须在其紧前工序结束后才能开始。作业的最早开始时间是它的各项紧前作业最早结束时间中最大的一个值，用TES (i，j)表示。可以假定最初事件在时刻零实现。作业的最早结束时间TEF(i，j)是它的做早开始时间加上该作业的计划作业时间的值。 注意：计算的顺序先从结点1

22、开始的作业开始，以结点1开始的作业算完后，再算结点2开始的作业，依次类推。一、网络时间的计算2022/7/2668计算各项时间: 最早开始和最早结束时间 假设最初事件在零时刻实现A(1,2)，B(1,3)，C(1,4)的最早开始时间：A(1,2)，B(1,3)，C(1,4)的最早结束时间：E(2,5)的最早开始和最早结束时间：2022/7/2669D(3,4)和虚作业（3，5）的最早开始和最早结束时间：F(4,6)的最早开始和最早结束时间：2022/7/2670G(5,6)、I(5,7)和H(5,8)的最早开始和最早结束时间：2022/7/2671完成所有作业的最短周期：J(7,8)的最早开始

23、和最早结束时间：工序(6，7)、(6，8)的最早开始和最早结束时间：2022/7/26722、作业最迟结束时间 TLF (i，j)。在不影响工程最早结束时间的条件下, 工序最迟必须结束时间，简称为工序最迟结束时间, 是它的各项紧后作业最迟开始时间中最小的一个。 可以假定全部作业在什么时间内结束。作业最迟开始时间TLS (i，j)。在不影响工程最早结束时间的条件下，工序最迟必须开始的时间。它等于作业的最迟结束时间减去该作业时间。注意：计算的顺序先从结点8结束的作业开始，以结点7结束的作业算完后，再算结点6结束的作业，依次类推。2022/7/2673最迟结束和最迟开始时间假设所有作业在51天内完成

24、H(5,8),J(7,8),K(6,8)的最迟开始时间：H(5,8),J(7,8),K(6,8)的最迟结束时间：2022/7/2674I(5,7)及虚作业（6，7）的最迟结束、最迟开始时间：G(5,6)和F(4,6)的最迟结束、最迟开始时间：2022/7/2675E(2，5)和虚(3，5)的最迟结束,最迟开始时间：2022/7/2676D(3，4) 和 C(1，4)的最迟结束,最迟开始时间：A(1，2)的最迟结束,最迟开始时间：B(1，3)的最迟结束,最迟开始时间：2022/7/2677最初事件1的最迟开始时间：2022/7/2678R(i，j) = TLF (i，j) TES (i，j) T

25、 (i，j)作业的总时差R(i,j)：网络上多于一项作业共同拥有的机动时间。也是网络上可以利用的时差总数，或工作的机动时间、富裕时间。在不影响工程最早结束时间的条件下，工序最早开始(或结束)时间可以推迟的时间(即工序的完工期可以推迟的时间)即： 3、时差的计算工序总时差越大,表明该工序在整个网络中的机动时间越大，可以在一定范围内将该工序的人力、物力资源利用到关键工序上去，以达到缩短工程结束时间的目的。总时差为零的作业是关键作业，没有任何机动时间。2022/7/2679式中，TES (j，k)为工序 ij 的紧后工序的最早开始时间。自由时差F(i,j) ：不影响作业的各项紧后作业最早开工时 间条

26、件下，该作业可以推迟开工时间的最大限度。自由时差0的工序，尤其是自由时差较大的作业，可以适当的分流人、财、物给关键作业，可以缩短工期。2022/7/2680工序 a工序a 的紧后工序b工序a 的自由时差工序a 的总时差 TES TLS TEF TLF TES TLS TEF TLF （参考内容）工序总时差、自由时差及其紧后工序的最早开始时间、最迟开始时间的关系如下图所示。 2022/7/2681二、各时间参数的图上计算法标出四个数：a、TES (i，j) 写在方框内，标在箭尾处，从左向右标，标的顺序同计算顺序；tES (i，j)=maxtES (h,i)+ thib、TLF (i，j)写在三角

27、形内，标在箭头处，从右向左标，标的顺序同计算顺序；tLF (i，j)=mintLF (j,k) - tjkc、T( i ，j)标在作业上面； d、R(i，j)标在作业下面。总时差为零的工序，开始和结束的时间没有一点机动的余地。由这些工序所组成的路线就是网络中的关键路线。这些工序就是关键工序；特点：方便、简便、直观，但工作数目多，图形复杂时候，容易遗漏和出错，这时可以采用表格法。2022/7/2682F15C1112367845E4B10D4J，15H，35G，21I25K20 000510101410101031313551515136363131101016161061A5051022016

28、5012022/7/2683作业（i,j) t(i,j) tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)F(i,j)12345678A (1,2)5051610B (1,3)1001001000C (1,4)1101151653E (2,5)45961011D (3,4)41014121620虚 (3,5)01010101000F (4,6)151429163122G (5,6)211031103100I (5,7)251035113610H (5,8)351045165166虚 (6,7)03131363654K (6,8)203151315100J (7,8)

29、153550365111三、各时间参数的表格计算法 2022/7/2684例：计算时间参数1234562a 43b 30c 67d 52e 80f 1004646166666工序t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)r(i,j)关键工序a4b3c6d5e8f10000466436914166661616162301186230720010720cf2022/7/26857.3 关键路线及网络计划的优化 绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用

30、和降低费用等目标，即进行网络优化，确定最优的计划方案。2022/7/2686关键路线：由最初事件到最终事件的各项作业累计 时间最长的路。F，15C，11A，512367845E，4B，10D，4J，15H，35G，21I，25K，20 关键路线上各作业的总时差均为0。2022/7/2687关键路线的意义：1、关键路线的持续时间决定了完成全盘计划所必需的最 少时间；2、关键路线上的各项作业对计划进度起决定作用，必须 投入充分的人、财、物保证各作业按时完工。若想提 前完工，必须缩短关键路线上的有关工序的时间。3、次关键路线可能成为关键路线，也要注意。例：要求上例中的工程在49天内完成，可缩短有关工

31、时的作 业时间，产生的额外费用如表所示，应如何安排，可使 得额增加的费用最小？2022/7/2688作业（i,j) 计划完成时间最短完成时间缩短1天增加的费用B (1,3)108700C (1,4)118400E (2,5)43450G (5,6)2116600H (5,8)3530500I (5,7)2522300J (7,8)1512400K (6,8)20165001、要缩短工期，应缩短关键路线上的 B, G, K 作业时间2、额外费用要最小，先考虑 K 3、缩短1天即会产生新的关键路线，故先缩短1天2022/7/2689F，15C，11A，512367845E，4B，10D，4J，15

32、H，35G，21I，25K，19 4、现有两条关键路线，应缩短关键路线上的 B, G, K ，或 B，I，J作业时间5、额外费用要最小，考虑 B6、缩短1天即会产生新的关键路线，故缩短1天。已满足要求2022/7/2690最优方案的选择时间优化：在人力、材料、设备、资金等资源基本有保证的条件下，寻求最短的工程周期。时间与资源的优化：在合理利用资源的条件下，寻求最短的工程周期。时间与成本的优化对于工期紧迫的工程，则在保证工期最短的情况下，寻求成本较低的方案。对于一般工程，则在成本最低的情况下，寻求合理的工程周期。目的是要找出总成本变动中的成本最低点。网 络 优 化:绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的计划方案。2022/7/2691网络计划