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

OR:SM 网网络计络计划的划的发发展展历历程程 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)网网络计络计划技划技术术的特性的特性 网网络计络计划技划技术术只不只不过过是反映和表达是反映和表达项项目目计计划安排的一种方法，是划安排的一种方法，是被被项项目施工技目施工技术术所决定的，它只能适所决定的，它只能适应项应项目施工方法的要求。是把目施工方法的要求。是把工程工程进进度安排通度安排通过过网网络络的形式直的形式直观观地反映出来。地反映出来。第第7章章 计计划划评审评审方法和关方法和关键键路路线线法法1OR:SM1 1 PERT网网络图络图 1-1PERT1-1PERT网网络图络图的一些基本概念的一些基本概念工序工序(作作业业)：一一项项需要人需要人财财物或物或时间时间等等资资源的相源的相对对独立的活独立的活动过动过程程在网在网络图络图中用箭中用箭线线“”表示，表示，前面直接相前面直接相连连工序称工序称紧紧前工序，前工序，直接相直接相连连的后的后继继工序工序为紧为紧后工序。后工序。结结点点(事件事件)：相相邻邻工序的分界点工序的分界点一般用一般用圆圆圈来表示，每个圈来表示，每个结结点点编编上上顺顺序号，序号，结结点既不消耗人力、物力，也不占用点既不消耗人力、物力，也不占用时间时间。路路线线：指指PERT网网络络图图中中，从从最最初初事事件件到到最最终终事事件件的的由由各各项项作作业业连连贯贯组组成成的的一条路一条路。关关键键路路线线：指指从从最最初初事事件件到到最最终终事事件件路路条条可可以以有有不不同同的的路路，各各项项作作业业累累计计时时间间最最长长的那条路的那条路。网网络图络图由工序、事由工序、事项项及及时间时间参数所构成的有向参数所构成的有向图图即即为为网网络图络图。箭箭线线表示工序表示工序,结结点点为为工序工序间间相互关系的网相互关系的网络图络图，称箭，称箭线线式网式网络络结结点表示工序点表示工序,箭箭线为线为工序工序间间相互关系的网相互关系的网络图络图，称，称结结点式网点式网络络2OR:SM一、网一、网络计络计划的划的图图示形式示形式 1 1、箭、箭线线式网式网络图络图 21A25B343C55D5Et作业时间iN作业名称j2 2、结结点式网点式网络图络图 t作业时间N作业名称iNti作业序号1225433555603OR:SM二、箭二、箭线线式网式网络图络图的的规则规则 工序表示的工序表示的规规定定一条箭一条箭线线和它的相关事和它的相关事项项只能代表一道工序，不能代表多道工序，只能代表一道工序，不能代表多道工序，两个两个结结点之点之间间只能有一条箭只能有一条箭线线相相连连。不允不允许许出出现现缺口与回路缺口与回路网网络图络图中中只能有一个始点和一个只能有一个始点和一个终终点点，使得自网，使得自网络图络图的始点的始点经经由任何路径都由任何路径都可以到达可以到达终终点。点。虚工序虚工序虚工序是虚工序是为为了表达相了表达相邻邻工序之工序之间间的的逻辑逻辑关系而关系而虚虚设设的工序的工序。不消耗不消耗时间时间、费费用和用和资资源，一般用虚箭源，一般用虚箭线线表示。表示。方向的方向的规规定定网网络图络图是有方向的，工序是有方向的，工序应应按工按工艺艺流程流程顺顺序或工作序或工作逻辑逻辑关系关系从左向右排列从左向右排列。编编号号的的规规定定编编号号应应从始从始结结点开始，按照点开始，按照时时序依次从小到大序依次从小到大对结对结点点编编号，直到号，直到终结终结点。点。编编号号时时不允不允许许箭箭头编头编号小于箭尾号小于箭尾编编号号。4OR:SM 对对承担的工程承担的工程经过经过工序分解、工工序分解、工时时确定，根据生确定，根据生产产工工艺艺、生生产组织产组织的制的制约约确定出各工序确定出各工序间间的的逻辑逻辑关系后，可以用一关系后，可以用一张张网网络图络图把上述各点把上述各点统统一反映出来，借以形象地表达工程一反映出来，借以形象地表达工程计计划方案划方案的的编编制。制。绘绘制网制网络图络图：前：前进进法、后退法、任意法。法、后退法、任意法。草草图图逐步逐步调调整整（尽量消除箭杆的交叉）（尽量消除箭杆的交叉）（正确运用虚工序）（正确运用虚工序）排列整排列整齐齐、完整准确反映工程、完整准确反映工程计计划划编编制的网制的网络图络图。注意：注意：1.1.总总开工、开工、总总完工事完工事项项都是唯一的；都是唯一的；2.2.编编号：号：总总开工事开工事项项1 1，各事，各事项编项编号不重复，任一工序完工事号不重复，任一工序完工事项编项编号大于开工事号大于开工事项编项编号，号，总总完工事完工事项为项为n.n.网网络图络图的建立的建立5OR:SM三、箭三、箭线线式网式网络图举络图举例例 某工程的工程一某工程的工程一览览表表 124536badcegf364458106OR:SM2 PERT2 PERT网网络图络图的的计计算算一、一、结结点的点的时间时间参数参数 结结点的最早点的最早时间时间tE(j)tE(j)等于从始点开始到本等于从始点开始到本结结点的最点的最长长路路线线上各道工序上各道工序时间时间之和。之和。从始点事从始点事项项开始，自左向右，开始，自左向右，顺顺着箭着箭线线方向逐个方向逐个计计算算。结结点的最点的最迟时间迟时间 tL(j)指以指以该结该结点点为结为结束的各道工序最束的各道工序最迟迟必必须须完工的完工的时时刻，否刻，否则则将会影响将会影响后后续续工序按工序按时时开工，以至推开工，以至推迟迟整个工程的完工整个工程的完工时间时间。从从终终点开始，从右向左，逆箭点开始，从右向左，逆箭线线方向逐个方向逐个计计算。算。7OR:SM一、一、结结点的点的时间时间参数参数 计计算算结结点点时间时间参数参数124536badcegf5483641003661119966111908OR:SM二、作二、作业业的的时间时间参数参数 最早可能开工最早可能开工时间时间tES(i,j)一个作一个作业业必必须须在其各在其各紧紧前作前作业业都完工后才能开工，都完工后才能开工，作作业业最早可能开工最早可能开工时间时间等于其箭尾事等于其箭尾事项项的最早的最早时间时间。tES(i,j)=tE(i)最早可能完工最早可能完工时间时间 tEF(i,j)从最早可能开工从最早可能开工时间时间开工，完成本作开工，完成本作业业的的时间时间。tEF(i,j)=tES(i,j)+t(i,j)最最迟迟必必须须开工开工时间时间 tLS(i,j)在不影响工程如期完工的前提下，作在不影响工程如期完工的前提下，作业业最最迟迟必必须须开工的开工的时时刻。刻。等于它的箭等于它的箭头头事事项项的最的最迟时间迟时间减去本作减去本作业业的作的作业时间业时间 tLS(i,j)=tL(j)-t(i,j)最最迟迟必必须须完工完工时间时间 tLF(i,j)在不影响工程如期完工的前提下，作在不影响工程如期完工的前提下，作业业最最迟迟必必须须完工的完工的时时刻刻。tLF(i,j)=tLS(i,j)+t(i,j)=tL(j)9OR:SM三、三、时时差与关差与关键键路路线线 时时差又称差又称宽宽裕裕时间时间：不影响如期完成任：不影响如期完成任务务的条件下，各道工序可以机的条件下，各道工序可以机动动使用的一段使用的一段时间时间。总总时时差差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)-tE(i)-t(i,j)总时总时差差为为零的工序称零的工序称为为关关键键工序；关工序；关键键工序工序组组成关成关键键路路线线。tEStEFtLStLFtEStEFtLStLFR(i,j)r(i,j)10OR:SM三、三、时时差与关差与关键键路路线线 124536badcegf54836410036611199661119011OR:SM四、四、时间时间参数算例参数算例 计计算作算作业业最早开始最早开始时间时间、最、最迟迟开始开始时间时间、最早、最早结结束束时间时间、最最迟结迟结束束时间时间以及以及时时差，从表中差，从表中寻寻找找总时总时差与差与单时单时差都差都为为零零的作的作业业，即，即为为关关键键作作业业，将其，将其连连接起来就是关接起来就是关键键路路线线。12OR:SM例例1 某某项项工程由工程由11项项作作业组业组成（分成（分别别用代号用代号A,B,J,K表示，基表示，基础础代代谢计谢计划完成划完成时间时间及作及作业间业间相互关系如表所示。相互关系如表所示。13OR:SM3 3 计计划划评审评审技技术术一、作一、作业时间业时间估估计计 工序工序时间时间的三种可能估的三种可能估计计：最最乐观时间乐观时间：在最理想的情况下完成工序所需：在最理想的情况下完成工序所需时间时间a；最悲最悲观时间观时间：在最不利的情况下完成工序所需：在最不利的情况下完成工序所需时间时间b；最可能最可能时间时间：在正常情况下完成工序所需：在正常情况下完成工序所需时间时间m。加加权权平均就是工序平均就是工序时间时间t 工程期望工期等于关工程期望工期等于关键键路路线线上各道工序的上各道工序的时间时间之和之和。设规设规定的工程完工定的工程完工时间为时间为Tk，则则完工完工时间时间的概率的概率为为二、二、计计算期望工期算期望工期 14OR:SM三三、PERT应应用用举举例例 某某项项目的作目的作业业流程及其流程及其时间时间估估计计 若合同若合同规规定工期定工期为为20，求如期完工的概率；若要求有，求如期完工的概率；若要求有90%的把握如的把握如期完工，求可接受的合同工期的期完工，求可接受的合同工期的为为多少。多少。15OR:SM三三、PERT应应用用举举例例 1234a3b2c45d8e10f566g0449172323179740参数参数计计算算工程期望工期工程期望工期 TE=23，关关键键工序的方差工序的方差 2=49/9，则则 (x)=-1.29，查查表知表知 P(x)=9.9%P(x)=90%，查查表知表知 (x)=1.3，则则可接受的合同工期可接受的合同工期为为TE+(x)=2616OR:SM4 4 网网络计络计划划优优化化由于网由于网络计络计划划编编制所受限制条件不同，制所受限制条件不同，设计设计目目标标不不同，网同，网络计络计划划编编制深度和使用范制深度和使用范围围的不同，的不同，对对网网络络计计划划编编制制优优化主要有下述三种基本化主要有下述三种基本类类型：型：工期工期优优化化单纯压缩单纯压缩关关键线键线路路长长度；度；费费用用优优化化寻寻求网求网络计络计划划对对象象执执行行费费用最低用最低时时的的工期工期优优化；化；资资源源优优化化资资源有限源有限时时工期工期优优化等。化等。网网络计络计划划编编制制优优化的基化的基础础是网是网络计络计划的机划的机动时间动时间，优优化化过过程程应应逐步反复逐步反复进进行，通行，通过对过对关关键键工作或非关工作或非关键键工作机工作机动时间调动时间调整来整来实现实现网网络计络计划工期、划工期、费费用、用、资资源源优优化等。化等。17OR:SM（一）工期（一）工期优优化：化：工期工期优优化的目的是使初始工期符合化的目的是使初始工期符合规规定工期的要求。定工期的要求。1、初始、初始计计划工期与划工期与规规定工期相同；定工期相同；不必修改初始网不必修改初始网络计络计划，但划，但这这种情况极其偶然。种情况极其偶然。2、初始、初始计计划工期小于划工期小于规规定工期；定工期；（1）根据合同中的）根据合同中的奖罚奖罚条款条款进进行成本与收益的比行成本与收益的比较较，取成本小、收益大者方案取成本小、收益大者方案为优为优；（2）考）考虑虑将工期延将工期延长长至至规规定工期，以降低定工期，以降低资资源消耗源消耗强强度，抽出人力和机械去加度，抽出人力和机械去加强强其他重点工程。其他重点工程。首先：延长某些关键工作的时间即关键工序；其次：延长资源消耗强度大的关键工作；18OR:SM3、初始、初始计计划工期大于划工期大于规规定工期定工期T=初始初始计计划工期划工期规规定工期定工期 第一、必须压缩某些关键工作的工作时间；第二、原来的关键线路压缩后可能转化为非关键工作，而原来的非关键线路这时可能上升为关键线路，出现新的关键工作，这时若要继续缩短工期，也应该考虑压缩这些新的关键工作；19OR:SM3、初始、初始计计划工期大于划工期大于规规定工期定工期T=初始初始计计划工期划工期规规定工期定工期 第一、必须压缩某些关键工作的工作时间；第二、原来的关键线路压缩后可能转化为非关键工作，而原来的非关键线路这时可能上升为关键线路，出现新的关键工作，这时若要继续缩短工期，也应该考虑压缩这些新的关键工作；20OR:SM例：例：B4500606000604711770107060080806001100135135110080011011080060201201008007047135801174760301351059030135017017013501002013511512018ESTFLFEFLSFF15324678A60D20F18G30K25L35H15E40C1021OR:SM求:计划工期为150天时的方案;思考:实际工期为170天,计划工期为150天,T=20天22OR:SM关键工作中每缩短一天所增加费用最少的是K工作,能缩短10天,因B、F、H工作的自由时差为30、47、18天，故可缩短K工作10天。增加的直接费用=10290=2900元减少的间接费用=10400=4000元再次找寻关键线路中费用最小的是G工作，G工作能缩短10天，但H作业只有8天的自由时差，因此，缩短8天将产生新的关键线路。故缩短G工作8天。增加增加的直接费用=8350=2800元减少的间接费用=8400=3200元合计增加400元合计增加1100元23OR:SM产生新的关键线路A-D-G-K-L与A-D-H-L，再缩短2天。方案：缩短D工作2天：增加直接费用=2400=800 减少间接费用=2400=800方案：缩短G工作2天：增加直接费用=2350=700缩短H工作2天：增加直接费用=2400=800 减少间接费用=2400=800合计增加700元故采用方案合计增加0元24OR:SM结论：1、缩短K工作10天，增加总成本1100元；2、缩短G工作8天，增加总成本400元；3、缩短D工作2天，增加总成本为0元；故T=150天，总成本减少1500元。25