运筹学胡运权第09章课件.ppt

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、图网络图:由工序、事件及标有完成各道工序所需时间所构成的连通有向图。工作：工作：或称为工序、活动工序、活动，指任何消耗时间或资源的活动，如新产品设计中的初步设计、技术设计、工装制造等。根据需要，工序可以划分得粗一些，也可以划分得细一些。虚工作：虚工作：虚设的工作。用来表达相邻工作之间的衔接关系，不需要时间和资源，用 表示事件：事件：标志工作的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前面各顶作业（紧前工序）的结束，又标志着在它之后的各项作业（紧后工序）的开始。如机械造业中，只有完成铸锻件毛坯后才能开始机加工；各种零部件都完成后，才能进行总

5、装等。15a2圆圈和里面的数字代表各事件，写在箭线中间的数字5为完成本工作所需时间，即工作a:(1,2)，事项：1,2。紧前工序：工序：紧接某项工序的先行工序紧后工序：紧后工序：紧接某项工序的后续工序前道工序：前道工序：某工序之前的所有工序后续工序后续工序：某工序之后的所有工序1278(1)(1)在一张网络图中，一般只允许出现在一张网络图中，一般只允许出现一个起点节点和一个终点节点。一个起点节点和一个终点节点。7843561278图9-1有多个起点节点和多个终点节点的网络图(2)(2)网络图中不允许出现循环回路网络图中不允许出现循环回路2153467图9-2 有循环回路的网络图(3)(3)节点

6、之间不允许有两个或两个以上的工节点之间不允许有两个或两个以上的工作作21ab图9-3图9-3不符合该规则(4)(4)必须正确表示工作之间的前行后继关必须正确表示工作之间的前行后继关系系31245abcd图9-4不符合该规则图9-4(5)(5)虚工作的运用虚工作的运用31245abcd图9-4图9-4用添加虚工作的方法可以改为正确的图9-541256abcd3图9-5（1）任务分解5H安装设备J2G调集人员K3A需求分析C6A产品设计D2B、G筹备设备H8B、G筹备原材料I3F制定生产计划G2C、E制定成本计划F8D产品研制E1I、J、K准备开工投资L10/资金筹备B4/市场调查A时间（周）紧前

7、工作工作内容工作表9-1（2）绘制网络图312456791086A4DI8C3H2L1K2G3F2B10图9-685（3）节点编号 原则上说，只要不重复、不漏编，每根箭线的箭头节点编号大于箭尾节点的编号即可。但一般的编号方法是，网络图的第一个节点编号为1，其它节点编号按自然数从小到大依次连续编排，最后一个节点的编号就是网络图节点的个数。有时也采取不连续编号的方法以留出备用节点号。1.当工序a完工后b和c可以开工3.工序c在工序a完工后就可以开工，但工序d必须在a和b都完工后才能开工 2.当工序a和b完工后c和d可以开工4.事件i、j之间有多道工序时，添加虚工序abc(a)abcd(b)acbd

8、(c)(d)abcacbdacbd(e)(f)ee图图976.网络图只有一个发点（项目的开始点）一个收点（项目的结束点）。如图（e）所示，则应合成图（f）所示的一个始点及一个终点。5.用弧(i，j)表示一道工序，事件i是工序的开始，事件j是工序的完成，规定i j。见下图 G2520ABCDEFH405030205020表9-2工序明细表 20E、F、G试运转H820B专业工程D450B设备安装G730B屋面工程C320D地面工程F650A构件安装B225C装修工程E540基础工程A1时间(天)紧前工序工序名称代号序号时间(天)紧前工序工序名称代号序号【练习1】某项目由8道工序组成，工序明细表见

9、表9-2所示。分别用箭线法和节点法绘制该项目的项目网络图。FGABCDH4050302050252020E图9-8【练习2】根据某项目作业明细表93的资料，绘制项目网络图 25gl12a,bf20d,h,gk16ce17ij5cd8d,hi13ac12e,fh9 b10a,bg6a工序时间(天)紧前工序工序工序时间(天)紧前工序工序表93【解】计划网络图如下：工序紧前工序工序时间(天)工序紧前工序工序时间(天)a 6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg25a,61b,9c,13d,5e,16f,12h,12g,10i,8k,20

10、j,17l,25图99箭线网络图123547108911|网络图|时间参数的计算|网络计划的优化和实施管理|图解评审法简介一、工序时间的估计三点估计法三点估计法是事先估计出工序的三种可能完成时间，其期望值就作为工序时间的估计值。三种时间是：(1)完成工序（i，j）的最短时间，称为乐观时间，记为aij(2)完成工序（i，j）的正常时间，称为最可能时间,记为mij(3)完成工序（i，j）的最长时间，称为悲观时间，记为bij三种时间发生的概率分别为1/6、4/6、1/6，则工序（i，j）完成时间的期望值和方差为：64)(ijijijijijbmatEt226)(ijijijijabtD二、事项时间参

11、数（1）事项的最早时间）事项的最早时间（2）事项的最迟时间）事项的最迟时间事项的最早时间用tE(j)表示tE(1)=0tE(j)=maxtE(i)+t(i,j)其中tE(i)表示与事项j相邻的各紧前事项的最早时间事项的最迟时间用tL(j)表示tL(n)=总工期tL(i)=mintL(j)-t(i,j)其中tl(j)表示与事项i相邻的各紧后事项的最迟时间（1）工作(i,j)的最早开始时间（Earliest start time for an activity）tES(i,j)。是指紧前工序的最早可能完工时间的最大值，计算公式为 t(,)max(,)(,)ESESki jtk it k i（2）工

12、序(i,j)的最早完工时间（Earliest finish time for an activity）tEF(i,j)。计算公式为 t(,)t(,)(,)EFESi ji jt i j三、工作的时间参数(4)工序(i,j)的最迟必须结束时间(Latest finish time for an activity)tLF(i,j)。计算公式为 t(,)(,)(,)LFLSi jti jt i j(3)工序(i,j)的最迟必须开始时间（latest start time for an activity）tLS(i,j)。是指为了不影响紧后工序如期开工，工序最迟必须开工的时间，计算公式为(,)min(

13、,)(,)LSLSkti jtj kt i j(6)工序的单时差或自由时间(Free for an activity)F(i，j)。在不影响紧后工序的最早开始时间的条件下，工序(i,j)的开始时间可以推迟的时间。计算公式为(,)(,)(,)ESEFF i jtj kti j(5)工序(i,j)的总时差或松弛时间(Slack for an activity)S(i,j)。是工序(i,j)的最迟开始(结束)时间与最早开始(结束)时间之差，计算公式为(,)(,)(,)(,)(,)(,)(,)(,)LSESLFEFLFESS i jti jti jti jti jti jti jt i j工作总时差和

14、单时差的区别与联系可以通过图9-14来说明。总时差为零的工作链为关键路线312456791086483212321085图9-102526232323232020181810100044323231311.先计算事项的时间参数312456791086483212321085图9-112526232323232020181810100044323231312.工作时间参数的计算0001341510104423232329202018183131232425262323312456791086483212321085图9-12003.找出关键路线 0001341510104423232329202

15、018183131232425262323工序工序 (i,j)tijTES(i,j)TEF(i,j)TLS(i,j)TLF(i,j)S(i,j)F(i,j)关键工序关键工序a(1,2)4040400是是b(1,7)1001013231313c(2,3)641041000是是d(2,4)34715181111e(3,4)81018101800是是f(4,5)21820182000是是g(5,6)32023202300是是h(6,7)02323232300是是i(6,9)22325293166j(7,8)22325242610k(7,9)82331233100是是l(8,10)5253026311

16、1l(9,10)13132313200是是表9-4工序时间是随机变量时，项目的完工期也是随机变量设Xk为关键工序 k 所需时间的随机变量，则 Xk 相互独立，工序的期望时间及方差为226)(64)()(kkkkkkkkkabXDbmaktXE工程完工期的期望值及方差为nkknnkknXE1221)(设关键工序数为n，工程的完工期是一随机变量nkkXX1nnnXZ令则由李雅普诺夫中心极限定理知(式中n为关键工序数）dteXZPXFXtnnn2221lim)(lim即当n很大时Zn近似服从N（0，1）分布，则有nnnKZXX近似服从），（2nnN），（2nnNX即设给定一个时间X0，则工程完工时间

17、不超过X0的概率为0),(20XnndtNXXpNNXXdtNnn00)1,0(要使工程完工的概率为p0，至少需要多少时间X0XpdtNXXp00)1,0(nnXX0查正态分布表求出X，由得nnXX0例2已知某一计划（见图9-13）中各件工作的a,m,b值(单位为月)，见表9-5的第2、3、4列。要求：(1)每件工作的平均工时t及均方差；(2)画出网络图，确定关键路线；(3)在25个月前完工的概率17435627-8-97-9-114-4-43-4-810-13-196-9-125-7-83-4-64-5-77-8-10图9-1311978437546431913101087444129687

18、594.55.1674.16713.58.167496.8338987tbma工作0.6670.8330.50.51.50.5040.50.33313122634353645565767表9-5解：1.利用公式计算t和0.83315.83315020.33320.3330.16615.166150.16610.99910.83306.8336.8330.1666.9996.8330.1666.9996.8333.33311.33380003.3333.3330RtLStES工作131226343536455657672.按t值计算出各工作的最早开始时间和最迟开始时间，总时差R；如表9-6表9-

19、6787.7833.05.15.02222762632312，3.确定关键工作为（1,3),(3,6),(6,7)%98.53099.0)1,0(25P787.1833.34-25）（dtNX即此计划在25个月前完成概率为0.5398。工序工序紧前紧前工序工序工序的三种时间工序的三种时间工工序序紧前紧前工序工序工序的三种时间工序的三种时间ambamba679fc182426b5810ge,303542c111214hd,202630da,b,c151719if141722ea91012jf283438【练习】（1）求工序的最早开始和最迟开始时间。（2）求工程完工期的期望值及其概率。（3）要求完

20、工的概率为0.95,至少需要多少天。表9-7a,6b,9d,5e,16f,12h,12g,10i,8k,20j,17l,25c,13123547109118图9-141图图9-15【解】(1)工序的最早开始和最迟开始时间见图9-15a,7.17b,7.83c,12.17d,17e,10.17f,23.33h,25.67g,35.33i,17.33j,33.6700007.177.1712.1712.1712.1735.529.1717.3435.569.1769.1769.1733.8443.551.8435.569.1712.1726.523.6716.518.670026.526.5工序工

21、序abcdefghij期望值期望值 7.177.8312.171710.17 23.33 35.33 25.67 17.33 33.67方差方差0.250.690.250.440.251.7842.781.782.78(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 9014.0)293.1(720XXp（4）已知概率p0=0.98，由式(7.15)，查正态分布表有0)()0

22、.98,2.05p XXZZ 02.05 2.188669.1773.65()XZ天要使项目完工的概率为0.98，至少需要73.65天|网络图|时间参数的计算|网络计划的优化和实施管理|图解评审法简介|网络计划中用关键线路控制工期，利用时差进行网络计划的优化。|网络计划的优化：通过利用时差，不断改善网络计划的初始方案，在满足既定的条件下，按某一衡量指标（如时间、成本、物资）来寻求最优方案。一、时间优化 二、费用优化 三、资源优化：类型1、将串联工作调整为平行工作。2、将串联工作调整为交叉工作。3、相应地推迟非关键工作的开始时间。4、相应地延长非关键线路中工作的工作时间。5、从计划外增加资源。6

23、、从计划外增加资源供应，以加快关键工作，缩短总工期。正常时间（正常时间（Normal Time）正常成本正常成本(Normal Cost)应急时间应急时间(Crash Time)应急成本应急成本(Crash Cost)总成本总应急成本总应急收益总成本总应急成本总应急收益 总正常成本总应急增加成本总正常成本总应急增加成本 总应急收益总应急收益单位时间工序的应急增加成本单位时间工序的应急增加成本(成本斜率成本斜率)(应急成本正常成本应急成本正常成本)（正常时间应急时间）（正常时间应急时间）计算正常作业条件下工程网络计划的工期、关键线路和总直接费、总间接费及总费用。计算各项工作的成本费率。在关键线路

24、上，选择成本费率(或组合直接费率）最小并且不超过工程间接费率的工作作为被压缩对象。将被压缩对象压缩至最短，当被压缩对象为一组工作时，将该组工作压缩同一数值，并找出关键线路，如果被压缩对象变成了非关键工作，则需适当延长其持续时间，使其刚好恢复为关键工作为止。重新计算和确定网络计划的工期、关键线路和总直接费、总间接费、总费用。重复上述第三至第五步骤，直至找不到成本费率或组合成本费率不超过工程间接费率的压缩对象为止。此时即求出总费用最低的最优工期。绘制出优化后的网络计划。在每项工作上注明优化的持续时间和相应的直接费用。图9-16【例3】项目工序的正常时间、应急时间及对应的费用见表9-8。（1）绘制项

25、目网络图，按正常时间计算完成项目的总成本和工期。（2）按应急时间计算完成项目的总成本和工期。（3）按应急时间的项目完工期，调整计划使总成本最低。（4）已知项目缩短1天额外获得奖金5万元，减少间接费用1万元，求总成本最低的项目完工期，也称为最低成本日程。工序工序紧前工紧前工序序时间时间(天天)成本成本(万元万元)时间的最大时间的最大缩量缩量(天天)应急增加成本应急增加成本(万万元元/天天)正常正常应急应急正常正常应急应急A1915528047BA21196290214CB2422243023DB25233860211EB2624182624FC25238810227GD,E2823193954H

26、F232330300IG,H27264055115JI1814172141KI3530253552LJ28253060310MK3026455743NL2520182852总成本总成本506713【解】(1)项目网络图及时间参数见图9-17。项目的完工期为210天，将表9-8正常成本一列相加得到总成本为506万元 C,24H,23B,21E,26D,25J,18G,28A,19F,25I,27L,2812K,35M,3013N,2511O,000194040406664668911213921001391571851742101851571801451391128489644084595819

27、0图图9-17C,22H,23B,19E,24D,23J,14G,23A,15F,23I,26L,2512K,30M,2613N,2011O,0001534343458565879102128187012814216715818716714216113112810279795634795655150图9-18（2）项目网络图不变，时间参数见图9-18，完工期187天，将表9-8应急成本一列相加得到总成本为713万元(3)图9-18中，非关键工序是D、E、G、K和M，可以看出，将工序D、E、G按正常时间施工时，最早开始和最迟开始时间不相等，说明按正常时间施工不影响项目的完工期（187天），见图9

28、-19(a)。工序K和M按正常时间共要缩短时间6天，见图9-19(b)。E,26D,25G,28O,0343460607979545312K,35M,3013J,14L,2513N,2011应急时间路长：应急时间路长：59正常时间路长：正常时间路长：6512K,30M,2613应急时间路长：应急时间路长：56图图9-19(a)(b)则最优的决策方案是：关键工序A、B、C、F、H、I、J、L、N全部按应急时间施工，总成本等于各工序应急成本之和；工序D、E、G按正常时间施工，成本等于各工序正常成本之和；工序K缩短5天工序M缩短1天，成本等于正常成本加应急时间增加的成本。按项目完工期187天施工的最

29、小成本是654万元，成本分析见表9-8。调整后有两条关键路线，见图9-20C,22H,23B,19E,26D,25J,14G,23A,15F,23I,26L,2512K,30M,2913N,2011O,0001534343460566079102128187012814216715818716714215812812810279795634795653150图图9-20(4)考虑缩短关键工序的时间，选择一天应急增加的成本小于等于6的关键工序采取应急措施来缩短时间，这样的工序有C、J、N，工序C缩短2天，工序J缩短4天，工序N缩短2天。对图78进行第一次调整得到图9-21。得到两条关键路线，工序

30、K和M变为关键工序，项目完工期为202天，缩短了8天。总成本变动额为:2341228634（万元）C,22H,23B,21E,26D,25J,14G,28A,19F,25I,27L,2812K,35M,3013N,2311O,0001940404066626687110137202013715117917220217915117213713711082876240825756190图9-21检查图9-21虚线围起来的部分。要缩短工期必须两条关键路线同时缩短时间，上面一条路线工序N还能缩短3天，因此下面一条路线只对工序K缩短3天，对图9-21调整得到图9-22。项目的完工期为199天，又缩短了3

31、天，总成本变动额为 3232366（万元）C,22H,23B,21E,26D,25J,14G,28A,19F,25I,27L,2812K,32M,3013N,2011O,0001940404066626687110137199013715117916919917915116913713711082876240825756190图9-22继续检查发现，缩短任何关键工序都不能降低成本，则总成本最低的项目工期是199天，总成本为 506-34-6466（万元）(1)资源一定，如何组织、安排和调配资源保证项目按期完成。(2)资源不足时，如何协调内部资源和采取应急措施(加班、雇工、增加设备、改进施工工艺

32、)保证项目按期完成。(3)资源、时间和成本的整体调整和系统优化【例7.4】项目各工序的时间和资源如表78所示（1）绘制项目网络图，按正常时间计算项目完工期，按期完工最多需要多少人。（2）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。工序紧前工序每天需要资源(人)时间(天)成本（万元）时间的最大缩量(天)应急增加成本(万元/天)正常 应急 正常应急A51083070220BA1286130150210CB20107100130310DA12764050110ED201085080215FC,EE103360600G7139708644表9-9【解】（1）项

33、目网络图及最早最迟开始时间见图923。项目完工期为40天。关键工序是A、D、E和G，非关键工序是B、C、F，总时差都等于9，也是工序B、C、F的全部机动时间。B,8D,7C,10E,10F,3G,13H,00010101817272840403727171019A,1000图9-2327从图9-24看出，如果非关键工序都按最早时间开始，第11天到第28天是用工高峰期，第19天到第27天为40人，按此计划施工需要40人 图图9-24将工序B按最早时间开始，工序C、F按最迟时间开始，调整后最多需要32人，见图9-25。图图9-25（2）由图9-25，只有1天时间需要32人，对计划整体优化可以从以下

34、几个方案考虑。第一，对工序B或E采取应急措施，缩短工序时间1天，能够使总人数降到27人，由表9-9知，工序B一天的应急成本比工序E低，因此工序B缩短1天，第17天完工，增加成本10万元。第二，如果项目完工期推迟1天完工的成本比工序B的应急成本低，可以考虑对关键工序E推迟一天开始，即第20天开始，项目完工期为41天。第三，从图9-25看出,人员并没有均衡利用,在某个时间段内就可以利用富裕的资源到关键工序，缩短关键工序的时间，而在用工高峰期时将缩短的关键工序时间用到其它工序上。第四，均衡利用资源，综合评价与审核。当资源、时间和成本可以相互转化和替代时，制定评价标准，确定多个目标的优先次序，是成本优

35、先、工期优先还是资源优先，综合评价与审核，经过反复调整与优化，得到满意的计划方案后，作出项目施工决策。|网络图|时间参数的计算|网络计划的优化和实施管理|图解评审法简介图解评审法(graphical evaluation and review technique，GERT)图解评审法解决问题的步骤为：(1)进行系统分析，明确问题的目标，各工作间的关系，正确绘制GERT网络图。(2)对工作工时及出现概率等参数进行认真测算与估计。如果工时是随机变量，需测辨其所服从的概率分布与密度函数，以及期望值和方差，作为计算的依据。(3)对模型进行分析、计算，计算内容依系统目标决定。一般地说，不但要求解网络中所

36、消耗的时间、费用和资源，而且还要求得网络中的流。(4)对计算结果进行分析和评价，作出预测或决策指导或监控计划的实施。基本解法解析法模拟法例4 生产一批零件，经过加工1完成后送检查1，检查1工作完成后，合格品转到加工2，不合格品转到返修工作进行修理加工，然后再送检查2，其中返修合格者转到加工2，不合格者报废。加工2完成后的产品转到检查3，其中合格品入库，不合格品报废。试求成批生产这种零件，每个成品平均需要的加工时间及成品率。图9-26描述了整个零件加工过程，表9-10给出了各工作完成概率、工时及各工作关系。565(1,3)返修4检查1(0.25,e1)(0.7,e3)检查27检查3(0.05,1

37、)成品废品(0.3,e4)检查22（0.75,e2）检查11（1,4）加工1（1,10）加工22（0.95,1）检查3835图9-26表9-10|解析法序号i路线实现概率(Pi)所需时间(Ti)10.71251620.166252130.03751640.008752150.07510路线1：，实现的概率为：P1=10.7510.95=0.7125，所需要的时间为：Ti=4+1+10+1=16成品率为：P1+P2=0.712 5+0.166 25=0.878 75每个成品零件所需平均加工时间为:1/(P1+P2)*(P1*T1+P2*T2)=16.946(h)废品率为：1-（P1+P2）=0.

38、12125|模拟法1）每个零件经过的加工路线是由始点事项开始，每个工作以概率Pi转移到紧后工作，直到终点事项或。若Pi服从(0Pi1)的均匀分布，则每个零件加工路线可以在计算机上产生随机数来模拟。根据可能出现的两个(或若干个)紧后工作的概率值将0，1分为两个(或若干个)区间，产生的随机数落在哪个区间，就认为那个区间对应的工作被实现。2)不同的加工路线上，各工作所需时间若是服从某种分布的随机变量，其取值也可以通过抽取服从(0，1)均匀分布的随机数，用公式逆变或者逐段逼近的方法来得到。3)通过步骤(1)、步骤(2)对某个零件加工路线与所需工时的模拟可得到随机网络的一个确定的子网络。计算每个零件加工的时间，并记下每个零件的路径。4)完成N次模拟(加工数量为N的一批零件)后，可按下述公式求出每个成品零件的平均加工时间及成品率。表示零件个数个废品零件加工时间表示第个成本零件加工时间表示第式中：k(%)11jtitNkPkttTiiikNjjkiic