《运筹学第09章课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第09章课件.ppt（74页珍藏版）》请在三一办公上搜索。
1、第九章网络计划,Network Programming,本章内容,网络图时间参数的计算网络计划的优化和实施管理图解评审法简介,用网络图编制的计划称为网络计划，网络计划技术由计划评审技术（Program Evaluation and Review Technique 简写为PERT）与关键路径法（Critical Path Method 简写为CPM）组成。,PERT主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。,CPM以经验数据确定工作时间，看作是确定的数值，主要研究项目的费用与工期的相互关系。通常将这两种方法融为一体，统
2、称为网络计划、网络计划技术(PERT/CPM)。,网络图的基本概念,网络计划的基本原理：从需要管理的任务总进度着眼，以任务中各工作所需要的工时为时间因素，按照工作的先后顺序和相互关系做出网络图，以反映任务全貌，实现管理过程的模型化。然后计算时间参数，找出计划中的关键工作和关键线路，以对任务的各项工作所需的人、财、物通过改善网络计划做出合理安排，得到最有方案并付诸实施。,网络计划主要应用于新产品研制与开发、大型工程项目的计划编制与计划的优化，是项目管理和项目安排领域目前比较科学的一种计划编制方法，比甘特图（Cantt chart）或称横道图(bar chart)计划方法有许多优点。,网络计划有利
3、于对计划进行控制、管理、调整和优化，更清晰地了解工作之间的相互联系和相互制约的逻辑关系，掌握关键工作和计划的全盘情况。,PERT最早应用于美国海军北极星导弹的研制系统，由于该导弹的系统非常庞大复杂,为找到一种有效的管理技术,设计了PERT这种方法,并使北极星导弹的研制周期缩短了一年半时间。,CPM是与PERT十分相似但又是独立发展的另一种技术，是1957年美国杜邦公司的沃克（M.R.walker）和兰德公司的小凯利(J.E.Kelley)共同研制的一种方法。它主要研究大型工程的费用与工期的相互关系。,箭示网络图: 用箭条表示工序的计划网络图。本章讲的就是箭示图,节点网络图: 用节点表示工序的计
4、划网络图,网络图: 由工序、事件及标有完成各道工序所需时间所构成的连通有向图。,工作： 或称为工序、活动，指任何消耗时间或资源的活动，如新产品设计中的初步设计、技术设计、工装制造等。根据需要，工序可以划分得粗一些，也可以划分得细一些。,1网络图,事件： 标志工作的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前面各顶作业（紧前工序）的结束，又标志着在它之后的各项作业（紧后工序）的开始。如机械造业中，只有完成铸锻件毛坯后才能开始机加工；各种零部件都完成后，才能进行总装等。,圆圈和里面的数字代表各事件，写在箭线中间的数字5为完成本工作所需时间，即
5、工作a:(1,2)，事项：1,2。,1网络图,紧前工序： 紧接某项工序的先行工序,紧后工序： 紧接某项工序的后续工序,前道工序： 某工序之前的所有工序,后续工序 ：某工序之后的所有工序,1网络图,(1)在一张网络图中，一般只允许出现一个起点节点和一个终点节点。,画网络图的规则,(2)网络图中不允许出现循环回路,(3)节点之间不允许有两个或两个以上的工作,(4)必须正确表示工作之间的前行后继关系,图9-4不符合该规则,图9-4,(5)虚工作的运用,图9-4,图9-4用添加虚工作的方法可以改为正确的图9-5,绘制网络图步骤,（1）任务分解,（2）绘制网络图,1网络图,1网络图,1.当工序a完工后b
6、和c可以开工,3.工序c在工序a完工后就可以开工，但工序d必须在a和b都完工后才能开工,2.当工序a和b完工后c和d可以开工,4.事件i、j之间有多道工序时，添加虚工序,6. 网络图只有一个发点（项目的开始点）一个收点（项目的结束点）。如图（e）所示，则应合成图（f）所示的一个始点及一个终点。,5. 用弧(i，j)表示一道工序，事件i是工序的开始，事件j是工序的完成，规定i j。见下图,【练习1】某项目由8道工序组成，工序明细表见表9-2所示。分别用箭线法和节点法绘制该项目的项目网络图。,1网络图,图9-8,1网络图,【练习2】根据某项目作业明细表93的资料，绘制项目网络图,【解】计划网络图如
7、下：,1网络图,a,6,1,b,9,c,13,d,5,e,16,f,12,h,12,g,10,i,8,k,20,j,17,l,25,图99箭线网络图,1,2,3,5,4,7,10,8,9,11,本章内容,网络图时间参数的计算网络计划的优化和实施管理图解评审法简介,一、工序时间的估计,三点估计法是事先估计出工序的三种可能完成时间，其期望值就作为工序时间的估计值。三种时间是：(1)完成工序（i，j）的最短时间，称为乐观时间，记为aij(2) 完成工序（i，j）的正常时间，称为最可能时间,记为mij(3) 完成工序（i，j）的最长时间，称为悲观时间，记为bij三种时间发生的概率分别为1/6、4/6、
8、1/6，则工序（i，j）完成时间的期望值和方差为：,2时间参数的计算,2时间参数的计算,二、事项时间参数,（1）事项的最早时间,（2）事项的最迟时间,（1）工作(i,j)的最早开始时间（Earliest start time for an activity）tES(i,j)。是指紧前工序的最早可能完工时间的最大值，计算公式为,（2）工序(i,j)的最早完工时间（Earliest finish time for an activity）tEF(i,j)。计算公式为,三、工作的时间参数,2时间参数的计算,(4) 工序(i,j)的最迟必须结束时间(Latest finish time for an
9、activity) tLF(i,j)。计算公式为,(3) 工序(i,j)的最迟必须开始时间（latest start time for an activity）tLS(i,j)。是指为了不影响紧后工序如期开工，工序最迟必须开工的时间，计算公式为,2时间参数的计算,(6)工序的单时差或自由时间(Free for an activity) F(i，j)。在不影响紧后工序的最早开始时间的条件下，工序(i,j) 的开始时间可以推迟的时间。计算公式为,(5) 工序(i,j)的总时差或松弛时间(Slack for an activity) S(i,j)。是工序(i,j)的最迟开始(结束)时间与最早开始(结
10、束)时间之差，计算公式为,工作总时差和单时差的区别与联系可以通过图9-14来说明。,总时差为零的工作链为关键路线,时间参数的图上计算法,25,26,23,23,23,23,20,20,18,18,10,10,0,0,4,4,32,32,31,31,1.先计算事项的时间参数,时间参数的图上计算法,25,26,23,23,23,23,20,20,18,18,10,10,0,0,4,4,32,32,31,31,2. 工作时间参数的计算,0,0,0,13,4,15,10,10,4,4,23,23,23,29,20,20,18,18,31,31,23,24,25,26,23,23,时间参数的图上计算法,
11、0,0,3.找出关键路线 ,0,0,0,13,4,15,10,10,4,4,23,23,23,29,20,20,18,18,31,31,23,24,25,26,23,23,时间参数的表上计算法,表9-4,工序时间是随机变量时，项目的完工期也是随机变量,设Xk为关键工序 k 所需时间的随机变量，则 Xk 相互独立，工序的期望时间及方差为,工程完工期的期望值及方差为,设关键工序数为n，工程的完工期是一随机变量,概率型网络图的时间参数计算,则由李雅普诺夫中心极限定理知(式中n为关键工序数）,即当n很大时Zn近似服从N（0，1）分布，则有,近似服从,即,概率型网络图的时间参数计算,设给定一个时间X0，
12、则工程完工时间不超过X0的概率为,要使工程完工的概率为p0，至少需要多少时间X0,查正态分布表求出X，由,得,概率型网络图的时间参数计算,例2已知某一计划（见图9-13）中各件工作的a,m,b值(单位为月)，见表9-5的第2、3、4列。要求：(1) 每件工作的平均工时t及均方差；(2) 画出网络图，确定关键路线；(3) 在25个月前完工的概率,图9-13,概率型网络图的时间参数计算,11,9,7,8,4,3,7,5,4,6,4,3,19,13,10,10,8,7,4,4,4,12,9,6,8,7,5,9,8,7,t,b,m,a,工作,表9-5,解：1.利用公式计算t和,概率型网络图的时间参数计
13、算,0.833,15.833,15,0,20.333,20.333,0.166,15.166,15,0.166,10.999,10.833,0,6.833,6.833,0.166,6.999,6.833,0.166,6.999,6.833,3.333,11.333,8,0,0,0,3.333,3.333,0,R,tLS,tES,工作,2.按t值计算出各工作的最早开始时间和最迟开始时间，总时差R；如表9-6,表9-6,概率型网络图的时间参数计算,3.确定关键工作为（1,3),(3,6),(6,7),即此计划在25个月前完成概率为0.5398。,概率型网络图的时间参数计算,【练习】（1）求工序的最
14、早开始和最迟开始时间。（2）求工程完工期的期望值及其概率。（3）要求完工的概率为0.95,至少需要多少天。,表9-7,图9-14,1,图9-15,【解】(1)工序的最早开始和最迟开始时间见图9-15,(2) 关键工序是c、f 和j，由表7-4及式(7.12)知，项目完工期的期望值、方差、标准差分别为 12.17+23.33+33.6769.1720.25+1.78+2.764.79， =2.1886,（3）X072，(X0)/=(7269.17)/2.1886=1.293,（4）已知概率p0=0.98，由式(7.15)，查正态分布表有,要使项目完工的概率为0.98，至少需要73.65天,本章内
15、容,网络图时间参数的计算网络计划的优化和实施管理图解评审法简介,3网络计划的优化和实施管理,网络计划中用关键线路控制工期，利用时差进行网络计划的优化。网络计划的优化：通过利用时差，不断改善网络计划的初始方案，在满足既定的条件下，按某一衡量指标（如时间、成本、物资）来寻求最优方案。,一、 时间优化 二 、费用优化 三 、资源优化：,类型,时间优化,1、将串联工作调整为平行工作。2、将串联工作调整为交叉工作。3、相应地推迟非关键工作的开始时间。4、相应地延长非关键线路中工作的工作时间。5 、从计划外增加资源。6、从计划外增加资源供应，以加快关键工作，缩短总工期。,总成本总应急成本总应急收益 总正常
16、成本总应急增加成本 总应急收益,单位时间工序的应急增加成本(成本斜率) (应急成本正常成本) （正常时间应急时间）,费用优化, 计算正常作业条件下工程网络计划的工期、关键线路和总直接费、总间接费及总费用。 计算各项工作的成本费率。 在关键线路上，选择成本费率(或组合直接费率）最小并且不超过工程间接费率的工作作为被压缩对象。,步骤和方法,费用优化, 将被压缩对象压缩至最短，当被压缩对象为一组工作时，将该组工作压缩同一数值，并找出关键线路，如果被压缩对象变成了非关键工作，则需适当延长其持续时间，使其刚好恢复为关键工作为止。 重新计算和确定网络计划的工期、关键线路和总直接费、总间接费、总费用。 重复
17、上述第三至第五步骤，直至找不到成本费率或组合成本费率不超过工程间接费率的压缩对象为止。此时即求出总费用最低的最优工期。 绘制出优化后的网络计划。在每项工作上注明优化的持续时间和相应的直接费用。,费用优化,图9-16,【例3】项目工序的正常时间、应急时间及对应的费用见表9-8。,（1）绘制项目网络图，按正常时间计算完成项目的总成本和工期。（2）按应急时间计算完成项目的总成本和工期。（3）按应急时间的项目完工期，调整计划使总成本最低。（4）已知项目缩短1天额外获得奖金5万元，减少间接费用1万元，求总成本最低的项目完工期，也称为最低成本日程。,【解】(1)项目网络图及时间参数见图9-17。项目的完工
18、期为210天，将表9-8正常成本一列相加得到总成本为506万元,C,24,H,23,B,21,E,26,D,25,J,18,G,28,A,19,F,25,I,27,L,28,12,K,35,M,30,13,N,25,11,O,0,0,0,19,40,40,40,66,64,66,89,112,139,210,0,139,157,185,174,210,185,157,180,145,139,112,84,89,64,40,84,59,58,19,0,图9-17,C,22,H,23,B,19,E,24,D,23,J,14,G,23,A,15,F,23,I,26,L,25,12,K,30,M,26
19、,13,N,20,11,O,0,0,0,15,34,34,34,58,56,58,79,102,128,187,0,128,142,167,158,187,167,142,161,131,128,102,79,79,56,34,79,56,55,15,0,图9-18,（2）项目网络图不变，时间参数见图9-18，完工期187天，将表9-8应急成本一列相加得到总成本为713万元,(3)图9-18中，非关键工序是D、E、G、K和M，可以看出，将工序D、E、G按正常时间施工时，最早开始和最迟开始时间不相等，说明按正常时间施工不影响项目的完工期（187天），见图9-19(a)。工序K和M按正常时间共要缩
20、短时间6天，见图9-19(b)。,E,26,D,25,G,28,O,0,34,34,60,60,79,79,54,53,12,K,35,M,30,13,J,14,L,25,13,N,20,11,应急时间路长：59,正常时间路长：65,12,K,30,M,26,13,应急时间路长：56,图9-19,(a),(b),则最优的决策方案是：关键工序A、B、C、F、H、I、J、L、N全部按应急时间施工，总成本等于各工序应急成本之和；工序D、E、G按正常时间施工，成本等于各工序正常成本之和；工序K缩短5天工序M缩短1天，成本等于正常成本加应急时间增加的成本。按项目完工期187天施工的最小成本是654万元，
21、成本分析见表9-8。调整后有两条关键路线，见图9-20,C,22,H,23,B,19,E,26,D,25,J,14,G,23,A,15,F,23,I,26,L,25,12,K,30,M,29,13,N,20,11,O,0,0,0,15,34,34,34,60,56,60,79,102,128,187,0,128,142,167,158,187,167,142,158,128,128,102,79,79,56,34,79,56,53,15,0,图9-20,(4)考虑缩短关键工序的时间，选择一天应急增加的成本小于等于6的关键工序采取应急措施来缩短时间，这样的工序有C、J、N，工序C缩短2天，工序J
22、缩短4天，工序N缩短2天。对图78进行第一次调整得到图9-21。得到两条关键路线，工序K和M变为关键工序，项目完工期为202天，缩短了8天。总成本变动额为: 2341228634（万元）,C,22,H,23,B,21,E,26,D,25,J,14,G,28,A,19,F,25,I,27,L,28,12,K,35,M,30,13,N,23,11,O,0,0,0,19,40,40,40,66,62,66,87,110,137,202,0,137,151,179,172,202,179,151,172,137,137,110,82,87,62,40,82,57,56,19,0,图9-21,检查图9-
23、21虚线围起来的部分。要缩短工期必须两条关键路线同时缩短时间，上面一条路线工序N还能缩短3天，因此下面一条路线只对工序K缩短3天，对图9-21调整得到图9-22。项目的完工期为199天，又缩短了3天，总成本变动额为 3232366（万元）,C,22,H,23,B,21,E,26,D,25,J,14,G,28,A,19,F,25,I,27,L,28,12,K,32,M,30,13,N,20,11,O,0,0,0,19,40,40,40,66,62,66,87,110,137,199,0,137,151,179,169,199,179,151,169,137,137,110,82,87,62,40
24、,82,57,56,19,0,图9-22,继续检查发现，缩短任何关键工序都不能降低成本，则总成本最低的项目工期是199天，总成本为 506-34-6466（万元）,(1) 资源一定，如何组织、安排和调配资源保证项目按期完成。(2) 资源不足时，如何协调内部资源和采取应急措施(加班、雇工、增加设备、改进施工工艺)保证项目按期完成。(3) 资源、时间和成本的整体调整和系统优化,资源的合理配置,表9-9,【解】（1）项目网络图及最早最迟开始时间见图923。项目完工期为40天。关键工序是A、D、E和G，非关键工序是B、C、F，总时差都等于9，也是工序B、C、F的全部机动时间。,B,8,D,7,C,10
25、,E,10,F,3,G,13,H,0,0,0,10,10,18,17,27,28,40,40,37,27,17,10,19,图9-23,27,从图9-24看出，如果非关键工序都按最早时间开始，第11天到第28天是用工高峰期，第19天到第27天为40人，按此计划施工需要40人,图9-24,将工序B按最早时间开始，工序C、F按最迟时间开始，调整后最多需要32人，见图9-25。,图9-25,（2）由图9-25，只有1天时间需要32人，对计划整体优化可以从以下几个方案考虑。 第一，对工序B或E采取应急措施，缩短工序时间1天，能够使总人数降到27人，由表9-9知，工序B一天的应急成本比工序E低，因此工序
26、B缩短1天，第17天完工，增加成本10万元。第二，如果项目完工期推迟1天完工的成本比工序B的应急成本低，可以考虑对关键工序E推迟一天开始，即第20天开始，项目完工期为41天。第三，从图9-25看出,人员并没有均衡利用,在某个时间段内就可以利用富裕的资源到关键工序，缩短关键工序的时间，而在用工高峰期时将缩短的关键工序时间用到其它工序上。第四，均衡利用资源，综合评价与审核。当资源、时间和成本可以相互转化和替代时，制定评价标准，确定多个目标的优先次序，是成本优先、工期优先还是资源优先，综合评价与审核，经过反复调整与优化，得到满意的计划方案后，作出项目施工决策。,本章内容,网络图时间参数的计算网络计划
27、的优化和实施管理图解评审法简介,图解评审法(graphical evaluation and review technique，GERT),4图解评审发简介,图解评审法解决问题的步骤为：(1) 进行系统分析，明确问题的目标，各工作间的关系，正确绘制GERT网络图。(2) 对工作工时及出现概率等参数进行认真测算与估计。如果工时是随机变量，需测辨其所服从的概率分布与密度函数，以及期望值和方差，作为计算的依据。(3) 对模型进行分析、计算，计算内容依系统目标决定。一般地说，不但要求解网络中所消耗的时间、费用和资源，而且还要求得网络中的流。(4) 对计算结果进行分析和评价，作出预测或决策指导或监控计划
28、的实施。,基本解法,解析法,模拟法,例4 生产一批零件，经过加工1完成后送检查1，检查1工作完成后，合格品转到加工2，不合格品转到返修工作进行修理加工，然后再送检查2，其中返修合格者转到加工2，不合格者报废。加工2完成后的产品转到检查3，其中合格品入库，不合格品报废。试求成批生产这种零件，每个成品平均需要的加工时间及成品率。图9-26描述了整个零件加工过程，表9-10给出了各工作完成概率、工时及各工作关系。,5,6,5,图9-26,表9-10,解析法,路线1：，实现的概率为：P1=10.7510.95=0.7125，所需要的时间为：Ti=4+1+10+1=16,成品率为：P1+P2=0.712
29、 5+0.166 25=0.878 75,每个成品零件所需平均加工时间为:,1/(P1+P2)*(P1*T1+P2*T2)=16.946(h),废品率为：1-（P1+P2）=0.12125,模拟法,1）每个零件经过的加工路线是由始点事项开始，每个工作以概率Pi转移到紧后工作，直到终点事项或。若Pi服从(0Pi1)的均匀分布，则每个零件加工路线可以在计算机上产生随机数来模拟。根据可能出现的两个(或若干个)紧后工作的概率值将0，1分为两个(或若干个)区间，产生的随机数落在哪个区间，就认为那个区间对应的工作被实现。,2) 不同的加工路线上，各工作所需时间若是服从某种分布的随机变量，其取值也可以通过抽取服从(0，1)均匀分布的随机数，用公式逆变或者逐段逼近的方法来得到。,3) 通过步骤(1)、步骤(2)对某个零件加工路线与所需工时的模拟可得到随机网络的一个确定的子网络。计算每个零件加工的时间，并记下每个零件的路径。,4) 完成N次模拟(加工数量为N的一批零件)后，可按下述公式求出每个成品零件的平均加工时间及成品率。,
