《运筹学》课件运筹九.ppt

1、第九章、网络计划分析第九章、网络计划分析1、网络计划方法的、网络计划方法的 基本概念基本概念 用网络分析的方法编制工程项目进度计划。它是用网络图的用网络分析的方法编制工程项目进度计划。它是用网络图的形式表示一个工程项目的若干作业在时间上的相互衔接关系，形式表示一个工程项目的若干作业在时间上的相互衔接关系，并通过一些分析计算为项目管理提供辅助决策信息。并通过一些分析计算为项目管理提供辅助决策信息。2、发展简史、发展简史1）1956年年 美观杜邦公司和兰德公司合作运用图论方法表示工美观杜邦公司和兰德公司合作运用图论方法表示工程项目的计划，定名为关键路线法（程项目的计划，定名为关键路线法（Criti

2、cal Path Method,CRM);2)1957年，美国海军负责北极星导弹核潜艇计划的特种计划局年，美国海军负责北极星导弹核潜艇计划的特种计划局委托咨询公司提出科学组织管理的计划评审技术（委托咨询公司提出科学组织管理的计划评审技术（Program Evaluation and Review Technique,PERT)，58年年9月第一颗北月第一颗北极星导弹发射成功；极星导弹发射成功；3、62年以后，年以后，CPM和和PERT开始在民用企业运用开始在民用企业运用4、1965年，开始推广应用年，开始推广应用CPM和和PERT科学方法，又取名为统科学方法，又取名为统筹法。筹法。9.1统筹法

3、统筹法一、网络图的组成一、网络图的组成1 1、作业、作业 （Job,Activity)Job,Activity)也称活动和工序。是指一也称活动和工序。是指一项具有耗费一定时间的具体活动过程。用带箭头的线项具有耗费一定时间的具体活动过程。用带箭头的线段表示。如：段表示。如：表示作业开始，表示作业开始，表示作业完成，箭线的长短与时间表示作业完成，箭线的长短与时间长短无关。长短无关。126543设计60下料10木模40 加工118加工215装试351 12 22、事项（、事项（Event)也称节点。是作业开始或完成的瞬时状态。只表示相关也称节点。是作业开始或完成的瞬时状态。只表示相关作业的衔接点。用

4、带标号的圆圈表示。如作业的衔接点。用带标号的圆圈表示。如这里这里表示作业，则表示表示作业，则表示,结点。结点。3、路（、路（Path)从起点到终点的一条通路。从起点到终点的一条通路。1）路长：路的总长度）路长：路的总长度2）关键路线：路长最长的路线）关键路线：路长最长的路线3）关键作业：关键路线上的作业）关键作业：关键路线上的作业2 23 34 42 23 33 34 44)网络图中的路网络图中的路图图9.1 网络图中的路网络图中的路23415673547639521257(1)路长151457(2)171467(3)191367(4)16二、网络图的绘制二、网络图的绘制1、任务分解、任务分解

5、（1）紧前作业：即紧挨着某一作业前面的那些作业；）紧前作业：即紧挨着某一作业前面的那些作业；（2）紧后作业：即紧挨着某一作业后面的那些作业；）紧后作业：即紧挨着某一作业后面的那些作业；（3）平行作业：即与某一作业同时进行的那些作业；）平行作业：即与某一作业同时进行的那些作业；（4）中途作业：即在某一作业中途可以进行的的那些作业；）中途作业：即在某一作业中途可以进行的的那些作业；2、画图、画图1）网络图不能出现回路）网络图不能出现回路2）任一箭线与一作业唯一一一对应，即不能出现：）任一箭线与一作业唯一一一对应，即不能出现：1212二、网络图的绘制（续）二、网络图的绘制（续）3）虚作业：作业时间为

6、零的作业；虚作业：作业时间为零的作业；4）虚作业的应用）虚作业的应用（1）解决两个接点间有两个以上作业问题）解决两个接点间有两个以上作业问题（2）解决不同的衔接关系）解决不同的衔接关系12213245ABCD13245ABCD3A作业完成后便可进行作业完成后便可进行C作业，而作业，而D作业则须在作业则须在A与与B两个作业都完成以后两个作业都完成以后才能进行才能进行二、网络图的绘制（续）二、网络图的绘制（续）（3）平行作业）平行作业（4）交叉作业）交叉作业5）作业的集中）作业的集中132456加工1加工2加工315243678二、网络图的绘制（续）二、网络图的绘制（续）3、编号、编号 一个事项有

7、一个顺序号，不应重复，一个作业的二一个事项有一个顺序号，不应重复，一个作业的二个相关事项可写成个相关事项可写成 ij,编号从始点开始，由小到大。编号从始点开始，由小到大。4.网络图编绘举例网络图编绘举例表表 9.1 各各项项工工作作的的前前后后关关系系表表工工作作分分项项 i-j说说明明紧紧前前工工作作负负责责部部门门A1-2确确定定产产品品数数量量销销售售部部门门B1-3调调查查市市场场价价格格销销售售部部门门C3-5定定价价A、B销销售售经经理理D2-4安安排排生生产产进进度度A生生产产部部门门E4-5确确定定生生产产费费用用D生生产产部部门门F5-6准准备备预预算算报报告告C、E计计划划

8、部部门门二、网络图的绘制（续）二、网络图的绘制（续）图图9.3 预算计划编制网络图预算计划编制网络图三、网络图的时间参数和计算方法三、网络图的时间参数和计算方法1、作业时间的确定、作业时间的确定1）一时估计法：以同类作业时间为依据；）一时估计法：以同类作业时间为依据；143526ABCDEF三、网络图的时间参数和计算方法三、网络图的时间参数和计算方法（续）（续）2）三时估计法）三时估计法:t(i,j)=(a+4c+b)/6其中，其中，a,b,c分别为最乐观、最悲观和最可能的作业时间。并分别为最乐观、最悲观和最可能的作业时间。并假定假定c的可能分别是的可能分别是a,b的两倍，取加权后得到上述公式

9、。的两倍，取加权后得到上述公式。(a+2c)/3 +(b+2c)/3/2=(a+4c+b)/63)利用过去资料求平均值法利用过去资料求平均值法p2763 3、网络图的时间参数与计算网络图的时间参数与计算1 1）节点的时间参数计算节点的时间参数计算（1 1）节点最早开始时间）节点最早开始时间TeTe（Earlist time)Earlist time)向前标号法向前标号法Te(j)=MaxTe(i)+t(i,j)Te(j)=MaxTe(i)+t(i,j)如图如图9.4所示例如所示例如TE（2）=3，TE（4）=4+2=63 3、网络图的时间参数与计算网络图的时间参数与计算（续）（续）图图9.4

10、网络图的结点时间参数与计算网络图的结点时间参数与计算2）结点最迟完成时间从终点开始，从右向左计算，到始）结点最迟完成时间从终点开始，从右向左计算，到始点为止，用公式表示为：点为止，用公式表示为：TL（i）=MinTL（j）-t（i，j）3）结点时差）结点时差 S(i)=TL(i)-TE(i)1 12 23 34 45 56 67 78 84 42 24 41 11 13 31 11 12 20 04 46 69 9101012125 56 60 0121210109 96 64 49 98 8(2)作业时间参数的计算作业时间参数的计算 作业最早的开始时间作业最早的开始时间 TE S(i,j)T

11、E S(i,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 网络图的作业时间参数与计算网络图的作业时间参数与计算1 12 23 34 45 56 67 78 84 42 24 41 11 13 31 11 12 20 04 46 69 910104 45 50 010109 96

12、64 48 87 74 45 56 69 93、表格法、表格法表表 9.2 网络图的作业时间参数计算表网络图的作业时间参数计算表ijt(i,j)(2)TE S(3)TE F(4)TL S(5)TL F(6)r(i,j)(7)s(i,j)(8)CJ(9)124040400122314578302424646002425448591136156893045369690045571910910005767167910337821012101200784 4、关键路线、关键路线（1 1）关键节点：时差为零的节点；）关键节点：时差为零的节点；（2 2）关键作业：作业总时差为零的作业；）关键作业：作业总时

13、差为零的作业；（3 3）关键路线：由关键作业组成的路线，即将时差为零）关键路线：由关键作业组成的路线，即将时差为零的工序串连起来就是要寻找的关键路线。的工序串连起来就是要寻找的关键路线。5 5、注意事项、注意事项（1 1）关键路线为总作业时间最长的作业路线，由于项目）关键路线为总作业时间最长的作业路线，由于项目完成必须使所有作业完成，所以，关键路线决定了整完成必须使所有作业完成，所以，关键路线决定了整个项目的工期；个项目的工期；（2 2）关键路线由关键作业连接起来组成；）关键路线由关键作业连接起来组成；5、注意事项（续）、注意事项（续）（3）用关键节点起来组成关键路线可能会发生错误。）用关键节

14、点起来组成关键路线可能会发生错误。如在如在9.4中，由关键节点联结起来的路线有两条。中，由关键节点联结起来的路线有两条。图图9.6 关键节点联结起来的路线关键节点联结起来的路线I(路长为路长为11)图图9.7 关键节点联结起来的路线关键节点联结起来的路线II(路长为路长为12)（4）在实际寻找关键路线时，仍可利用节点标号法，此时可）在实际寻找关键路线时，仍可利用节点标号法，此时可能出现两种情况，第一种是用关键节点连接起来的路线只能出现两种情况，第一种是用关键节点连接起来的路线只有唯一一条，则它就是所求的关键路线，第二种是用关键有唯一一条，则它就是所求的关键路线，第二种是用关键节点连接起来的路线

15、只有多条，则取路长最长的一条路线节点连接起来的路线只有多条，则取路长最长的一条路线为关键路线。为关键路线。（5）向关键作业要时间，向非关键作业要资源。）向关键作业要时间，向非关键作业要资源。125784412124574231829.2 网络图的分析与应用网络图的分析与应用一、甘特图一、甘特图关键路线为：关键路线为：1345。工期为。工期为35月。月。1 12 25 53 34 47 78 8131317176 65 5月0133036二、项目按期完成的概率分析二、项目按期完成的概率分析1、项目完成时间的均值与方差、项目完成时间的均值与方差设个作业完成的时间均值和均方差分别为设个作业完成的时间

16、均值和均方差分别为t(i,j)=(a+4c+b)/6,=(b-a)/6则由中心极限定理可知，当关键作业数则由中心极限定理可知，当关键作业数J J充分大时，项目完成充分大时，项目完成的时间可近似认为是服从正态分布。且其均值与均方差分的时间可近似认为是服从正态分布。且其均值与均方差分别为别为 tm=(ai+4ci+bi)/6 c 2=(bi-ai)/62，J为关键作业数为关键作业数2、项目按期完成的概率分析、项目按期完成的概率分析由上面分析可知，项目完成时间由上面分析可知，项目完成时间T服从均值和方差分别为服从均值和方差分别为tm和和 c的正态分布，即：的正态分布，即：TN（tm，c）二、项目按期

17、完成的概率分析二、项目按期完成的概率分析(续）续）3、例：设某工程网络图如图、例：设某工程网络图如图9.8所示，试计算该工程在所示，试计算该工程在35天完成的概率，如果完成的概率要求达到天完成的概率，如果完成的概率要求达到97.7，则，则工程的工期应规定为多少天？工程的工期应规定为多少天？图图9.8 某工程的网络图某工程的网络图1 12 25 53 34 42-5-142-5-146 65-14-175-14-1713133-12-213-12-2112126-15-306-15-3016162-5-82-5-85 51-4-71-4-74 40 06 62828323212120 01515

18、121232322828二、项目按期完成的概率分析二、项目按期完成的概率分析(续）续）解解 利用节点标号法，如图利用节点标号法，如图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

19、=2.0 所以所以T=z*C+tm=2*5.1+32=42.2即该工程完成概率为即该工程完成概率为97.7所需天数为所需天数为42.2天。天。3)问题：工程在问题：工程在32天（即按数学期望计算的工期）完成天（即按数学期望计算的工期）完成的概率为多大？的概率为多大？三、作业开工早晚对项目费用支付的影响三、作业开工早晚对项目费用支付的影响1、背景：（、背景：（1）非关键作业存在时差）非关键作业存在时差 （2）资金具有时间价值。）资金具有时间价值。2、例。、例。某项目的网络图如图某项目的网络图如图9.9所示，图中各边是数字，图中各边是数字表示作业的费用（元）和所需的时间（月）。表示作业的费用（元）

20、和所需的时间（月）。图图9.9 某项目的网络图某项目的网络图1 12 25 53 34 46 67 78 84 4800080002 2600060006 690009000450045009 92 2500050005 51000010000101015000150007 7700070001 1400040003 375007500三、作业开工早晚对项目费用支付的影响（续）三、作业开工早晚对项目费用支付的影响（续）表表9.3 项目费用支付费用计算表项目费用支付费用计算表由表由表9.3可作出早开工和晚开工的月费用支出计划图可作出早开工和晚开工的月费用支出计划图9.10。根据早开工和晚开工的月

21、费用支出计划图根据早开工和晚开工的月费用支出计划图9.10可得到早开可得到早开工和晚开工的累计费用曲线图工和晚开工的累计费用曲线图9.11作作 业业时时 间间（月月）早早 开开 工工时时 间间晚晚 开开 工工时时 间间总总 费费 用用（元元）月月 费费 用用（元元）（1，2）40080002000（2，3）241460003000（2，4）64490001500（3，5）361675002500（4，5）910104500500（1，6）20150002500（6，5）5214100002000（6，7）72370001000（5，8）1191940004000（7，8）10910150001

22、500图图9.10 早开工和晚开工的月费用支出计划图早开工和晚开工的月费用支出计划图1 16 62 23 34 45 50 01 12 23 34 45 56 67 78 89 91010 111112121313 1414 151516161717 1818 191920207 78 8454545451 16 62 23 34 45 58 87 75050 50507575 75757070 50505050 30302020 20202020 20202020 20202020 20202020 40404545 9090 140140460460340340 4104102652651

23、90190510510 540540560560580580 600600 620620640640 660660680680 700700 720720760760202045454545 30302525 25252525 25252525 25252020 20202020 20207070 70706565 65656565 55556565 110110240240190190 215215165165140140265265 290290310310 330330350350 370370440440 510510575575 6406407057057607602020时时间间月

24、月月费用月费用100元100元月费用月费用100元100元累计费用累计费用100元100元累计费用累计费用100元100元20203030252515155 52020101025251515404020202525151510103030252540405 520201515三、作业开工早晚对项目费用支付的影响（续）三、作业开工早晚对项目费用支付的影响（续）图图 9.11 早开工和晚开工的累计费用早开工和晚开工的累计费用2 24 46 68 810101212141416161818202010000100000 020000200003000030000400004000050000500

25、00600006000070000700008000080000早开工费用支出早开工费用支出晚开工费用支出晚开工费用支出可行的预算可行的预算费用费用四、经济赶工分析四、经济赶工分析讨论如何以最少的直接成本来实现经济赶工的方法。讨论如何以最少的直接成本来实现经济赶工的方法。1）直接成本与时间的关系）直接成本与时间的关系 工期工期 费用费用图图9.12 直接成本与时间的关系直接成本与时间的关系赶工时间赶工时间正常时间正常时间正正常常成成本本赶赶工工成成本本正常点正常点赶工点赶工点直接成本曲线直接成本曲线作业时间作业时间成本成本四、经济赶工分析（续）四、经济赶工分析（续）2）成本斜率）成本斜率=（赶

26、工成本（赶工成本-正常成本）正常成本）/（正常时间（正常时间-赶工时间）赶工时间）3）经济赶工方法：在关键路线上，对成本斜率最）经济赶工方法：在关键路线上，对成本斜率最小的关键作业进行赶工。小的关键作业进行赶工。4）例。）例。1 12 23 34 45 56 67 76 65 51313101015159 95 55 58 87 70 06 611115 51313202030300 05 520203030212116161313图图9.13某方案的网络图某方案的网络图四、经济赶工分析（续）四、经济赶工分析（续）表表9.4 成本斜率表成本斜率表在关键路线上的所有关键作业中，成本斜率最小是在关

27、键路线上的所有关键作业中，成本斜率最小是34，其成本斜率为其成本斜率为70元元/天，故将该作业时间缩短一天，整个天，故将该作业时间缩短一天，整个项目的工期缩短为项目的工期缩短为29天。若将该作业再缩短一天，即项目天。若将该作业再缩短一天，即项目工期缩短为工期缩短为28天，此时，在网络上出现三条关键路线。天，此时，在网络上出现三条关键路线。如如图图9.14所示所示正正 常常赶赶 工工作作 业业时时 间间（天天）成成 本本（元元）时时 间间（天天）成成 本本（元元）成成 本本 斜斜率率（元元/天天）1 262105300901 353004380802 452404300602 554804660

28、1803 485605770703 6160011700504 6749065901004 715750139901205 7980089401406 7104507900150四、经济赶工分析（续）四、经济赶工分析（续）1 12 23 34 45 56 67 76 65 51313101015159 95 55 56 67 70 06 611115 51111181828280 05 518182828212116161111图图9.14 缩短工期后的关键路线缩短工期后的关键路线I II III 四、经济赶工分析（续）四、经济赶工分析（续）如果要求将整个工期再缩短一天成为如果要求将整个工期再

29、缩短一天成为27天时，由于关键路线天时，由于关键路线已有三条，因此必须对每条关键都缩短一天，才能达到。已有三条，因此必须对每条关键都缩短一天，才能达到。现在把三条关键路线和它们有关的成本斜率加以比较，如现在把三条关键路线和它们有关的成本斜率加以比较，如表表9.5所示。所示。从各条关键路线上选出成本斜率最小的为：在从各条关键路线上选出成本斜率最小的为：在I中选中选24，在，在II中选中选34，III中选中选36，三者成本斜率加起来为，三者成本斜率加起来为180元。元。我们把三个关键路线各缩短一天的各种优化组合列出来进我们把三个关键路线各缩短一天的各种优化组合列出来进行比较如表行比较如表9.6所示。所示。表表 9.5 从从各各条条关关键键路路线线上上选选出出成成本本斜斜率率最最小小表表关关键键路路线线 I关关键键路路线线 II关关键键路路线线 III作作业业成成 本本 斜斜率率 元元/天天作作业业成成 本本 斜斜率率 元元/天天作作业业成成 本本 斜斜率率 元元/天天908080607050100100150150150四、经济赶工分析（续）四、经济赶工分析（续）表表9.6 各方案比较表各方案比较表由表由表9.6可知选取方案可知选取方案B比较有利。比较有利。