《运筹学胡运权第09章》由会员分享，可在线阅读，更多相关《运筹学胡运权第09章（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完
6、工后b和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 三种时间发生的概率
8、分别为1/6、4/6、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 t
9、ime for an 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）分布，则有,近似服从,即,概率型网络图的时间参数计算
12、,设给定一个时间X0，则工程完工时间不超过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。,概率型网络图的时间参数计
14、算,【练习】 （1）求工序的最早开始和最迟开始时间。 （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.17 20.25+1.78+2.764.79， =2.1886,（3）X072， (X0)/=(7269.17)/2.1886=1.293,（4）已知概率p0=0.98，由式(7.15)，查正态分布表有,要使项目完工的概率为
15、0.98，至少需要73.65天,本章内容,网络图 时间参数的计算 网络计划的优化和实施管理 图解评审法简介,3网络计划的优化和实施管理,网络计划中用关键线路控制工期，利用时差进行网络计划的优化。 网络计划的优化：通过利用时差，不断改善网络计划的初始方案，在满足既定的条件下，按某一衡量指标（如时间、成本、物资）来寻求最优方案。,一、 时间优化 二 、费用优化 三 、资源优化：,类型,时间优化,1、将串联工作调整为平行工作。 2、将串联工作调整为交叉工作。 3、相应地推迟非关键工作的开始时间。 4、相应地延长非关键线路中工作的工作时间。 5 、从计划外增加资源。 6、从计划外增加资源供应，以加快关键工作，缩短总工期。,总成本总应急成本总应急收益 总正常成本总应急增加成本 总应急收益,单位时间工序的应急增加成本(成本斜率) (应急成本正常成本) （正常时间应急时间）,费用优化, 计算正常作业条件下工程网络计划的工期、关键线路和总直接费、总间接费及总费用。 计算各项工作的成本费率。 在关键线路上，选择成本费率(或组合直接费率）最小并且不超过工程间接费率的工作作为被压缩对象。,步骤和方法,费用优化, 将被压缩对象压缩至最短，当被压缩对象为一组工作时，将该组工作压缩同一数值，并找出关键线路，如果被压缩对象变成了非关键工作，则需适当延长其持续时间，使其刚好恢复为关键工
