运筹学教程课件运筹十一

1、第十一章、网络计划分析11.1 概述1、网络计划方法的 基本概念 用网络分析的方法编制工程项目进度计划。它是用网络图的形式表示一个工程项目的若干作业在时间上的相互衔接关系，并通过一些分析计算为项目管理提供辅助决策信息。2、发展简史1）1956年 美观杜邦公司和兰德公司合作运用图论方法表示工程项目的计划，定名为关键路线法（Critical Path Method, CRM);2)1957年，美国海军负责北极星导弹核潜艇计划的特种计划局委托咨询公司提出科学组织管理的计划评审技术（Program Evaluation and Review Technique, PERT)，58年9月第一颗北极星导弹

2、发射成功；3、62年以后，CPM和PERT开始在民用企业运用4、1965年，开始推广应用CPM和PERT科学方法，又取名为统筹法。11.2网络计划方法一、网络图的组成1、作业 （Job, Activity) 也称活动和工序。是指一项具有耗费一定时间的具体活动过程。用带箭头的线段表示。如：表示作业开始，表示作业完成，箭线的长短与时间长短无关。126543设计60下料10木模40 加工118加工215装试352、事项（Event)也称节点。是作业开始或完成的瞬时状态。只表示相关作业的衔接点。用带标号的圆圈表示。如这里表示作业，则表示,结点。3、路（Path)从起点到终点的一条通路。1）路长：路的总

3、长度2）关键路线：路长最长的路线3）关键作业：关键路线上的作业4)网络图中的路图9.1 网络图中的路二、网络图的绘制1、任务分解（1）紧前作业：即紧挨着某一作业前面的那些作业；（2）紧后作业：即紧挨着某一作业后面的那些作业；（3）平行作业：即与某一作业同时进行的那些作业；（4）中途作业：即在某一作业中途可以进行的的那些作业；2、画图1）网络图不能出现回路2）任一箭线与一作业唯一一一对应，即不能出现：二、网络图的绘制（续）3）虚作业：作业时间为零的作业；4）虚作业的应用（1）解决两个接点间有两个以上作业问题（2）解决不同的衔接关系A作业完成后便可进行C作业，而D作业则须在A与B两个作业都完成以后

4、才能进行二、网络图的绘制（续）（3）平行作业（4）交叉作业5）作业的集中二、网络图的绘制（续）3、编号 一个事项有一个顺序号，不应重复，一个作业的二个相关事项可写成 ij ,编号从始点开始，由小到大。4. 网络图编绘举例二、网络图的绘制（续）图9.3 预算计划编制网络图三、网络图的时间参数和计算方法1、作业时间的确定1）一时估计法：以同类作业时间为依据；三、网络图的时间参数和计算方法（续）2）三时估计法: t(i ,j)=(a+4c+b)/6其中，a,b,c分别为最乐观、最悲观和最可能的作业时间。并假定c的可能分别是a,b的两倍，取加权后得到上述公式。(a+2c)/3 + (b+2c)/3 /

5、2 =(a+4c+b)/63)利用过去资料求平均值法p2763、网络图的时间参数与计算1）节点的时间参数计算（1）节点最早开始时间Te（Earlist time) 向前标号法Te(j)=MaxTe(i)+t(i,j) 如图9.4所示例如TE（2）= 3， TE（4）= 4+2 = 63、网络图的时间参数与计算（续）图9.4 网络图的结点时间参数与计算2）结点最迟完成时间从终点开始，从右向左计算，到始点为止，用公式表示为：TL（i）=MinTL（j）-t（i，j）3）结点时差 S(i)=TL(i) - TE(i)(2)作业时间参数的计算作业最早的开始时间 TE S(i , j) TE S (i

6、, j)=TE( i )作业最早完成时间TE F (i , j) TE F (i , j)=TE( i ) + t (i , j)作业最迟必须开始时间TL S(i , j) TL S (i , j)=TL ( j ) - t (i , j)作业最迟必须完成时间TL F (i , j) TL F (i , j) =TL ( j)(2)作业时间参数的计算（续）图9.5 网络图的作业时间参数与计算3、表格法4、关键路线（1）关键节点：时差为零的节点；（2）关键作业：作业总时差为零的作业；（3）关键路线：由关键作业组成的路线，即将时差为零的工序串连起来就是要寻找的关键路线。5、注意事项（1）关键路线为

7、总作业时间最长的作业路线，由于项目完成必须使所有作业完成，所以，关键路线决定了整个项目的工期；（2）关键路线由关键作业连接起来组成；5、注意事项（续）（3）用关键节点起来组成关键路线可能会发生错误。如在9.4中，由关键节点联结起来的路线有两条。图9.6 关键节点联结起来的路线I (路长为11)图9.7 关键节点联结起来的路线II(路长为12) （4）在实际寻找关键路线时，仍可利用节点标号法，此时可能出现两种情况，第一种是用关键节点连接起来的路线只有唯一一条，则它就是所求的关键路线，第二种是用关键节点连接起来的路线只有多条，则取路长最长的一条路线为关键路线。（5）向关键作业要时间，向非关键作业要

8、资源。11.3 网络图的分析与应用一、甘特图关键路线为：1345。工期为35月。二、项目按期完成的概率分析1、项目完成时间的均值与方差设个作业完成的时间均值和均方差分别为t(i,j)=(a+4c+b)/6, =(b-a)/6则由中心极限定理可知，当关键作业数J充分大时，项目完成的时间可近似认为是服从正态分布。且其均值与均方差分别为 tm= (ai+4ci+bi)/6 c 2 = (bi - ai)/62 ， J为关键作业数2、项目按期完成的概率分析由上面分析可知，项目完成时间T服从均值和方差分别为tm和 c的正态分布，即：TN（ tm， c）二、项目按期完成的概率分析(续）3、例：设某工程网络

9、图如图9.8所示，试计算该工程在35天完成的概率，如果完成的概率要求达到97.7，则工程的工期应规定为多少天？ 图9.8 某工程的网络图二、项目按期完成的概率分析(续）解 利用节点标号法，如图9.8所示。可得关键路线为：1345，路长为32。即tm=32。此外，利用均方差计算公式可得 c= 5.1 1）当T=35天时，z=(T tm)/C=(35-32)/5.1 =0.5882查正态分布表可得， P(Z 0.5882)=0.7218即整个工程在35天完成的概率为0.72582)当P(Z z)=0.977时，查正态分布表可z=2.0 所以T= z*C + tm =2*5.1+32=42.2即该工

10、程完成概率为97.7所需天数为42.2天。3)问题：工程在32天（即按数学期望计算的工期）完成的概率为多大？三、作业开工早晚对项目费用支付的影响1、背景：（1）非关键作业存在时差； （2）资金具有时间价值。2、例。 某项目的网络图如图9.9所示，图中各边是数字表示作业的费用（元）和所需的时间（月）。图9.9 某项目的网络图三、作业开工早晚对项目费用支付的影响（续）表9.3 项目费用支付费用计算表由表9.3可作出早开工和晚开工的月费用支出计划图9.10。根据早开工和晚开工的月费用支出计划图9.10可得到早开工和晚开工的累计费用曲线图9.11图9.10 早开工和晚开工的月费用支出计划图三、作业开工

11、早晚对项目费用支付的影响（续）图 9.11 早开工和晚开工的累计费用四、经济赶工分析讨论如何以最少的直接成本来实现经济赶工的方法。1）直接成本与时间的关系 工期 费用图9.12 直接成本与时间的关系四、经济赶工分析（续）2）成本斜率=（赶工成本 - 正常成本）/（正常时间-赶工时间）3）经济赶工方法：在关键路线上，对成本斜率最小的关键作业进行赶工。4）例。图9.13某方案的网络图四、经济赶工分析（续）表9.4 成本斜率表在关键路线上的所有关键作业中，成本斜率最小是34，其成本斜率为70元/天，故将该作业时间缩短一天，整个项目的工期缩短为29天。若将该作业再缩短一天，即项目工期缩短为28天，此时，在网络上出现三条关键路线。如图9.14所示四、经济赶工分析（续）图9.14 缩短工期后的关键路线四、经济赶工分析（续）如果要求将整个工期再缩短一天成为27天时，由于关键路线已有三条，因此必须对每