实用管理运筹学 第8章 图与网路.ppt

* * * * * 6.1 1 2 4 5 3 a 10 b 5 e 8 c 7 d 8 (a) 1 2 4 5 3 a 10 b 5 e 8 c 7 d 8 (b) 5 7 8 0 f 6 g 6 工序代号 所需时间 紧前工序 a 10 —— b 5 a c 7 a d 8 c e 8 b,d f 6 d g 6 d h 5 e,f,g 1 2 4 6 3 a 10 b 5 e 8 c 7 d 8 (c) 5 7 8 0 g 6 h 5 f 6 0 网络计划图 关键路线 在网络图上从始点(发点)开始，沿弧的方向(即按各工序的顺序)连续不断地到终点(收点)的一条路称为路线。网络中最长的路线称为关键路线，通常可用双线标出。关键路线上的各工序称为关键工序，其它工序称为非关键工序。 求解步骤如下： 步骤1：从网络的发点开始，按顺序计算出每个工序的最早开始时间(Earliest Start，ES)和最早结束时间(Earliest Finish，EF)，设一个工序所需的时间为t，这对于同一个工序来说，有EF=ES+t。 步骤2：从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(Latest Start，LS)和最晚结束时间(Latest Finish，LF)，显然对同一工序有LS=LF-t。 步骤3：计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始(或结束)的时间可以推迟的时间，称为该工序的时差，对每个工序来说其时差记为Ts，有Ts=LS-ES=LF-EF。 步骤4：找出关键工序，得到关键路线。时差为0的工序即为关键工序，关键工序组成关键路线；时差非0的工序为非关键工序，非关键工序的时差即为其可以推迟开始的最大时间。 例8-9 某工程项目的工序关系如表8-6所示。求完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。 工序代号 所需时间（天） 紧前工序 a 60 —— b 45 a c 10 a d 20 a e 40 a f 18 a g 30 d h 15 d,e i 25 g j 35 b,f,h,i 关键路线 6.2 解：根据表8-6绘制该工程项目的计划网络图，如图(a)所示。 关键路线 6.2 Step1：从网络的发点开始，按顺序计算出每个工序的ES和EF，并用“[ES,EF]”记录在表示该工序的弧的上方，如图(b)所示。 关键路线 6.2 Step2：从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的LS和LF，并用“[LS,LF]”记录在表示该工序的弧的下方，如图(c)所示。 关键路线 6.2 Step3：根据公式Ts=LS-ES=LF-EF，计算出每一个工序的时差，如表8-7所示。 工序代号 最早开始时间ES 最晚开始时间LS 最早完成时间EF 最晚完成时间LF 时差Ts 是否关键工序 a 0 0 60 60 0 是 b 60 90 105 135 30 否 c 60 107 70 117 70 否 d 60 60 80 80 0 是 e 60 80 100 120 20 否 f 70 117 88 135 47 否 g 80 80 110 110 0 是 h 100 120 115 135 20 否 i 110 110 135 135 0 是 j 135 135 170 170 0 是 关键路线 用线性规划的方法求关键路线，设xij表示弧(i，j)是否在关键路线上，是则为1，否则为0，建立数学模型如下： 关键路线 求解结果与上述方法的求解结果一致，数学模型的局限性在于只求出了关键路线，没有求出工序的最早开始时间、最早结束时间以及最晚开始时间、最晚结束时间。 计划网络图优化 ①优先安排关键工序所需的资源。 ②利用非关键工序的时差，错开各工序的开始时间。 ③统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。 工序代号 需要人数/人 最早开始时间/天 所需时间/天 时差/天 d 58 60 20 0 f 22 70 18 47 g 42 80 30 0 h 39 100 15 20 i 26 110 25 0 1.时间-资源优化 例8-10 在例9中，假定工序d,f,g,h,i的工作性质相似，同一工人可以完成5个工序的任何一个，5个工序所需的工人数如下表所示，试求一个时间-资源优化方案。 解：根据表8-8可绘制一个时间-资源负荷图，如图(a)所示。图的横坐标表示时间，纵坐标表示资源，时间-资源负荷图表示任意时刻所需资源的数量。利用非关键工序的时差，错开各