运筹学 网络图

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

2、D,B,E,A,2,6,2,2,3,2,二、网络图的绘制,网络图的构成,作业（工作、工序、活动），箭头表示,箭头之上表示工作名称，之下表示工作,时间。可有虚工作,事项，节点表示，表示某个工作的结束,和另一工作的开始,工作名称,时间,1,2,D,0,i,j,一个基建项目网络图,1,3,2,4,装配厂房,建设,装配,设,计,制,造,设计结束,制造开始,制造结束,厂房装配开始,始节点,终节点,二、网络图的绘制,从开始节点到结束节点的一条路经叫做路线,一个网络图的有多条路线，每条路线有一个,总时间,总时间最长的路线叫做关键路线，关键路线,的总时间叫做工期,看下面的例子,网络图的路线,1,2,3,4,5

3、,6,A,1,B,5,C,3,D,2,E,6,H,3,F,5,G,5,以上网络图共有,8,条路线,可以计算出这,8,条路线的总时间，最长的是,16,天,关键路线是,当某些工作的时间调整后，可能引起关键路线的变,化和工期的变化。例如将工作,E,的时间缩短为,4,天,则工期缩短为,13,天，关键路线将变为,1,3,4,6,B,E,G,5,6,5,1,3,5,6,B,F,H,5,5,3,网络图的画法,作业的串联,作业的并联,1,2,3,4,5,6,A,B,C,D,E,网络图的画法,作业的交叉,作业的合并,1,2,3,4,5,6,7,8,1,a,2,a,3,a,1,b,2,b,3,b,1,2,3,4,

4、5,6,A,B,C,D,E,F,G,1,2,5,6,A,X,G,绘制网络图的基本原则,两事项间只能有一项作业,2,5,A,B,C,2,3,4,5,A,B,C,改为,绘制网络图的基本原则,网络图应从左向右延伸，编号应从小到大，且不,重复。箭头事项编号大于箭尾事项编号,网络图只能一个开始节点，一个终止节点,不能出现循环路线,尽量少交叉，采用暗桥；有层次性,1,2,4,3,A,B,C,D,1,2,4,3,A,B,C,D,5,1,2,3,4,使用暗桥,网络图的绘制步骤,确定目标，做好准备工作,任务分解和分析,绘制网络图,表,4-1,调查项目的任务分解和分析,作业代号,作业说明,周期,天,紧前作业,A,

5、系统地提出问题,4,B,研究选点问题,7,A,C,准备调研方案,10,A,D,收集资料，安排工作,8,B,E,挑选和训练调研人员,12,B,C,F,准备有关表格,7,C,G,实地调查,5,D,E,F,H,分析调查数据，写调查报告,4,G,绘制作业图的方法,试探性绘制法,计算机辅助绘制法,流程图过渡绘制法,试探性绘制法：试探,1,2,3,4,5,6,A,B,C,D,E,H,F,G,7,8,9,10,试探性绘制法：修改,1,2,3,4,5,A,B,C,D,E,H,F,G,8,9,10,4,10,7,8,12,7,5,4,流程图过渡绘制法：流程图,A,C,B,E,F,D,G,H,流程图过渡绘制法：加

6、事项,A,C,B,E,F,D,G,H,流程图过渡绘制法：去方框,A,C,B,E,F,D,G,H,1,2,3,4,6,9,12,5,8,7,10,11,13,14,15,16,流程图过渡绘制法：修改,A,C,B,E,F,D,G,H,1,4,6,5,8,7,13,15,16,三、网络图时间参数计算,作业时间的确定,事项时间参数的计算,作业时间参数的计算,关键路线的寻找方法,按期完成计划的概率,作业时间的确定,对具有标准的作业，采用单一时间估计法,对一般性作业，采用三点时间估计法,最乐观时间,a,最可能时间,m,最悲观时间,b,计算时间期望值和方差,作业时间计算方法,a,m,b,6,6,4,a,b,

7、b,m,a,T,e,分布,事项参数的计算,事项最早时间,事项最迟时间,0,1,max,E,ij,E,i,E,T,T,i,T,j,T,i,j,ij,T,min,n,T,n,T,T,j,T,i,T,E,L,ij,L,i,L,1,2,3,4,5,A,B,C,D,E,H,F,G,8,9,10,4,10,7,8,12,7,5,4,0,4,11,14,14,26,31,35,0,14,4,14,14,26,31,35,图上计算法,矩阵法计算事项时间,T,L,0,4,14,14,14,26,31,35,T,E,0,0,4,4,0,7,10,11,3,0,8,14,0,0,7,14,0,12,26,0,5,3

8、1,0,4,35,0,1,4,2,5,3,6,8,1,7,2,5,3,6,8,4,7,作业时间参数的计算,作业开始最早时间,作业结束最早时间,作业开始最迟时间,作业结束最迟时间,总时差,单时差,作业最早时间,作业最迟时间,j,i,T,j,i,T,j,i,T,i,T,j,i,T,ES,EF,E,ES,j,i,T,j,i,T,j,i,T,j,T,j,i,T,LF,LS,L,LF,时差,j,i,T,k,j,T,j,i,T,j,T,r,j,i,T,j,i,T,j,i,T,j,i,T,R,EF,ES,EF,E,ij,LS,LF,ES,LS,ij,总时差,单时差,时差之间的关系,作业,i-j,作业,i-j

9、,ij,T,ij,r,ij,R,i,T,T,E,ES,EF,T,j,T,E,ij,R,i,T,E,LS,T,j,T,E,j,T,T,L,LF,j,T,T,L,LF,表,4-3,作业时间参数计算,作业时间,T(i,j,开始,结束,开始,结束,A,4,0,4,0,4,0,B,7,A,4,11,7,14,3,C,10,A,4,14,4,14,0,D,8,B,11,19,18,26,7,E,12,B,C,14,26,14,26,0,F,7,C,14,21,19,26,5,G,5,D,E,F,26,31,26,31,0,H,4,G,31,35,31,35,0,作业,代号,最早时间,最迟时间,总时差,紧前

10、作业,关键路线的确定方法,总时差为零的作业即是关键作业，关键,作业构成关键路线,破圈法,也可采用最长路线法,1,2,3,4,6,5,7,0.2,2,1,8,3,1,1.5,3,2,5,5,6,0,7,8,4,5,按期完成计划的概率,每项作业的时间是一个随机变量，近似服从,分,布，均质和标准差为,工期也是一个随机变量，它的期望值为各关键作,业时间期望之和,6,6,4,ij,ij,ij,ij,ij,a,b,b,m,a,j,i,T,按期完成计划的概率,当作业数足够多时，工期近似服从正态,分布,K,T,2,K,T,N,T,按期完成计划的概率,其中,按期完成的概率,2,2,2,6,6,4,K,K,K,P

11、,i,i,i,P,i,i,P,i,i,i,i,K,a,b,b,m,a,T,2,1,2,2,K,D,T,T,z,D,T,T,dz,e,T,T,P,K,D,图,4-44,工期概率分析的例子,1,2,4,5,6,A,B,C,D,1,2,3,3,4,1,5,6,13,2,6,8,三种时间估计,期望值,标准差,方差,a,m,b,T,2,1,2,1,2,3,2,1/3,1/9,2,4,3,4,11,5,1 1/3,1 7/9,4,5,5,6,13,7,1 1/3,1 7/9,5,6,2,6,8,6,1,1,总和,20,4 2/3,作业,计算按期完成概率,工期的期望值和标准差是,分别计算要求,20,天,21

12、,天和,19,天完成的概率,9,42,1,9,16,9,16,9,1,20,6,7,5,2,K,T,323,0,46,0,19,677,0,46,0,21,5,0,0,20,T,P,T,P,T,P,计算概率下完工的工期,由于,所以,可根据要求的概率，查表得到,z,在用上式计算,T,D,例如，要求完工概率为,0.9,的工期：由,得,z=1.28,所以,K,D,T,T,z,z,T,T,K,D,9,0,z,8,22,16,2,28,1,20,天,z,T,T,K,D,四、网络优化,工期限定，资源需要平衡,资源有限，工期希望最短,工期缩短，总费用最小,工期限定，资源需要平衡,工期不变，就是关键工作时间不

13、能调整,资源不平衡将导致资源不足,利用时差，调整非关键路线上工作的开,始时间，使资源实现平衡,一个例子,1,2,3,5,4,6,0,2,6,C,D,2,4,F,2(7,2,4,B,2,3,2,E,3,8,G,3,2,7,H,4,1,A,4(9,11,0,2,4,4,7,11,各工作都按最早开始时间开始,日,日,人数,10,20,1,2,3,4,5,6,7,8,9,10,11,1,2,3,4,5,6,7,8,9,10,11,1,2,3,5,6,4,H(1,G(2,A(9,E(8,B,3,F(7,D(4,C(6,22,24,10,2,1,调整非关键工作的开始时间,日,日,人数,10,1,2,3,4

14、,5,6,7,8,9,10,11,1,2,3,4,5,6,7,8,9,10,11,1,2,3,5,6,4,H(1,G(2,A(9,E(8,B(3,F(7,D(4,C(6,10,资源有限，要求工期最短,下图表示的项目只有,10,人工作,日,日,人数,10,20,1,2,3,4,5,1,2,3,4,5,1,2,3,5,8,4,H(8,G(1,A(4,E(6,B(2,F(7,D(5,18,10,8,7,6,7,C(3,第一次调整,日,日,人数,10,1,2,3,4,5,1,2,3,4,5,1,2,3,5,8,4,H(8,G(1,A(4,E(6,B(2,F(7,D(5,8,10,8,7,6,7,C(3

15、,6,6,第二次调整,日,日,人数,10,1,2,3,4,5,1,2,3,4,5,1,2,3,5,8,4,H(8,G(1,A(4,E(6,B(2,F(7,D(5,10,9,7,6,7,C(3,6,6,工期缩短，总费用最少,一般情况下，若采取措施缩短工期，则间接费用,将减少，直接费用将增加，总费用由一个最低点,C,K,T,T,总费用,间接费用,直接费用,直接成本的处理,按线性处理，作业的费用率为,时间,t,费用,C,T,N,T,N,C,C,C,C,N,N,C,T,T,C,C,P,图,4-52,一个例子,1,2,4,3,1,3,3,2,5,1,2,4,1,0,2,1,1,6,3,i,j,P,T,T

16、,N,C,解题思路,以正常时间进行网络分析，求得关键路,线,在关键路线上，寻找最小费率的工作,缩短其时间，使工期最多到次长路线的,长度,缩短工期必须对所有关键路线进行，此,时应选择费率总和最小的组合方案,第一步求关键路线,1,2,4,3,1,3,3,2,5,1,2,4,1,0,2,1,1,6,3,0,3,5,11,0,3,5,11,作业,1,2,2-3,3-4,费率,3,1,3,工期,11,天,第二步选择,2,3,缩短工期,1,2,4,3,1,3,3,2,5,1,2,4,1,0,1,1,1,6,3,工期,10,天,增加费用,1,可选方案,I,II,III,缩短的作业,1,2),(1,3,2,3

17、),(1,3,3,4,总费用率,3+1=4,1+1=2,3,第三步按第,I,方案缩短工期,1,2,4,3,1,3,3,2,5,1,2,3,1,0,0,1,1,6,3,工期,9,天,增加费用,1+2=3,再按方案,III,缩短周期,1,2,4,3,1,3,3,2,5,1,2,3,1,0,0,1,1,5,3,可选方案,I,II,缩短的作业,1,2),(1,3,2,4),(3,4,总费用率,3+1=4,1+3=4,工期,8,天,增加费用,3+3=6,第四步按第,I,II,方案缩短,4,天,1,2,4,3,1,2,3,2,2,1,2,2,1,0,0,1,1,2,3,工期,4,天,增加费用,6+16=22,调整,1,2,与,2,3,并缩短,3,4,1,2,4,3,1,1,3,2,2,1,2,2,1,0,1,1,1,1,3,工期,3,天,增加费用,22+5=27,总合算费用，绘制直接费用图,直,接,费,用,C,K,T,工期,11,10,9,8,7,4,3,增加直接费用,0,1,3,6,10,22,27,总费用最小的优化,一般应考虑间接费用，工期缩短，总的间,接费用减少,例如，上例中，间接费用率为,4.5,天,则因为最