运筹学课件――7 网络计划技术

运筹学7讲课教师：XXXLOGO第七章网络计划技术7.1PERT网络图7.2PERT网络参数计算7.3PERT网络优化7.4LOGO7.1PERT网络图一、网络计划技术的基本概念工程计划与甘特图–不易表现工程全貌–不便于对各项工作的安排进行筹划和推敲–不能识别影响进度的关键工作–不能反映一项工作不能按进度完成时对工程进度的影响计划评审技术(PERT)与关键路线法(CPM)–系统性和协调性–动态性和可控性–科学性LOGO甘特图时间活动ABCDE九月五月六月七月八月一月二月三月四月LOGO上述甘特图的网络图1435CDBEA262232LOGO二、网络图的绘制1.网络图的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。工作名称时间12D0ijLOGO一个基建项目的网络图1324装配厂房建设装配设计制造设计结束制造开始制造结束厂房装配开始始节点终节点LOGO2.路线、关键路线、工程工期从开始节点到结束节点的一条路经叫做路线一个网络图的有多条路线，每条路线有一个总时间总时间最长的路线叫做关键路线，关键路线的总时间叫做工期LOGO网络图的路线123456A1B5C3D2E6H3F5G5LOGO以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH553LOGO3.网络图的画法作业的串联作业的并联123456ABCDELOGO作业的交叉123456781a2a3a1b2b3bLOGO123456ABCDEFG1256AXG作业的合并LOGO4.绘制网络图的基本原则两事项间只能有一项作业25ABC2345ABC改为LOGO网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号网络图只能一个开始节点，一个终止节点不能出现循环路线尽量少交叉，采用暗桥；有层次性。LOGO1243ABCD1243ABCD5LOGO1234使用暗桥LOGO5.网络图的绘制步骤确定目标，做好准备工作任务分解和分析绘制网络图LOGO表7-1调查项目的任务分解和分析作业代号作业说明周期(天)紧前作业A系统地提出问题4-B研究选点问题7AC准备调研方案10AD收集资料，安排工作8BE挑选和训练调研人员12B、CF准备有关表格7CG实地调查5D、E、FH分析调查数据，写调查报告4GLOGO试探性绘制法：试探123456ABCDEHFG78910LOGO试探性绘制法：修改12345ABCDEHFG89104107812754LOGO7.2PERT网络时间参数计算作业时间的确定事项时间参数的计算作业时间参数的计算关键路线的寻找方法按期完成计划的概率LOGO一、作业时间的确定对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间估计法–最乐观时间：a–最可能时间：m–最悲观时间：b计算时间期望值和方差LOGO作业时间计算方法amb6/)(64abbmate分布LOGO二、事项参数的计算事项最早时间事项最迟时间0)1(])([)(maxEijEiETtiTjTijijt)()(])([)(minnTnTtjTiTELijLiLLOGO12345ABCDEHFG891041078127540411141426313501441414263135图上计算法LOGO矩阵法计算事项时间表7-2TL04141414263135TE0[0]44[0]71011[3]0814[0]0714[0]1226[0]531[0]435[0]1425368172536847LOGO三、作业时间参数的计算作业最早开始时间作业最早结束时间作业最迟开始时间作业最迟结束时间作业总时差作业单时差LOGO作业最早开始和结束时间作业最迟开始和结束时间),(),(),()(),(jitjiTjiTiTjiTESEFEES),(),(),()(),(jitjiTjiTjTjiTLFLSLLFLOGO时差),(),(),()(),(),(),(),(jiTkjTjiTjTrjiTjiTjiTjiTREFESEFEijLSLFESLSij总时差单时差LOGO时差之间的关系作业i-j作业i-jijTijrijR)(iTTEESEFT)(jTEijR)(iTELST)(jTE)(jTTLLF)(jTTLLFLOGO表7-3作业时间参数表上计算法作业时间t(i,j)开始结束开始结束A4-04040B7A4117143C10A4144140D8B111918267E12B,C142614260F7C142119265G5D,E,F263126310H4G313531350作业代号最早时间最迟时间总时差紧前作业LOGO四、关键路线的确定方法总时差为零的作业即是关键作业，全部关键作业构成关键路线破圈法也可采用最长路线法。12346570.2(2)(1)8311.5(3)2.556078(4)(5)LOGO五、按期完成计划的概率每项作业的时间是一个随机变量，近似服从分布，均质和标准差为工程工期也是一个随机变量，它的期望值为各关键作业时间期望之和。6/)(64),(ijijijijijabbmajitLOGO按期完成计划的概率当作业数足够多时，工期近似服从正态分布KT),(~2KTNTLOGO按期完成计划的概率其中按期完成的概率222664KKKPiiiPiiPiiiiKabbmaT)(21)(2/2KDTTzDTTdzeTTPKDLOGO图7-1工期概率分析的例子12456ABCD(1,2,3)(3,4,1)(5,6,13)(2,6,8)三种时间估计期望值标准差方差ambTσσ2(1,2)12321/31/9(2,4)3411511/317/9(4,5)5613711/317/9(5,6)268611总和2042/3作业LOGO计算按期完成概率工期的期望值和标准差是分别计算要求20天、21天和19天完成的概率942191691691206752KT323.0)46.0()19(677.0)46.0()21(5.0)0()20(TPTPTPLOGO计算概率下完工的工期由于所以可根据要求的概率，查表得到z，在用上式计算TD，例如，要求完工概率为0.9的工期：由得z=1.28，所以KDTTzzTTKD9.0)(z)(8.2216.228.120天zTTKDLOGO7.3网络优化工期限定，资源需要平衡资源有限，工期希望最短工期缩短，总费用最小LOGO一、工期限定，资源需要平衡工期不变，就是关键工作时间不能调整资源不平衡将导致资源不足利用时差，调整非关键路线上工作的开始时间，使资源实现平衡。LOGO例12354602(6)CD2(4)F2(7)24B2(3)2E3(8)G3(2)7H4(1)A4(9)110244711LOGO各工作都按最早开始时间开始日日人数102012345678910111234567891011123564H(1)G(2)A(9)E(8)B(3)F(7)D(4)C(6)(22)(24)(10)(2)(1)LOGO调整非关键作业的开始时间日日人数1012345678910111234567891011123564H(1)G(2)A(9)E(8)B(3)F(7)D(4)C(6)(10)LOGO二、资源有限，要求工期最短下图表示的项目只有10人工作日日人数10201234512345123584H(8)G(1)A(4)E(6)B(2)F(7)D(5)(18)(10)(8)(7)67C(3)LOGO第一次调整日日人数101234512345123584H(8)G(1)A(4)E(6)B(2)F(7)D(5)(8)(10)(8)(7)67C(3)66LOGO第二次调整日日人数101234512345123584H(8)G(1)A(4)E(6)B(2)F(7)D(5)(10)(9)(7)67C(3)66LOGO三、工期缩短，总费用最少一般情况下，若采取措施缩短工期，则间接费用将减少，直接费用将增加，目标是求总费用最低的工程工期。C*KTT总费用间接费用直接费用LOGO直接成本的处理按线性处理，作业的费用率为时间t费用CTNTNCCCCNNCTTCCPLOGO例图4-21243(1,3,3)(2,5,1)(2,4,1)(0,2,1)(1,6,3)ij),,(PTTNCLOGO解题思路以正常时间进行网络分析，求得关键路线在关键路线上，寻找最小费率的工作，缩短其时间，使工期最多到次长路线的长度。缩短工期必须对所有关键路线进行，此时应选择费率总和最小的组合方案。LOGO第一步求正常关键路线1243(1,3,3)(2,5,1)(2,4,1)(0,2,1)(1,6,3)0351103511作业(1,2)(2-3)(3-4)费率313工期=11天LOGO第二步选择(2,3)缩短工期1243(1,3,3)(2,5,1)(2,4,1)(0,1,1)(1,6,3)工期=10天增加费用1可选方案IIIIII缩短的作业(1,2),(1,3)(2,3),(1,3)(3,4)总费用率3+1=41+1=23LOGO第三步按第Ⅱ方案缩短工期1243(1,3,3)(2,5,1)(2,3,1)(0,0,1)(1,6,3)工期=9天增加费用1+2=3LOGO第四步再按方案Ⅲ缩短工期1243(1,3,3)(2,5,1)(2,3,1)(0,0,1)(1,5,3)可选方案III缩短的作业(1,2),(1,3)(2,4),(3,4)总费用率3+1=41+3=4工期=8天增加费用3+3=6LOGO第五步按第I、II方案共缩短4天1243(1,2,3)(2,2,1)(2,2,1)(0,0,1)(1,2,3)工期=4天增加费用6+16=22LOGO第六步调整(1,2)与(2,3)，并缩短(3,4)1243(1,1,3)(2,2,1)(2,2,1)(0,1,1)(1,1,3)工期=3天增加费用22+5=27LOGO第七步绘制直接费用变化图直接费用CKT工期111098743增加直接费用0136102227LOGO第八步确定总费用最小的优化方案一般应考虑间接费用，工期缩短，总的间接费用减少例如，上例中，间接费用率为：4.5/天，则因为最后一步直接费率5/天4.5/天，因此最后一步的工期不能缩短，工期应为4天，此时可节省费用7x4.5-22=9.5(万元)。LOGO习题P152，7.2;7.3(图7.13b)