运筹学网络计划

1、第六章,网络计划,以网络图的形式制定计划，求得计划的最优方案,并据以组织和计划生产，达到预定目标的一种科学的管,理方法,引例：沏茶,烧水,10,沏茶,2,1,3,4,备茶,3,2,1,问题的一般提法,1,烧水,10,3,沏茶,2,4,备茶,3,2,设：有一项工程，分为若干道工序；已知各工序,间的先后关系，以及各工序所需时间,t,问：,1,工程完工期,T,2,工程的关键工序有哪些,相关概念,关键工序,主矛盾工序，不能延期完工,路,线,从始点到终点的一条路,关键路线,由关键工序组成的路线，是所有路线中时间,最长的路线。关键工序的延误将导致整个项目完,成时间延误,求解方法,关键路径法,Critica

2、l Path Methd,简称,CPM,方法,计划评审技术,Program Evaluation and Review,Technique,简称,PERT,法,两种方法的原理基本一致，都是用网络表示工程项目,以确定关键路线；这两种方法的主要区别是,CPM,方法对工程中各工序完工时间的估计是确定的，而,PERT,方法对时间估计是概率型的,PERT,方法主要注重计划中的时间问题,CPM,方法在把费用,概念引人计划控制过程中，不仅注重时间问题，而且还考,虑工程的费用和成本问题，考虑工程时间的均衡问题,2,解法关键路径法,CPM,分为三步,绘制工程网络图,标号法求工期,T,标号法求关键路线,准备工作,

3、将整个工程分解为若干工序,确定各工序的前后顺序（紧前、紧后,确定工序完成时间,一点估计法,三点估计法：最乐观时间,a,最可能时间,m,最悲观时间,t,a,4,m,b,ij,6,b,p135,1,绘制工程网络图,1,烧水,10,3,沏茶,2,4,1,顺序：按工序先后从左至右,备茶,2,图的结构,弧,箭线,表示工序,3,2,为工序的起点、终点,结点,表示相邻工序的时间分界点，称事项,连接箭尾的结点称为该工序的,紧前事项,连接箭头的结点称为该工序的,紧后事项,权,工序的完成时间,相邻弧,表示工序前后衔接关系，称紧,前,后,工序,只有当事项的所有紧前工序完成后，事项的紧后工序才能开始,1,绘制工程网络

4、图（续,3,绘图要求：图中不得有,缺口、回路和多重边,缺口,多个始点或多个终点的现象,应当只有一个始点和终点,回路,方向一致的闭合链,多重边的处理,一项工作只能用唯一的实箭线和唯一的,双号表示,处理方法：增加虚工序,a,1,2,a,1,2,2,虚工序,b,b,b,1,绘制工程网络图（续,3,绘图要求,要尽量避免弧的交叉,4,8,9,10,13,7,11,12,14,1,4,3,5,8,13,2,7,6,10,9,12,2,1,5,14,6,3,11,编号由左到右，不能重复,每条弧上起点的编号数小于终,点的编号数,方法：箭杆删除法,给起点一个编号数,1,设想将该点为起点的弧都去掉，从而又有新,的

5、起点，依次给新的起点编号，反复这样做直到终点已经编号为止,P135,例,1,某工厂进行技术改造，需要拆掉旧厂房、建造新,厂房和安排设备。这项改建工程可以分解为,7,道工序,其相关资料如下表,工序代号,A,B,C,D,E,F,G,工序名称,拆迁,工程设计,土建工程设计,采购设备,厂房土建,设备安装,设备调试,紧前工序,B,B,C,A,D,E,F,工序时间（周,2,3,2.5,6,20,4,2,工序代号,A,B,C,D,E,F,G,工序名称,拆迁,工程设计,土建工程设计,采购设备,厂房土建,设备安装,设备调试,紧前工序,B,B,C,A,D,E,F,工序时间（周,2,3,2.5,6,20,4,2,解

6、,1,B,3,A,2,2,C,2.5,3,D,6,E,20,F,4,G,2,4,5,6,用箭秆删除法标号（保证箭尾号大于箭头号,工序,紧前工序,A,_,10,B,_,3,C,_,1,D,_,2,E,D,7,9,F,E,3,G,A,F,5,H,G,4,I,B,H,4,J,B,H,3,K,I,J,6,L,G,3,M,C,I,4,N,K,L,7,所需天数,C,M,I,B,A,H,6,1,D,2,E,3,I,J,L,7,I,11,5,F,G,4,8,K,10,N,例,2,绘制工程网络图,工序代号,紧前工序,工序时间（周,A,2,B,3,C,2,D,A,3,E,A,4,续左表,工序代号,紧前工序,F,B

7、,G,B,H,D,E,I,B,C,J,G,I,工序时间（周,7,6,4,10,3,解,2,E,4,A,2,B,3,C,2,4,E,0,6,D,3,F,7,G,6,7,H,4,8,1,3,B,0,5,I,10,J,3,两种情况需要引入虚工序,两个工序,A,B,有相同的始点和终点,两个或两个以上的,工序有相同的紧前工序，又同时作为另外一工序的紧前工序,P134,图,6.1,四个工序,A,B,X,Y,有如下关系,A,是,X,的紧前工序,A,和,B,同时又是,Y,的紧前工序,1,A,B,2,X,Y,3,虚工序,A,4,5,6,P134,图,6.2,练习,工序,A,B,C,D,E,F,G,4,H,2,紧

8、前工序,4,A,9,A,B,3,B,6,D,E,2,D,C,G,F,工序时间,天,2,A (2,2,C (9,6,5,7,G (4,1,B (4,4,3,D (3,E (6,8,F (2,H (2,9,2,用标号法求工期,T,6,E (4,2,4,D (3,E,0,6,5,H (4,8,16,A (2,0,2,3,1,B (3,C (2,3,B,0,3,F(7,G(6,13,6,I (10,7,J(3,1,标出各事项的最早开始时间,给始点,1,标,0,给任意点,j,标,E,j,E,j,Max,以,j,为箭头的各箭之,箭尾,2,终点,n,的,T,中的,T,即完工期,箭长,t,ij,3,求关键路（

9、用标号法,6,2,A (2,0,0,1,B (3,C (2,8,3,3,B,0,3,E (4,4,D (3,12,E,0,6,5,F(7,2,12,H (4,3,8,16,16,G(6,13,7,13,J(3,6,I (10,3,1,标出各事项的最晚开始时间,给终点,n,标,T,给任意点,i,标,L,i,L,i,Min,以,i,为箭尾的各箭之,箭头,箭长,t,ij,3,求关键路（用标号法,6,2,A (2,12,E (4,8,3,4,D (3,E,0,6,5,2,3,3,12,H (4,0,0,1,B (3,C (2,F(7,G(6,13,7,13,8,16,16,B,0,3,6,I (10,

10、3,J(3,2,计算各工序,i,j,的,R(i,j),j,的总时差,不影响总工期条件下，任务可以延,t,ij,i,的,迟的最大幅度,3,关键路径：由,R(i,j)= 0,的关键工序组成的由,1,至,n,的路,一个工序的总时差为,0,意味着该工序在不影响工期前提下机动时间为,0,及工序的最早开始时间也是最迟开始时间，其开始和结束时间没有一点,注,关键工序,头尾皆有,反之未必成立,机动的余地,练习,工序,紧前工序,A,B,4,C,A,9,D,A,B,3,E,B,6,F,D,E,2,G,4,H,2,D,C,G,F,工序时间,天,2,A (2,4,0,0,1,B (4,2,2,2,11,11,C (9

11、,6,7,5,7,10,13,G (4,11,15,8,15,8,4,3,4,7,17,H (2,9,17,D (3,E (6,F (2,工序时间参数的计算,1,计算最早开始时间,ES,与最早完工,EF,时间,从网络起点开始,用下列公式计算最早开始时间,t,ES,和最,早完工时间,t,EF,最早开始时间,紧前活动的,最早结束时间的最大值,开始结点的最早时间,t,ES,i,j,max,k,t,EF,k,i,ET,i,最早完工时间,最早开始时间,活动持续时间,t,EF,i, j,t,ES,i, j,t,i, j,工序时间参数的计算,续,2,计算最晚开始时间与最晚结束时间,从最后活动开始依次按下式计

12、算每个活动最晚结,束时间,t,LF,和最晚开始时间,t,LS,最晚结束时间,紧后活动的,最晚开始时间的最小值,完成结点的最晚时间,t,LF,i,j,min,k,t,LS,j,k,LT,j,最晚开始时间,最晚结束时间,活动持续时间,t,LS,i, j,t,LF,i, j,t,i, j,工序时间参数的计算,续,3,总时差,总时差,不影响总工期条件下，任务可以延迟的最大幅,度，用,R,i,j,表示,总时差,最晚开始时间,最早开始时间,最晚结束时间,最早结束时间,R,i,j,t,LS,i,j,t,ES,i,j,t,LF,i,j,t,EF,i,j,p144,作业,工序代号,工序,紧前工序,工序时间,A,

13、B,C,D,系统提出和研究问题,研究选点问题,准备调研方案,收集资料工作安排,无,A,A,B,4,7,10,8,E,F,G,H,I,挑选、实地训练工作人员,准备收集资料用表格,实地调查,分析准备调查报告,任务结束,B,C,C,D,E,F,G,H,12,7,5,4,0,工序代号,A,B,C,D,E,工序,系统提出和研究问题,研究选点问题,准备调研方案,收集资料工作安排,挑选、实地训练工作人员,紧前工序,无,A,A,B,B,C,工序时间,4,7,10,8,12,F,G,H,I,准备收集资料用表格,实地调查,分析准备调查报告,任务结束,C,D,E,F,G,H,7,5,4,0,11,2,3,11,14

14、,D 8,网络结构图,逻辑关系图,关键路线,B 7,5,14,14,14,4,E,12,F 7,26,26,6,26,5,G,5,31,31,7,31,6,H,4,35,35,8,35,7,0,0,1,0,1,A,4,4,4,2,4,1,C,10,14,14,14,2,4,课堂练习,P150,习题,6.1,工,序,a,b,c,紧前,工序,a,a,a,a,a,工序,时间,60,14,20,30,21,10,工,序,g,h,i,j,k,l,紧前,工序,b,c,e,f,f,d,g,h,j,k,工序,时间,7,12,60,10,25,10,工,序,m,n,o,p,q,紧前,工序,j,k,i,l,n,m

15、,o,p,工序,时间,5,15,2,7,5,3,b,4,30,21,d,e,f,1,a,60,b,14,c,2,20,d,7,g,7,e,j,10,绘制网络图，关键路线，工期，总时差,10,f,6,h,12,8,25,k,9,m,5,10,10,f,5,l,n,p,7,i,60,o,11,15,12,2,13,5,q,14,课堂练习,P150,习题,6.1,3,b,4,30,21,7,1,a,60,b,14,c,2,20,g,7,d,e,j,10,8,25,10,f,6,h,12,k,9,m,5,10,10,f,5,l,n,p,7,152,13,5,i,60,o,11,15,12,2,q,14

16、,练习,为筹建某餐馆，需制定计划。将工程分为,14,道工序，各工序需时及先后关系如下表。试求,该工程完工期,T,及关键路径,工序,A,B,内容,购买炉灶及材料,购买室内设备,紧前工序,所需天数,10,3,C,D,E,招集工人,选择开业地点,申请许可得到执照,D,1,2,7,F,G,H,修理门窗、粉刷墙壁,砌炉灶、水池,接通上下水道,E,A,F,G,3,5,4,I,J,K,安装室内设备,做好室内装饰,购进米面及副食品,B,H,B,H,I,J,4,3,6,L,M,N,张贴开业广告,人员训练,开业前操作试验,G,C,I,K,L,3,4,7,工序,紧前,工序,所需,天数,A,_,10,B,_,3,C,

17、_,1,D,_,2,E,D,7,F,E,3,G,A,F,5,H,G,4,I,B,H,4,J,B,H,3,K,I,J,6,L,G,3,M,C,I,4,N,K,L,7,9,C,M,I,B,A,2,E,3,H,6,7,I,8,K,N,11,1,D,I,J,L,5,F,G,4,10,C(1,0,1,D(2,2,2,9,25,M(4,I(0,21,H(4,38,6,I(4,J(3,7,25,I(0,8,25,K(6,10,31,N(7,11,B(3,A(10,17,3,F(3,4,12,5,L(3,E(7,9,G(5,2,求完工期（用标号法,1,标出各事项的最早开始时间,给始点,1,标,0,给任意点,j

18、,为箭头的各箭,之,标,E,j,E,j,Max,以,j,箭尾,箭长,t,ij,n,的,T,2,终点,中的,T,即完工期,0,0,1,D(2,2,C(1,B(3,A(10,2,2,E(7,34,9,25,M(4,I(0,21,H(4,38,6,21,38,7,25,I(0,25,8,25,K(6,10,31,N(7,I(4,J(3,25,11,17,3,9,F(3,17,4,12,5,L(3,12,G(5,9,31,3,求关键路（用标号法,1,标出各事项的最晚开始时间,给终点,n,标,T,为箭尾的各箭之,箭头,2,计算各工序,i,给任意点,i,标,L,i,L,i,Min,以,i,箭长,t,ij,

19、t,ij,i,的,j,的时差,R(i,j),j,的,3,关键路径：由,R(i,j)= 0,的关键工序组成的由,1,至,n,的路,0,0,1,D(2,2,C(1,34,9,25,M(4,I(0,21,H(4,38,38,B(3,A(10,6,21,I(4,J(3,7,25,I(0,8,25,25,K(6,10,31,25,11,2,2,E(7,9,3,9,17,F(3,17,4,12,5,L(3,12,N(7,G(5,31,完工期,T=38,天,关键路,D-E-F-G-H-I-K-N,由本例可见,关键工序,头尾皆有,但反之未必,关键工序时间之和,工期,T,二、工程完工期的概率分析,计划评审技术,

20、PERT,1,PERT,与,CPM,的区别,CPM,工序时间是确定的,工程工期的概率分析是是时间不确定情况下,PERT,的主要工作,确定平均工序时间的三点估计法,设工序最乐观时间为,a,最悲观时间为,b,最可能时,m,ij,ij,ij,a,4,m,b,ij,ij,ij,t,ij,6,b,ij,a,ij,6,2,ij,2,期望工期,T,E,关键工序的平均工序时间之和,工期方差,关键工序时间方差之和,2,2,N,T,由概率论的中心极限定理总工期,T,E,标准化,T,T,E,N,0,1,给定时间,T,求工期,TT,内完工的概率,方法：首先计算,T,T,E,P,T,T,P,1,t,2,2,e,2,d,

21、t,阴影面积,然后查表求,1,1,例,15,已知某工程网络图，以及各工序的时间参数,3,1,A,12.83,B,D,E,4,F,9,4,10.33,6,5,G,12.17,2,7.83,C,8.17,b,15,10,10,11,6,14,15,13,H,7,11,工序,A,B,C,D,E,F,G,H,a,10,5,7,7,2,8,10,9,m,13,8,8,9,4,10,12,11,t,ij,12.83,7.83,8.17,9,4,10.33,12.17,ij,2,0.69,0.25,求工程在,43,天内完工的概率,解,关键路线,I,为:ACFH,T,E,42.33,2,2,1,54,ij,2

22、,38,i,j,I,T,T,43,42,33,E,0,44,1,54,1.00,0.44,P,T,43,0,44,0,67,11,例,2,某工程可分为,11,项工作，有关资料如下表,紧前,工作,工作,A,B,C,A,D,B,E,B,F,C,G,C,H,G,H,I,D,E,J,K,F,I,J,工序时间,a,1,1,1,1,2,3,2,1,1,1,4,m,2,2,2,10.5,5,6,3,2,4,2,4,b,3,3,3,17,14,15,10,9,7,9,4,1,画出施工网络图，确定关键路线及完工期,T,E,2,估计工程在,20,周内完工的概率,紧前,工作,工作,A,B,C,A,D,B,E,B,F

23、,C,G,C,H,G,H,I,D,E,J,K,F,I,J,0,0,1,工序时间,a,1,1,1,1,2,3,2,1,1,1,4,m,2,2,2,10.5,5,6,3,2,4,2,4,2,D(10,E(6,b,3,3,3,17,14,15,10,9,7,9,4,12,12,J(3,5,t,2,2,2,10,6,7,4,3,4,3,4,0.33,0.33,0.33,2.67,2.00,2.00,1.33,1.33,1.00,1.33,0,2,ij,0.11,0.11,0.11,7.13,4.00,4.00,1.77,1.77,1.00,1.77,0,19,19,9,2,2,A(2,B(2,3,2,

24、4,6,15,15,K(4,8,C(2,2,7,F(7,G(4,6,7,11,I(4,H(3,6,5,11,期望工期,T,E,19,关键路,A-D-J-K,2,0.33,2.67,1.33,0,3.001,3,2,2,2,2,20,19,0.6293,P,T,20,0,33,3,工程在,20,周内完工的概率为,0.6293,19,20,标准正态分布数值表,z,0.31 0.32 0.33 0.34 0.35,P,Z,z,0.6217 0.6255 0.6293 0.6331 0.6338,2,给定概率,p,求完工可能性为,p,的工期,方法：首先查表求,使,p,再由,T,T,E,解出,T,例、上

25、例中，求完工可能性达,95,的工期,解：由,0,95,查表,1,6,再由,T,T,T,42,33,E,解出,1,54,45,T,压缩工程工期,问题,保证质量。不增加人力，物力尽量缩短工期,思路,1,向关键工序要时间,2,在非关键工序挖潜力,赶工期问题中，只有压缩关键工序才能引起总工,期缩短。若网络图中同时有几条关键路线，则几条关,键路线必须,同时在各自线路上压缩一个关键工序,才能缩短总工期,压缩工期步骤,一,选择压缩工序,二,确定压缩量,一,选择压缩工序的步骤,1,构建关键路线网络，赋权为压缩费用率（对不可压缩,工序赋权为,M,表示压缩费用率很大,2,求此网络最小截,3,选择最小截上工序同时进

26、行压缩,二,压缩量确定,1,压缩量,t,不超过工序上允许压缩限度,2,压缩量不超过关键路长与次关键路长之差值（一般限,制压缩量不超过非关键工序最小总时差,即压缩量,t,由,下式确定,t,min,min,t,i,j,t,i,j,i,j,I,min,R,i,j,R,i,j,0,例：下图是某工程施工网络，图中单箭线,表示普通工序，箭线上,的,t,ij,C,ij,d,ij,中,t,ij,为工序时间,C,ij,为该工序上每压缩一天所需的费,用,d,ij,为可压缩天数,2,1(3,0,H,5(5,4,A,8(3,7,B,I,5,L 1(3,0,3,5(1,4,C,D,7(2,6,4(2,3,E,5(1,4

27、,K,M,3(8,2,7,3(4,2,J,6,N,3(4,2,10(4,9,F,1,4,8,P,9,8(7,7,G,1(4,0,10,5(4,4,1,关键路线与工期,2,工期压缩为,18,天，应如何选择压缩工序和压缩天数,3,工期压缩到,17,天，通过在,1,中所选定的压缩工序上压,缩,3,天能否达到目的什么,1,计算关键路、工期、总时差,4,1,1(3,0,0,0,H,5(5,4,A,8(3,7,B,3(4,2,J,17,4,N,2,L 1(3,0,5,5,1,5(4,4,I,5,7,5(1,4,3,C,7(2,6,D,8,8,4(2,3,4,E,5(1,4,K,M,5,3(8,2,10,1

28、0,6,3(4,2,10(4,9,7,F,8(7,7,8,12,G,12,P,1(4,0,9,19,8,20,10,20,关键路线,A,C,F,A,D,G,B,E,G,工期,T,E,20,天,工序,总时差,H,L,J,N,P,M,K,I,3,3,13,13,11,11,2,2,2,构建关键路线网络,赋权值为费用率,确定最小割,选择压缩工序,5,1,4,C,D,7,2,6,4,2,3,E,1,5,5,4,A,8,3,7,B,3,7,10,4,9,F,4,8,8,7,7,G,10,用最大流标号法得最小割为,C, D, E,所以选择在工序,C, D,E,上压缩时间,根据非关键工序的总时差和压缩工序的

29、限制，确定压缩量,2,得压缩量为,T,m,in,2,m,d,in,d,d,3,C,D,E,在,C,D,E,工序上各压缩两天，使总工期压缩至,18,天,3,工期压缩,2,天后，关键路线已发生变化，所以不能在中选中的压缩,工序压缩三天以达到工期成为,17,天的目的。重复上述步骤，得新的网络,重新确定关键路线和非关键路线的总时差，如图,4,1,1(3,0,H,5(5,4,A,8(3,7,B,I,15,2,L 1(3,0,3(1,2,3,C,5(2,4,D,8,8,2(2,1,4,E,5(1,4,K,5,M,3(8,2,5,5,3(4,2,J,6,4,8,8,7,N,0,0,1,3(4,2,10(4,

30、9,F,8(7,7,G,10,18,18,8,5(4,4,10,10,P,1(4,0,5,5,工序,总时差,9,17,8,N,P,M,H,L,J,3,3,11,11,9,9,继续构建关键路线网路，确定最小割为,C,D,E,K,作为压缩,工序。确定压缩量,5,5,4,A,8,3,7,B,5,4,4,I,5,3,3,1,2,C,D,5,2,4,2,2,1,E,5,1,4,K,7,10,4,9,F,8,7,7,G,10,1,4,8,根据非关键工序的总时差和压缩工序的限制，确定压缩量,m,d,in,d,d,d,1,最小时差,3,得压缩量为,C,D,E,K,T,mi,n,1,在,C,D,E,K,工序上各

31、压缩,1,天，使总工期压缩至,17,天,工程费用分析,问题,编制工程网络计划时，不仅要考虑工期时间，还应,到考虑工程造价,对一个工程来说，无论是以考虑工程费用为主，还,是以控制时间进度为主，都必须对工程计划进行时间,费用分析，从而可综合考虑制定最优的计划,费用概念,直接费用,指人工、材料、燃料等直接用来完成工程,任务的费用,工序直接费用率,指一道工序缩短单位时间所需增,加的费用,赶进度工时费用,正常工序时间费,直接费用率,q,正常工序时间,赶进度工序时间,间接费用,指管理人员的工资、办公、采购等并非直,接用于完成工程任务的费用,间接费用率,p,整个项目的工期每提前单位时间可节,约的费用,工程的

32、时间,费用关系图,压缩工期会增加直接费用，但减少了间接费用,延长工期会增加间接费用，但可能减少直接费用,总费用曲线由同一,工期下的直接费用,和间接费用相加得,到,费,用,总费用,直接费用曲线,工程的时间,费用曲线,间接费用曲线,最低成本工期,T,E,工期时间,因此只有当压缩关键工序时间增加的直接费用小于由,此导致工期缩短而节约的间接费用时，这一压缩才进行,最低成本工期的确定,q (i, j,工序,i, j,的费用率,t,i, j,工序,i, j,的工序时间可缩短下限，即赶进度时间,p,单位时间的间接费用率,确定最低成本工期的步骤,一、绘制网络图，计算工序总时差,R (i, j,确定,T,E,与

33、关键路线,计算相应工程费用,二、在各关键路线上所有可压缩的工序中，各确定一个本线路上,费用率最低的工序作为压缩工序，这些压缩工序之集合用,I,表示,一,般可由,1,构建关键路线网络，赋权为压缩费用率（对不可压缩工序赋,权为,M,表示压缩费用率很大,2,求此网络最小截,3,选择最小截上工序同时进行压缩,q,i,j,q,q,p,0,三,计算这些压缩工序上费用率之和,若,i,j,I,则表示压缩工期将引起工程费用上升，若,q,p)0,表示可以压缩工,期使总费用下降,四,确定压缩时间,t,t,的选择可由,t (i, j,与,R (i, j,决定，可用下列式子表示,t,min,min,t,i,j,t,i,

34、j,i,j,I,min,R,i,j,R,i,j,0,在压缩供需上压缩时间,t,以后，绘制新的网络图，继续重复上述步,骤，直到发生,q,p) 0,时为止,最低成本工期确定步骤,1,绘制网络图，计算工序总时差,R (i, j,确定,TE,与关键路线，计,算相应工程费用,压缩,4,确定压缩时间,t,t,min,min,t,i,j,t,i,j,i,j,I,min,R,i,j,R,i,j,0,2,在各关键路线上各确定,一个本线路上费用率最低,的工序作为压缩工序，这,些压缩工序之集合用,I,表示,是,3,计算这些压缩工序,上费用率之和,i,j,I,若,q,p)0,q,i,j,q,否,最低成,本工期,例：下图表示由,l,m,n,o,p,q,