运筹学——计划评审方法和关键路线法

1、OR:SM1 网络计划的发展历程网络计划的发展历程 v关键路线法关键路线法(Critical Path Method，CPM )v计划评审技术计划评审技术(Program Evaluation and Review Technique，PERT )v图示评审技术图示评审技术(Graphic Evaluation and Review Technique，GERT )v风险评审技术风险评审技术(Venture Evaluation Review Technique，VERT ) 网络计划技术的特性网络计划技术的特性 网络计划技术只不过是反映和表达项目计划安排的一种方法，网络计划技术只不过是反映和

2、表达项目计划安排的一种方法，是被项目施工技术所决定的，它只能适应项目施工方法的要求。是被项目施工技术所决定的，它只能适应项目施工方法的要求。是把工程进度安排通过网络的形式直观地反映出来。是把工程进度安排通过网络的形式直观地反映出来。 OR:SM21 1 PERT网络图网络图 1-1PERT1-1PERT网络图的一些基本概念网络图的一些基本概念 工序工序(作业作业)：一项需要人财物或时间等资源的相对独立的活动过程一项需要人财物或时间等资源的相对独立的活动过程 在网络图中用箭线在网络图中用箭线“” 表示，表示， 前面直接相连工序称紧前工序，前面直接相连工序称紧前工序， 直接相连的后继工序为紧后工序

3、。直接相连的后继工序为紧后工序。 结点结点(事件事件)：相邻工序的分界点相邻工序的分界点 一般用圆圈来表示，每个结点编上顺序号，一般用圆圈来表示，每个结点编上顺序号， 结点既不消耗人力、物力，也不占用时间。结点既不消耗人力、物力，也不占用时间。 路线：路线：指指PERT网络图中，从最初事件到最终事件的由各项作业连贯组成的网络图中，从最初事件到最终事件的由各项作业连贯组成的一条路一条路。关键路线：关键路线：指从最初事件到最终事件路条可以有不同的路，各项作业累计时指从最初事件到最终事件路条可以有不同的路，各项作业累计时间最长的那条路间最长的那条路。 网络图网络图 由工序、事项及时间参数所构成的有向

4、图即为网络图。由工序、事项及时间参数所构成的有向图即为网络图。 箭线表示工序箭线表示工序,结点为工序间相互关系的网络图，称箭线式网络结点为工序间相互关系的网络图，称箭线式网络 结点表示工序结点表示工序,箭线为工序间相互关系的网络图，称结点式网络箭线为工序间相互关系的网络图，称结点式网络OR:SM3一、网络计划的图示形式一、网络计划的图示形式 1 1、箭线式网络图、箭线式网络图 21A25B343C55D5Et作业时间iN作业名称j2 2、结点式网络图、结点式网络图 t作业时间N作业名称iNti作业序号122543355560OR:SM4二、箭线式网络图的规则二、箭线式网络图的规则 工序表示的规

5、定工序表示的规定 一条箭线和它的相关事项只能代表一道工序，不能代表多道工序，一条箭线和它的相关事项只能代表一道工序，不能代表多道工序， 两个结点之间只能有一条箭线相连两个结点之间只能有一条箭线相连。不允许出现缺口与回路不允许出现缺口与回路 网络图中网络图中只能有一个始点和一个终点只能有一个始点和一个终点，使得自网络图的始点经由任何路径都，使得自网络图的始点经由任何路径都可以到达终点。可以到达终点。 虚工序虚工序 虚工序是为了表达相邻工序之间的逻辑关系而虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序虚设的工序。 不消耗时间、费用和资源，一般用虚箭线表示。不消耗时间、费用和资源，一般用虚箭线表

6、示。方向的规定方向的规定 网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列从左向右排列。编号编号的规定的规定 编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。 编号时编号时不允许箭头编号小于箭尾编号不允许箭头编号小于箭尾编号。 OR:SM5 对承担的工程经过工序分解、工时确定，根据生产工艺、对承担的工程经过工序分解、工时确定，根据生产工艺、生产组织的制约确定出各工序间的逻辑关系后，可以用一张网生产组织的制约确定出各工序间的逻辑关系后，可以用一张网络

7、图把上述各点统一反映出来，借以形象地表达工程计划方案络图把上述各点统一反映出来，借以形象地表达工程计划方案的编制。的编制。绘制网络图：前进法、后退法、任意法。绘制网络图：前进法、后退法、任意法。草图草图逐步调整逐步调整 （尽量消除箭杆的交叉）（尽量消除箭杆的交叉）（正确运用虚工序）（正确运用虚工序）排列整齐、完整准确反映工程计划编制的网络图。排列整齐、完整准确反映工程计划编制的网络图。注意：注意：1. 1. 总开工、总完工事项都是唯一的；总开工、总完工事项都是唯一的；2. 2. 编号：总开工事项编号：总开工事项1 1，各事项编号不重复，任一工序完工事，各事项编号不重复，任一工序完工事项编号大于

8、开工事项编号，总完工事项为项编号大于开工事项编号，总完工事项为n.n.OR:SM6三、箭线式网络图举例三、箭线式网络图举例 某工程的工程一览表某工程的工程一览表 124536badcegf36445810OR:SM72 PERT2 PERT网络图的计算网络图的计算一、结点的时间参数一、结点的时间参数 结点的最早时间结点的最早时间tE(j) tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。等于从始点开始到本结点的最长路线上各道工序时间之和。 从始点事项开始，自左向右，顺着箭线方向逐个计算从始点事项开始，自左向右，顺着箭线方向逐个计算 。),()(max)(0)1(jititjttE

9、iEE 结点的最迟时间结点的最迟时间 tL(j) 指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影响后续工序按时开工，以至推迟整个工程的完工时间。响后续工序按时开工，以至推迟整个工程的完工时间。 从终点开始，从右向左，逆箭线方向逐个计算。从终点开始，从右向左，逆箭线方向逐个计算。),()(min)()()(jitjtitntntLjLELOR:SM8一、结点的时间参数一、结点的时间参数 计算结点时间参数计算结点时间参数124536badcegf548364100366111996611190OR:SM9二、作业的时间参数二、作业的

10、时间参数 最早可能开工时间最早可能开工时间tES(i, j) 一个作业必须在其各紧前作业都完工后才能开工，一个作业必须在其各紧前作业都完工后才能开工， 作业最早可能开工时间等于其箭尾事项的最早时间。作业最早可能开工时间等于其箭尾事项的最早时间。 tES(i, j)= tE(i) 最早可能完工时间最早可能完工时间 tEF(i, j) 从最早可能开工时间开工，完成本作业的时间从最早可能开工时间开工，完成本作业的时间 。 tEF(i, j)= tES(i, j) +t(i, j) 最迟必须开工时间最迟必须开工时间 tLS(i, j) 在不影响工程如期完工的前提下，作业最迟必须开工的时刻。在不影响工程

11、如期完工的前提下，作业最迟必须开工的时刻。 等于它的箭头事项的最迟时间减去本作业的作业时间等于它的箭头事项的最迟时间减去本作业的作业时间 tLS(i, j)= tL( j) - t(i, j) 最迟必须完工时间最迟必须完工时间 tLF(i, j) 在不影响工程如期完工的前提下，作业最迟必须完工的时刻在不影响工程如期完工的前提下，作业最迟必须完工的时刻 。 tLF(i, j)= tLS(i, j) +t(i, j) = tL( j) OR:SM10三、时差与关键路线三、时差与关键路线 时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机时差又称宽裕时间：不影响如期完成任务的条件下，各道工

12、序可以机动使用的一段时间。动使用的一段时间。总时差总时差R(i, j)：不影响其紧后工序：不影响其紧后工序最迟必须开工最迟必须开工的前提下，本工序最早的前提下，本工序最早可能完工时间可以推迟的时间。可能完工时间可以推迟的时间。 R(i, j)= tLS(i, j) -tES(i, j) = tLF(i, j) -tEF(i, j) = tL( j) -tE(i) -t(i, j) 单时差单时差r(i, j)：不影响其紧后工序：不影响其紧后工序最早可能开工最早可能开工的前提下，本工序最早的前提下，本工序最早可能完工时间可以推迟的时间。可能完工时间可以推迟的时间。 r(i, j)= tE( j)

13、-tE(i) -t(i, j) 总时差为零的工序称为关键工序；关键工序组成关键路线。总时差为零的工序称为关键工序；关键工序组成关键路线。tEStEFtLStLFtEStEFtLStLFR(i,j)r(i,j)OR:SM11三、时差与关键路线三、时差与关键路线 124536badcegf548364100366111996611190OR:SM12四、时间参数算例四、时间参数算例 计算作业最早开始时间、最迟开始时间、最早结束时间、计算作业最早开始时间、最迟开始时间、最早结束时间、最迟结束时间以及时差，从表中寻找总时差与单时差都为最迟结束时间以及时差，从表中寻找总时差与单时差都为零的作业，即为关键

14、作业，将其连接起来就是关键路线。零的作业，即为关键作业，将其连接起来就是关键路线。( , )t i j( , )ESti j( , )EFti j( , )LSti j( , )LFti j( , )R i j( , )r i jOR:SM13例例1 某项工程由某项工程由11项作业组成（分别用代号项作业组成（分别用代号A,B,J,K表示，基础表示，基础代谢计划完成时间及作业间相互关系如表所示。代谢计划完成时间及作业间相互关系如表所示。OR:SM143 3 计划评审技术计划评审技术一、作业时间估计一、作业时间估计 工序时间的三种可能估计：工序时间的三种可能估计： 最乐观时间最乐观时间：在最理想的

15、情况下完成工序所需时间：在最理想的情况下完成工序所需时间a； 最悲观时间最悲观时间：在最不利的情况下完成工序所需时间：在最不利的情况下完成工序所需时间b； 最可能时间最可能时间：在正常情况下完成工序所需时间：在正常情况下完成工序所需时间m。加权平均就是工序时间加权平均就是工序时间t 22)664abbmat（，方差工序时间工程期望工期等于关键路线上各道工序的时间之和工程期望工期等于关键路线上各道工序的时间之和 。22)6()64(iiiiiiiEabbmaT，方差工期设规定的工程完工时间为设规定的工程完工时间为Tk，则完工时间的概率为，则完工时间的概率为EkTTx)(二、计算期望工期二、计算期

16、望工期 OR:SM15三三、PERT应用举例应用举例 某项目的作业流程及其时间估计某项目的作业流程及其时间估计 若合同规定工期为若合同规定工期为20，求如期完工的概率；若要求有，求如期完工的概率；若要求有90%的把握如的把握如期完工，求可接受的合同工期的为多少。期完工，求可接受的合同工期的为多少。 OR:SM16三三、PERT应用举例应用举例 1234a3b2c45d8e10f566g0449172323179740 参数计算参数计算 工程期望工期工程期望工期 TE=23 ，关键工序的方差，关键工序的方差 2 =49/9，则，则 (x)=-1.29，查表知，查表知 P(x)=9.9% P(x)

17、=90% ，查表知，查表知 (x)=1.3，则可接受的合同工期为，则可接受的合同工期为TE+ (x) =26OR:SM174 4 网络计划优化网络计划优化 由于网络计划编制所受限制条件不同，设计目标由于网络计划编制所受限制条件不同，设计目标不同，网络计划编制深度和使用范围的不同，对不同，网络计划编制深度和使用范围的不同，对网络计划编制优化主要有下述三种基本类型：网络计划编制优化主要有下述三种基本类型： 工期优化工期优化单纯压缩关键线路长度；单纯压缩关键线路长度； 费用优化费用优化寻求网络计划对象执行费用最低时寻求网络计划对象执行费用最低时的工期优化；的工期优化； 资源优化资源优化资源有限时工期

18、优化等。资源有限时工期优化等。 网络计划编制优化的基础是网络计划的机动时间，网络计划编制优化的基础是网络计划的机动时间，优化过程应逐步反复进行，通过对关键工作或非优化过程应逐步反复进行，通过对关键工作或非关键工作机动时间调整来实现网络计划工期、费关键工作机动时间调整来实现网络计划工期、费用、资源优化等。用、资源优化等。 OR:SM18（一）工期优化：（一）工期优化： 工期优化的目的是使初始工期符合规定工期的要求。工期优化的目的是使初始工期符合规定工期的要求。1、初始计划工期与规定工期相同；、初始计划工期与规定工期相同； 不必修改初始网络计划，但这种情况极其偶然。不必修改初始网络计划，但这种情况

19、极其偶然。2、初始计划工期小于规定工期；、初始计划工期小于规定工期； （1）根据合同中的奖罚条款进行成本与收益的比）根据合同中的奖罚条款进行成本与收益的比较，取成本小、收益大者方案为优；较，取成本小、收益大者方案为优； （2）考虑将工期延长至规定工期，以降低资源消）考虑将工期延长至规定工期，以降低资源消耗强度，抽出人力和机械去加强其他重点工程。耗强度，抽出人力和机械去加强其他重点工程。首先：延长某些关键工作的时间即关键工序；其次：延长资源消耗强度大的关键工作；OR:SM193、初始计划工期大于规定工期、初始计划工期大于规定工期T=初始计划工期规定工期初始计划工期规定工期 第一、必须压缩某些关键

20、工作的工作时间；第二、原来的关键线路压缩后可能转化为非关键工作，而原来的非关键线路这时可能上升为关键线路，出现新的关键工作，这时若要继续缩短工期，也应该考虑压缩这些新的关键工作；OR:SM203、初始计划工期大于规定工期、初始计划工期大于规定工期T=初始计划工期规定工期初始计划工期规定工期 第一、必须压缩某些关键工作的工作时间；第二、原来的关键线路压缩后可能转化为非关键工作，而原来的非关键线路这时可能上升为关键线路，出现新的关键工作，这时若要继续缩短工期，也应该考虑压缩这些新的关键工作；OR:SM21B4500606000604711770107060080806001100135135110080011