运筹学-网络图课件.ppt

1、第四章第九节 网络计划一一、画网络图的规则画网络图的规则前前 言言二二、实例实例三三、网络图的分类网络图的分类作 业 五-1第一节 网络图4.9 网络计划技术 网络计划技术的基本概念 网络图的绘制 网络图的时间参数计算 网络优化一、网络计划技术的基本概念 工程计划与甘特图 不易表现工程全貌不易表现工程全貌 不便于对各项工作的安排进行筹划和推敲不便于对各项工作的安排进行筹划和推敲 不能识别影响进度的关键工作不能识别影响进度的关键工作 不能反映一项工作不能按进度完成时对工程进不能反映一项工作不能按进度完成时对工程进度的影响度的影响 计划评审技术(PERT)与关键路线法(CPM)系统性和协调性系统性

2、和协调性 动态性和可控性动态性和可控性 科学性科学性甘特图 时间活动ABCDE九月五月 六月 七月八月一月 二月三月四月前甘特图的网络图二、网络图的绘制 网络图的构成 作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。一个基建项目网络图二、网络图的绘制 从开始节点到结束节点的一条路经叫做路线 一个网络图的有多条路线，每条路线有一个总时间 总时间最长的路线叫做关键路线，关键路线的总时间叫做工期 看下面的例子网络图的路线 以上网络图共有8条路线 可以计算出这8条路线的总时间，最长的是16天。关键路线是 当某些

3、工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH553网络图的画法 作业的串联 作业的并联网络图的画法 作业的交叉 作业的合并绘制网络图的基本原则 两事项间只能有一项作业改为绘制网络图的基本原则 网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号 网络图只能一个开始节点，一个终止节点 不能出现循环路线 尽量少交叉，采用暗桥；有层次性。使用暗桥网络图的绘制步骤 确定目标，做好准备工作 任务分解和分析 绘制网络图表4-1 调查项目的任务分解和分析作业代号 作业说明周期(

4、天)紧前作业A系统地提出问题4-B研究选点问题7 AC准备调研方案10 AD收集资料，安排工作8 BE挑选和训练调研人员12 B、CF准备有关表格7 CG实地调查5 D、E、FH分析调查数据，写调查报告4 G绘制作业图的方法 试探性绘制法 计算机辅助绘制法 流程图过渡绘制法试探性绘制法：试探试探性绘制法：修改流程图过渡绘制法：流程图流程图过渡绘制法：加事项流程图过渡绘制法：去方框流程图过渡绘制法：修改三、网络图时间参数计算 作业时间的确定 事项时间参数的计算 作业时间参数的计算 关键路线的寻找方法 按期完成计划的概率作业时间的确定 对具有标准的作业，采用单一时间估计法 对一般性作业，采用三点时

5、间估计法 最乐观时间：最乐观时间：a 最可能时间：最可能时间：m 最悲观时间：最悲观时间：b 计算时间期望值和方差作业时间计算方法6/)(64abbmaTe分布事项参数的计算 事项最早时间 事项最迟时间0)1()()(maxEijEiETTiTjTijijT)()()()(minnTnTTjTiTELijLiL图上计算法矩阵法计算事项时间TL0414 14 14 26 3135TE004407 101130814007140 12260531043501425368172536847作业时间参数的计算 作业开始最早时间 作业结束最早时间 作业开始最迟时间 作业结束最迟时间 总时差 单时差作业最

6、早时间作业最迟时间),(),(),()(),(jiTjiTjiTiTjiTESEFEES),(),(),()(),(jiTjiTjiTjTjiTLFLSLLF时差),(),(),()(),(),(),(),(jiTkjTjiTjTrjiTjiTjiTjiTREFESEFEijLSLFESLSij总时差单时差时差之间的关系表4-3 作业时间参数计算作业时间T(i,j)开始 结束开始 结束A4-04040B7 A4117143C10 A4144140D8 B111918267E12 B,C142614260F7 C142119265G5 D,E,F263126310H4 G313531350作业代

7、号最早时间最迟时间总时差紧前作业关键路线的确定方法 总时差为零的作业即是关键作业，关键作业构成关键路线 破圈法 也可采用最长路线法。按期完成计划的概率 每项作业的时间是一个随机变量，近似服从 分布，均质和标准差为 工期也是一个随机变量，它的期望值为各关键作业时间期望之和。6/)(64),(ijijijijijabbmajiT按期完成计划的概率 当作业数足够多时，工期近似服从正态分布),(2KTNT按期完成计划的概率 其中 按期完成的概率222664KKKPiiiPiiPiiiiKabbmaT)(21)(2/2KDTTzDTTdzeTTPKD图4-44 工期概率分析的例子三种时间估计期望值 标准

8、差 方差ambT2(1,2)12321/31/9(2,4)341151 1/31 7/9(4,5)561371 1/31 7/9(5,6)268611总和204 2/3作业计算按期完成概率 工期的期望值和标准差是 分别计算要求20天、21天和19天完成的概率942191691691206752KT323.0)46.0()19(677.0)46.0()21(5.0)0()20(TPTPTP计算概率下完工的工期 由于 所以 可根据要求的概率，查表得到z，在用上式计算TD，例如，要求完工概率为0.9的工期：由 得z=1.28，所以KDTTzzTTKD9.0)(z)(8.2216.228.120天zT

9、TKD四、网络优化 工期限定，资源需要平衡 资源有限，工期希望最短 工期缩短，总费用最小工期限定，资源需要平衡 工期不变，就是关键工作时间不能调整 资源不平衡将导致资源不足 利用时差，调整非关键路线上工作的开始时间，使资源实现平衡。一个例子各工作都按最早开始时间开始调整非关键工作的开始时间资源有限，要求工期最短 下图表示的项目只有10人工作第一次调整第二次调整工期缩短，总费用最少 一般情况下，若采取措施缩短工期，则间接费用将减少，直接费用将增加，总费用由一个最低点。直接成本的处理 按线性处理，作业的费用率为CNNCTTCCP图4-52 一个例子ij),(PTTNC解题思路 以正常时间进行网络分

10、析，求得关键路线 在关键路线上，寻找最小费率的工作，缩短其时间，使工期最多到次长路线的长度。缩短工期必须对所有关键路线进行，此时应选择费率总和最小的组合方案。第一步求关键路线作业(1,2)(2-3)(3-4)费率313工期=11天第二步选择(2,3)缩短工期工期=10天增加费用1可选方案IIIIII缩短的作业(1,2),(1,3)(2,3),(1,3)(3,4)总费用率3+1=41+1=23第三步按第I方案缩短工期工期=9天增加费用1+2=3再按方案III缩短周期可选方案III缩短的作业(1,2),(1,3)(2,4),(3,4)总费用率3+1=41+3=4工期=8天增加费用3+3=6第四步按

11、第I、II方案缩短4天工期=4天增加费用6+16=22调整(1,2)与(2,3)，并缩短(3,4)工期=3天增加费用22+5=27总合算费用，绘制直接费用图工期111098743增加直接费用0136102227总费用最小的优化 一般应考虑间接费用，工期缩短，总的间接费用减少 例如，上例中，间接费用率为：4.5/天，则因为最后一部直接费率5/天4.5/天，因此最后一步的工期不能缩短，工期应为4天，此时可节省费用3.5+1.5+4*0.5=7。例续例续(1,4)(3,5)(1,1)(3,3)(2,1)(4,2)(1,3)(2,5)(4,2)vsv1v2v3vtv4例续例续(1,4)(3,5)(1,1)(3,3)(2,1)(4,2)(1,3)(2,5)(4,2)vsv1v2v3vtv4作业 时间 紧前作业作业 时间 紧前作业 A 2 -F 5 D,E B 1 -G 3 F,C C 3 A H 6 D,E D 4 A I 0 G,H E 4 B 阅读 P273 -p278 P302 2,作 业 五-2