运筹学计划评审方法和关键路线法专家讲座

运筹学基础及应用(OperationsResearch)主讲：杨启明运筹学计划评审方法和关键路线法专家讲座第1页PERT网络图1PERT网络图计算2关键路线和网络计划优化3第7章计划评审方法和关键路线法完成作业期望时间和在要求时间内实现事件概率4运筹学计划评审方法和关键路线法专家讲座第2页目标要求：掌握PERT(ProgramEvaluationandReviewTechnique)网络图建立、计算与优化本章重点：PERT网络图计算与优化本章难点：关键路线(CriticalPathMethod)确定，PERT途中各种相关参数计算运筹学计划评审方法和关键路线法专家讲座第3页最初是作为大规模开发研究项目标计划和管理方法而被开发出来。现已用于全世界军用、民用等各方面项目中。1965年，著名数学家华罗庚教授首先在我国推广和应用了这种计划管理方法。网络计划介绍概念：以网络图为基础一个有逻辑和数学依据计划模型。优点：能够直观地反应工作之间相互关系，使一个计划组成一个系统整体，从而为实现计划定量分析奠定基础。运筹学计划评审方法和关键路线法专家讲座第4页也称为横道图，是描述进度计划最惯用工具，最早于1917年由HenryL.Ganntt提出。甘特图（GanttChart）12345678机房装修房间布置网络布线硬件安装软件调试天关键活动非关键活动运筹学计划评审方法和关键路线法专家讲座第5页6

网络计划是用网络分析方法编制计划。为了编制网络计划，首先需绘制网络图。网络图是由结点(点)、箭线及权所组成有向图，即有向赋权图。（区分于上一章网络图）

7.1PERT网络图123油漆地板摆放家俱51结点：事件序号结点：事件序号权：工作时间运筹学计划评审方法和关键路线法专家讲座第6页7123油漆地板摆放家俱51作业或活动描述工期预计事件序号事件序号图解一、几个基本概念1.作业：指任何消耗时间或资源行动。2.事件：标志作业开始或结束紧前工序紧后工序运筹学计划评审方法和关键路线法专家讲座第7页82、事件（也称事项，结点）（1）它是一个或若干个工序开始或结束，是相邻工序在时间上分界点。（2）事件用圆圈和里面数字表示，数字表示结点编号，如①，②，…等。箭尾结点表示工序开始，箭头结点表示工序完成。（3）结点(事项)本身既不消耗人力、物力，也不占用时间。运筹学计划评审方法和关键路线法专家讲座第8页93.路线：起点事件（图最初事件）与终点事件（最终事件）之间由各项作业连贯组成一条路。关键路线：各弧权重总和最大路线，或称主要矛盾路线，它决定网络图上全部作业需要最短时间。4.网络图：由工序、事项及时间参数所组成有向图即为网络图。运筹学计划评审方法和关键路线法专家讲座第9页123456782433121二、网络图绘制标准与注意事项1.方向要求网络图是有向图，按照工艺流程次序，要求工序从左向右，从上到下排列。运筹学计划评审方法和关键路线法专家讲座第10页2.两事件间只能画一条箭线，表示一项作业不正确画法对含有相同开始和结束事件两项以上作业，要引进虚事件和虚作业。1231342abcabc虚工序正确画法运筹学计划评审方法和关键路线法专家讲座第11页12虚工序。

为了用来表示相邻工序之间衔接关系，而实际上并不存在而虚设工序。虚工序不需要人力、物力等资源和时间。只表示某工序必须在另外一个工序结束后才能开始。用虚箭线┄→表示，表示工时为0。ijk750a3b运筹学计划评审方法和关键路线法专家讲座第12页3.不允许回路123不正确画法运筹学计划评审方法和关键路线法专家讲座第13页3.网络图中基本逻辑关系表示方法①A完工后进行B，B完工后进行CABC②A完工后进行B和CBC1234A③工序A与B完工后进行Cabc1234④工序a与b完工后进行c与dab12345cd运筹学计划评审方法和关键路线法专家讲座第14页⑤工序a完工后进行c，a、b完工后进行dab123cd456运筹学计划评审方法和关键路线法专家讲座第15页例1、a,b,c,d,c在a,b完工后开始，d在b完工后开始。cabdabcd运筹学计划评审方法和关键路线法专家讲座第16页例2已知ABCEADCABDCE运筹学计划评审方法和关键路线法专家讲座第17页18练习：绘制网络图作业代号紧前作业A无BACBDBEBFC、D、E15234ACEB6DF7运筹学计划评审方法和关键路线法专家讲座第18页19练习：绘制网络图作业代号紧前作业A无BAC无DA、CECFB、D、E13452ACEB6DF运筹学计划评审方法和关键路线法专家讲座第19页例3

某企业研制新产品部分工序与所需时间以及它们之间相互关系都显示在其工序进度表如表所表示，请画出其网络图。工序代号工序内容所需时间（天)紧前工序abcde产品设计与工艺设计外购配套零件外购生产原料自制主件主配可靠性试验601513388-aacb,d１２４５３abcde601383815运筹学计划评审方法和关键路线法专家讲座第20页

例４把例３工序进度表做一些扩充，以下表，请画出其网络图。工序代号所需时间（天）紧前工序工序代号所需时间（天）紧前工序abcd60151338－aacefgh810165b，ｄdde,ｆ,ｇ152643a60b158e1013dc38f扩充工序ｆ添加ｇ、ｈ工序7h5g16网络图中不允许两个点之间多于一条弧，所以增加了一个点和虚工序616g78运筹学计划评审方法和关键路线法专家讲座第21页22绘制网络图学习方法：亲自画几个，从易到难，画几个之后，就会知道其中规律。运筹学计划评审方法和关键路线法专家讲座第22页23练习1：某工程工序一览表以下，试绘制网络图。工序紧前工序a--b--c--da,bea,cfa,b,c123abc4def56运筹学计划评审方法和关键路线法专家讲座第23页24工序ABCDEFGHI紧前工序----ABBC、DC、DE、FG工序时间466759748

练习2：某工程工序一览表以下，试绘制网络图。A,4B,6C,6D,7E,5G,7F,9H,4I,8运筹学计划评审方法和关键路线法专家讲座第24页257.2PERT网络图计算一、网络计划时间参数最早开始时间ES最早结束时间EF最迟开始时间LS最迟结束时间LF总时差TF自由时差FF运筹学计划评审方法和关键路线法专家讲座第25页261、作业最早开始时间tES(i，j)

任何一个工序都必须在其紧前工序结束后才能开始。紧前工序最早结束时间即为工序最早可能开始时间，简称为工序最早开始时间，用tES(i，j)表示。tES(i，j)=max{tEF(k，i)}

能够假定最初事件在时刻零实现。2、工序最早结束时间tEF(i，j)

是工序最早可能结束时间简称，它等于工序最早开始时间加上该工序作业时间。即

tEF(i，j)=tES(i，j)+t(i，j)

注意：计算次序先从结点1开始作业开始，以结点1开始作业算完后，再算结点2开始作业，依次类推。最早时间

参数计算最早开始时间ES＝MAX{紧前工作EF}最早结束时间EF＝ES＋工作延续时间t运筹学计划评审方法和关键路线法专家讲座第26页最早时间

参数计算最早开始时间ES＝MAX{紧前工作EF}最早结束时间EF＝ES＋工作延续时间t12345798610111213A3B10C20D5E2F10G12H2I65J5K7L8M1003313133333383840384838503840481135060113120120128128138运筹学计划评审方法和关键路线法专家讲座第27页283、作业最迟结束时间tLF(i，j)。在不影响工程最早结束时间条件下，工序最迟必须结束时间，简称为工序最迟结束时间,是它各项紧后作业最迟开始时间中最小一个，用TLF(i，j)表示。

tLF(i，j)=min{tLS(j，k)}

能够假定全部作业在什么时间内结束。4、作业最迟开始时间tLS(i，j)。在不影响工程最早结束时间条件下，工序最迟必须开始时间，简称为工序最迟开始时间,用tLS(i，j)表示。它等于工序最迟结束时间减去工序作业时间，即:tLS(i，j)=tLF(i，j)t(i，j)注意：计算次序先从最终一个结点结束作业开始，以终止点结束作业算完后，再算前一个结点结束作业，依次类推。最迟时间参数计算最迟结束时间LF＝MIN{紧后工作LS}最迟开始时间LS＝LF—工作延续时间t运筹学计划评审方法和关键路线法专家讲座第28页最迟时间参数计算最迟结束时间LF＝MIN{紧后工作LS}最迟开始时间LS＝LF—工作延续时间t12345798610111213A3B10C20D5E2F10G12H2I65J5K7L8M10033131333333838403848385038404811350601131201201281281381381281281201201131134811310810810610896483848463833331313330运筹学计划评审方法和关键路线法专家讲座第29页时差(机动时间)计算总时差R(i，j)计算总时差R(i，j)

＝LF—EF或总时差R(i，j)

＝LS—ES自由时差F(i，j)

自由时差F(i，j)

＝min{ES(紧后工作)}—EF

工序总时差越大，表明该工序在整个网络中机动时间越大，能够在一定范围内将该工序人力、物力资源利用到关键工序上去，以到达缩短工程结束时间目标。运筹学计划评审方法和关键路线法专家讲座第30页2023/4/2531工序总时差、自由时差及其紧后工序最早开始时间、最迟开始时间关系如图所表示。

tEStLStEFtLF工序a工序a

紧后工序b工序a自由时差工序a总时差

tEStLStEFtLF运筹学计划评审方法和关键路线法专家讲座第31页327、各时间参数图上计算法。标出四个数：

(1)、tES(i，j)

写在方框内，标在箭尾处，从左向右标，标次序同计算次序；tES(i，j)=max{tES(h,i)+t(h，i)}(2)、

tLF(i，j)写在三角形内，标在箭头处，从右向左标，标次序同计算次序；tLF(i，j)=min{tLF(j,k)–t(j，k)}(3)、

t(i，j)

标在作业上面(4)、R(i，j)标在作业下面特点：方便、简便、直观，但工作数目多，图形复杂时候，轻易遗漏和犯错，这时能够采取表格法。运筹学计划评审方法和关键路线法专家讲座第32页338、各时间参数表格计算法

时间作业tijtEStEFtLStLFRijFij①②③=②+①④⑤=④+①⑥=④-②⑦作业一列：填写工作表上全部作业。从起点事件中编号最小填写起，对起点事件编号相同作业，按终点事件编号由小到大填写。

tES一列：假定起点事件最早开始时间为0。运筹学计划评审方法和关键路线法专家讲座第33页34例5

某项工程由11项作业组成（分别用代号A，B，……，J，K表示），其计划完成时间及作业间相互关系如表7-1所表示，要求编制该项工程网络计划并计算其时间参数。作业计划完成时间/d紧前作业作业计划完成时间/d紧前作业A5—G21B,EB10—H35B,EC11—I25B,ED4BJ15F,G,IE4AK20F,GF15C,D运筹学计划评审方法和关键路线法专家讲座第34页2023/4/2535

依据表中已知条件和数据，绘制网络如图所示。12345678ABCEDGHIJKF5435101141520152125运筹学计划评审方法和关键路线法专家讲座第35页36图上计算时间参数：1）标出各事项最早开始时间，

-给始点标；

-给任意点

标,Ej=Max{以为箭头各箭之“箭尾+箭长tij”}10jEjj2)终点中T即完工期。nT（1）求完工期（用标号法）运筹学计划评审方法和关键路线法专家讲座第36页37图上计算时间参数：12345678ABCEDGHIJKF543510114152015212505101410313551运筹学计划评审方法和关键路线法专家讲座第37页38图上计算时间参数：（2）求关键路（用标号法）2）计算各工序时差R(i,j)=

-tij-。ijji1）标出各事项最晚开始时间，

-给终点标；-给任意点标,Li=Min{以为箭尾各箭之“箭头-箭长tij”}niLiiT3）关键路径：由R(i,j)=0关键工序组成由至路。n1由本例可见：关键工序头尾皆有=，但反之未必。关键工序时间之和=工期T。

运筹学计划评审方法和关键路线法专家讲座第38页39图上计算时间参数：12345678ABCEDGHIJKF54351011415201521250510141031355151363110616010运筹学计划评审方法和关键路线法专家讲座第39页2023/4/2540表格计算时间参数：

时间作业tijtEStEFtLStLFRijFij①②③④⑤⑥⑦A(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)153550365111运筹学计划评审方法和关键路线法专家讲座第40页41

总时差为零工序，开始和结束时间没有一点机动余地。由这些工序所组成路线就是网络中关键路线。这些工序就是关键工序。12345678ABCEDGHIJKF54351011415201521250510141031355151363110616010运筹学计划评审方法和关键路线法专家讲座第41页42

用计算工序总时差方法确定网络中关键工序和关键路线是确定关键路线最惯用方法。

关键路线意义：（1）这条路线连续时间决定完成全盘计划所需最少时间；（2）关键路上各项作业是整个工程控制步骤，是需重点抓和安排人力物力以确保按期完工关键部位。7.3关键路线和网络优化运筹学计划评审方法和关键路线法专家讲座第42页437.3关键路线和网络优化(1)工期优化(2)工期－成本优化(3)资源优化网络优化运筹学计划评审方法和关键路线法专家讲座第43页2023/4/2544

为了缩短整个计划进程，就要设法缩短关键路线连续时间，这就是网络图优化或改进。（1）检验关键路线上各项作业计划时间是否订得恰当，假如订得过长，可适当缩短；（2）将关键路线上作业深入分细，尽可能安排多工位或平行作业；（3）抽调非关键路线上人力、物力支援关键路线上作业；（4）有时也可重新制订工艺流程，改变网络图结构。缩短关键路线连续时间，可经过以下路径实现：运筹学计划评审方法和关键路线法专家讲座第44页45例6

假如上例（例5）所列工程要求在49天完成。为加紧进度，下表列出了可缩短工序全部作业及其相关费用。问怎样安排，使额外增加总费用为最小。作业代号计划完成时间/d最短完成时间/d缩短1d增加费用(1,3)B108700(1,4)C118400(2,5)E43450(5,6)G2116600(5,8)H3530500(5,7)I2522300(7,8)J1512400(6,8)K2016500表7-212345678ABCEDGHIJKF54351011415201521250510141031355151363110616010运筹学计划评审方法和关键路线法专家讲座第45页46解：按下列图所表示步骤进行运筹学计划评审方法和关键路线法专家讲座第46页47①工期尚需缩短：51-49=2天；②作业K最多可缩短：20-16=4天；③非关键路线上总时差最小为：1；Min{2,4,1}=1表7-212345678ABCEDGHIJKF54351011415201521250510141031355151363110616010关键路线上作业有3项：B、G、K，其缩短1天增加费用分别为：700,600,500，作业K缩短1天费用最小；说明工期缩短1天将出现新关键路线，即作业K可缩短1天，即为：20-1=19天，额外增加500元费用。运筹学计划评审方法和关键路线法专家讲座第47页48§3关键路线和网络优化工期缩短1天后PERT图以下：12345678ABCEDGHIJKF54351011415191521250510141031355050353110616010运筹学计划评审方法和关键路线法专家讲座第48页2023/4/2549表格计算时间参数：

时间作业tijtEStEFtLStLFRijFij①②③④⑤⑥⑦A(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)251035103500H(5,8)351045155055虚(6,7)03131353544K(6,8)193150315000J(7,8)153550355000运筹学计划评审方法和关键路线法专家讲座第49页2023/4/255012345678ABCEDGHIJKF5435101141520152125I有两条关键路线，有5中缩短工期方案：缩短作业BI,GI,KJ,GJ,K增加费用（元/d）7009008001000900作业B缩短1天费用最小运筹学计划评审方法和关键路线法专家讲座第50页2023/4/2551§3关键路线和网络优化而作业B最多可压缩：10-8=2天，工期尚需压缩：50-49=1天，非关键路上总时差最小为1，min{2,1,1}=1所以，将作业B缩短1天，增加额外费用700元。12345678ABCEDGHIJKF543591141520152125I比正常施工，额外增加费用：500+700=1200元运筹学计划评审方法和关键路线法专家讲座第51页52运筹学计划评审方法和关键路线法专家讲座第52页当完成工序所需时间不确定情况下怎样求网络时间和关键路线？例某培训中心负责明年春天培训工作，相关培训组织各项活动信息以下表，要求绘制出统筹方法网络图，设法求出网络时间和关键路线，并确定开始这个组织工作时间以确保培训工作准期举行。7.4完成作业期望时间和在要求时间内实现事件概率活动（工序）活动（工序）内容紧前活动（工序）abCdefgHi

制订培训计划选聘培训教师列出一些可供选择培训地点确定培训地点确定培训日程安排落实教学设备，器材，资料发培训通知并确定学员名单订旅馆房间处理最终一些事务-a-c

b,de

b,dgf,g运筹学计划评审方法和关键路线法专家讲座第53页活动（工序）活动（工序）内容紧前活动（工序）abCdefgHi

制订培训计划选聘培训教师列出一些可供选择培训地点确定培训地点确定培训日程安排落实教学设备，器材，资料发培训通知并确定学员名单订旅馆房间处理最终一些事务-a-c

b,de

b,dgf,g12356487abecdfghi解：由下表绘出网络图运筹学计划评审方法和关键路线法专家讲座第54页因为是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种预计：1.乐观时间。指所需最少时间，用a表示。2.最可能时间。指正常时间，用m表示。3.消极时间。指不顺利情况下，最多时间，用b表示。以下表：

活动乐观时间最可能时间消极时间abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.0