第六章网终计划 、工程计划网络问题(关键路径法) 1.问题的一般提法 设:有一项工程,分为若干道工序;已知各工序 间的先后关系,以及各工序所需时间t 问:(1)工程完工期T=? (2)工程的关键工序有哪些? 2.解法关键路径法(CPM) (1)绘制工程网络图
一、工程计划网络问题（关键路径法） 1. 问题的一般提法 设：有一项工程，分为若干道工序；已知各工序 间的先后关系，以及各工序所需时间t。 问：（1）工程完工期T=？ （2）工程的关键工序有哪些？ 2.解法——关键路径法（CPM） （1）绘制工程网络图 第六章 网络计划
1)顺序:按工序先后从左至右; 2)图中弧(箭线):表示工序; 顶点(结点):表示相邻工序的时间分 界点,称事项,用⑦表示。 相邻弧:表示工序前后衔接关系,称紧 前(后)工序; 3)要求:图中不得有缺口、回路和多重边。 缺口:多个始点或多个终点的现象。○ (应当只有一个始点和终点) 回路:方向一致的闭合链
1）顺序：按工序先后从左至右； 2）图中弧（箭线）：表示工序； 顶点（结点）：表示相邻工序的时间分 界点，称事项，用 表示。 相邻弧：表示工序前后衔接关系，称紧 前（后）工序； 3）要求：图中不得有缺口、回路和多重边。 i 缺口：多个始点或多个终点的现象。 （应当只有一个始点和终点） 回路：方向一致的闭合链
多重边:两点间有多于一条的边。 ABQ 处理方法:增加虚工序。 B 例1为筹建某餐馆,需制定计划。将工程分为 14道工序,各工序需时及先后关系如下表。试求 该工程完工期T及关键路径
例1 为筹建某餐馆，需制定计划。将工程分为 14道工序，各工序需时及先后关系如下表。试求 该工程完工期T及关键路径。 多重边：两点间有多于一条的边。 A B 处理方法：增加虚工序。 A A’ B
工序」 内 紧前工序所需天数 ∧购买炉灶及材料 10 B购买室内设备 C|招集工人 D选择开业地点 E|申请许可得到执照 F修理门窗、粉刷墙壁 DE G砌炉灶、水池 A、F H|接通上下水道 G I安装室内设备 B、H J做好室内装饰 B、H K购进米面及副食品 L张贴开业广告 27354436347 M人员训练 N开业前操作试验 K、L
工序 内容 紧前工序 所需天数 A 购买炉灶及材料 —— 10 B 购买室内设备 —— 3 C 招集工人 —— 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
工序ABC|DE| FGHIJKLMN 紧前 DEAGBBIGCIK 工序 F HH J L 所需|103 27354436347 天数 B A F s K
工序 A B C D E F G H I J K L M N 紧前 工序 _ _ _ _ D E AF G BH BH IJ G CI KL 所需 天数 10 3 1 2 7 3 5 4 4 3 6 3 4 7 1 C B D A 2 E 3 F 4 G 5 H 6 IJ 7 I ’ 8K L 9 I’’ M 10 N 11
25 I(0 38 B(3) 21 25 D(2) A(10) H(4 T(0) J(3) 25 K(6 E(7) G(5)L(3 F(3) 12 31 (2)求完工期(用标号法) 1)标出各事项的最早开始时间国, 给始点①标0]; 给任意点①标1,E=Max{以①为箭头的各箭之 箭尾」+箭长t”} 2)终点(n的中的T即完工期
（2）求完工期（用标号法） 1）标出各事项的最早开始时间 ， -给始点 标 ； -给任意点 标 ,Ej=Max{以 为箭头的各箭之 “箭尾 +箭长t ij”} 1 0 j Ej j 2) 终点 n 的 T 中的T即完工期。 1 C(1) B(3) D(2) A(10) 2 E(7) 3 F(3) 4 G(5) 5 H(4) 6 I(4) J(3) 7 I’(0) 8 K(6) L(3) 9 I’’(0) M(4) 10 N(7) 11 0 2 9 12 17 21 25 25 31 25 38
3425 38/38 B(3) 21 ⑦2525和 D(2) A(10) H(4)2 I(0) J(3) 2 17175 23825/N7 E(7 F(3 G(5)I(3) 4 1212 31/3 (3)求关键路(用标号法) 1)标出各事项的最晚开始时间△, 给终点标△:给任意点⑥标△L=Min(以① 为箭尾的各箭之“箭淞、-箭长t”} 2)计算各工序①·①的时差R(i)①的△t①的 3)关键路径:由R(ij=0的关键工序组成的由①至(的路
（3）求关键路（用标号法） 2）计算各工序 的时差R(i,j)= 的 -t ij i j j - i 的 。 1）标出各事项的最晚开始时间 ， -给终点 标 ； -给任意点 标 ,Li=Min{以 为箭尾的各箭之 “箭头 -箭长t ij”} n T i Li i 3）关键路径：由R(i,j)= 0的关键工序组成的由 1 至 n 的路。 9 1 C(1) B(3) D(2) A(10) 2 E(7) 3 F(3) 4 G(5) 5 H(4) 6 I(4) J(3) 7 I’(0) 8 K(6) L(3) I’’(0) M(4) 10 N(7) 11 0 2 9 12 17 21 25 25 31 25 38 38 25 34 25 21 31 17 12 9 2 0
5 C(1) 34 0 81/38 38 B(3) 21 25 25 D(2 A(10) H(4)/2 r(0) J(3) E(N3 F3)ovi L B25/NO 2(2 1717(5 G(5) 31/3 完工期T=38(天); 关键路:DE-F-G-H--KN。 由本例可见:关键工序→头尾皆有口=△,但反之未必 关键工序时间之和=工期T
1 C(1) B(3) D(2) A(10) 2 E(7) 3 F(3) 4 G(5) 5 H(4) 6 I(4) J(3) 7 I’(0) 8 K(6) L(3) 9 I’’(0) M(4) 10 N(7) 11 0 2 9 12 17 21 25 25 31 25 38 38 25 34 25 21 31 17 12 9 2 0 完工期T=38（天）； 关键路：D-E-F-G-H-I-K-N。 由本例可见：关键工序 头尾皆有 = ，但反之未必。 关键工序时间之和=工期T。
二、工序时间不确定的工程计划网络问题 (计划评审技术PERT) 1与CPM的区别仅在于: 工序时间t是随机变量,从而完工期η也是随机的。 但由中心极限定理,可近似认为7服从于N(ea2) 2确定平均工序时间t的三时估计法: 设工序最乐观时间为a,最悲观时间为b,最可能时间为m a+4m,,2的方差为O
二、工序时间不确定的工程计划网络问题 （计划评审技术PERT） 1.与CPM的区别仅在于： 但由中心极限定理，可近似认为 服从于 ， 。 工序时间 是随机变量，从而完工期 也是随机的。 ( ) 2 T N T t T 2.确定平均工序时间t i j 的三时估计法： 设工序最乐观时间为a ，最悲观时间为b ，最可能时间为m , 2 2 6 , 6 4 − = + + = b a t a m b 则 t 的方差为
3期望工期T。=关键工序的平均工序时间之和; 工期方差σ2=关键工序时间方差之和。 4求工程在T天内完工的概率 ∵T~N(T,2) T-TT-T ∴P(T≤T)=P( 由标准正态分布数值表可查得 d(=)=P(Z≤2)=
2 3. 工期方差 期望工期T E =关键工序的平均工序时间之和； =关键工序时间方差之和。 4.求工程在Tk 天内完工的概率2 2 2 ( , ), ( ) ( ) ( ) ( ) 1 ( ) ( ) 2 E E k E k k E k E z x T N T T T T T P T T P T T T T P Z z P Z z e dx − − − − = − − = = = = 由标准正态分布数值表可查得：