《运筹学》课程授课教案（讲稿）第20讲 关键路径求解法

课程名称：《运筹学》第_20 讲次1、网络计划图的画法及其相关概念授课题目2、关键路径求解法本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，会画网络计划图，学会用关键路径求解法计算工期。[重点及难点】关键路径求解法。内容[本讲课程的引入]大型项目的开发涉及很复杂的项目协调和管理问题，为使项目管理人员对项目进度有全面的了解，进行有效的控制，必须使用科学的管理方法[本讲课程的内容]网络计划法是使用最广泛的方法之一，关键路径法(CPM)和项目评审技术(PERT)是两种使用最广泛的网络计划技术。网络计划方法的优点使它适用于生产技术复杂，工作项目繁多，且紧密联系的一些跨部门的工作计划，如：新产品研制开发大型工程项目建设生产技术准备复杂设备的大修计划网络计划方法的基本原理：将工程项目分解为相对独立的活动，根据各活动先后顺序、相互关系以及完成所需时间做出反映项目全貌的网络图：从项目完成全过程着眼，找出影响项目进度的关键活动和关键路线，通过对资源的优化调度，实现对项目实施的有效控制和管理。网络计划方法的主要功能1用网络图描述一个实际项目的管理问题（画网络图）；2计算项目的最早、最晚完成和开工时间（网络计算)；3寻找关键活动和关键路径(网络分析);4根据以上分析对网络进行优化

课程名称：《运筹学》 第 20 讲次 授课题目 1、网络计划图的画法及其相关概念 2、关键路径求解法 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，会画网络计划图，学会用关键路径求解法计算工期。 [重点及难点] 关键路径求解法。 内 容 [本讲课程的引入] 大型项目的开发涉及很复杂的项目协调和管理问题，为使项目管理人员对项目进度 有全面的了解，进行有效的控制，必须使用科学的管理方法. [本讲课程的内容] 网络计划法是使用最广泛的方法之一，关键路径法(CPM)和项目评审技术(PERT)是两种使用 最广泛的网络计划技术。 网络计划方法的优点使它适用于生产技术复杂，工作项目繁多，且紧密联系的一些跨部门的 工作计划，如： 新产品研制开发 大型工程项目建设 生产技术准备 复杂设备的大修计划 网络计划方法的基本原理： 将工程项目分解为相对独立的活动，根据各活动先后顺序、相互关系以及完成所需时间做出反映 项目全貌的网络图；从项目完成全过程着眼，找出影响项目进度的关键活动和关键路线，通过对资源 的优化调度，实现对项目实施的有效控制和管理。 网络计划方法的主要功能： 1 用网络图描述一个实际项目的管理问题 (画网络图) ; 2 计算项目的最早、最晚完成和开工时间 (网络计算) ; 3 寻找关键活动和关键路径(网络分析); 4 根据以上分析对网络进行优化

内容一、网络计划与网络图复杂工程项目可被分解为一系列小的事件或活动，各种事件和活动之间的逻辑顺序可以表述为一个由一系列弧和节点组成的网络图：网络图中的有向弧代表各种活动(或工作），活动完成需要的时间写在弧上；节点表示事件（或事项），表示活动的开始与结束，每个节点有唯一节点号；位于弧的起点和终点的节点表示活动或事件的开始和结束，每个活动有一个起点和一个终点521a圆圈和里面的数字代表各事项，写在箭杆中间的数字5表示完成本工作所需时间，即工作α(1,2)，事项：（1,2)。”表示。它表示工时为零，不消耗任何资源的虚虚工作用箭线“构工作。其作用只是正确表示工作的前行后继关系。整个网络的方向按惯例从左到右地反映活动的逻辑顺序，并有唯一的起点和终点。画网络图有以下四个阶段：一、列出所有活动一个完整的项目必须被分解为一系列独立活动（称为工序），分解程度取决于项目计划的需要以及相应的管理职能。二、确定每个活动的紧前工序项目执行的连续性确定了项目各项活动的前后顺序，为了从逻辑上搞清楚活动之间的顺序关系，需要确定每项活动可以开始之前必须完成的活动--紧前工序。注意：区分习惯上发生的顺序和它们在逻辑上应该发生的顺序，例如，寄出一个发票的一般方法是：(1）检查发票(2）将发票放入信封

内 容 一、网络计划与网络图 复杂工程项目可被分解为一系列小的事件或活动，各种事件和活动之间的逻辑顺序可 以表述为一个由一系列弧和节点组成的网络图； 网络图中的有向弧代表各种活动(或工作), 活动完成需要的时间写在弧上； 节点表示事件 (或事项), 表示活动的开始与结束, 每个节点有唯一节点号； 位于弧的起点和终点的节点表示活动或事件的开始和结束, 每个活动有一 个起点和 一个终点: 圆圈和里面的数字代表各事项，写在箭杆中间的数字 5 表示完成本工作所需时间， 即工作 a ( 1 , 2 )，事项： ( 1 , 2 )。 虚工作用箭线“ ” 表示。它表示工时为零，不消耗任何资源的虚 构工作。其作用只是正确表示工作的前行后继关系。 整个网络的方向按惯例从左到右地反映活动的逻辑顺序, 并有唯一的起点和终点。 画网络图有以下四个阶段: 一、列出所有活动 一个完整的项目必须被分解为一系列独立 活动（称为工序）, 分解程度取决于项目计划的需要以及相应的管理职能。 二、确定每个活动的紧前工序 项目执行的连续性确定了项目各项活动的前后顺序, 为了从逻辑上搞清楚活 动之间的顺序关系, 需要确定每项活动可以开始之前必 须完成的活动-紧前工序。 注意 ： 区分习惯上发生的顺序和它们在逻辑上应该发生的顺序, 例如, 寄出一个发 票的一般 方法是: (1) 检查发票 (2) 将发票放入信封

内容(3）封上信封(4）在信封上写地址这不是唯一正确方法，网络图应能反映所有可能性，而不仅仅是传统方法。三、画网络图画网络图应注意以下规则1、网络只能有一个总起点和一个总终点；?④679782图8.27中，有两个总起点事项①，；三个总终点事项④，③，③，不符合规则。2、网络图为有向图，且不能有回路；图8.28中③V③VV③是回路，不符合规则3、两个节点之间不能有两条或两条以上的弧（两个及两个以上的工作）：b2a图8.29不符合规则。4、应正确表示活动之间的前行后继关系；如4道工作a,b,c,d的关系为：c必须在a,b均完成后才能开工，而d只要在b完工后即可开工，如画成下图是错误的，因本来与α工作的工作d被错误地表为必须在α完工后才能开工

内 容 (3) 封上信封 (4) 在信封上写地址 这不是唯一正确方法, 网络图应能反映所有可能性, 而不仅仅是传统方法。 三、画网络图 画网络图应注意以下规则: 1、网络只能有一个总起点和一个总终点; 图 8. 27 中，有两个总起点事项①， ⑦ ；三个总终点事项④，⑥，⑨，不符合规则。 2、网络图为有向图, 且不能有回路； 图 8. 28 中 ③⑤  ⑥  ③是回路，不符合规则 3、两个节点之间不能有两条或两条以上的弧（两个及两个以上的工作）; 图 8 . 29 不符合规则。 4、应正确表示活动之间的前行后继关系; 如 4 道工作 a , b , c , d 的关系为： c 必须在 a , b 均完成后才能开工，而 d 只要 在 b 完工后即可开工，如画成下图是错误的，因本来与 a 工作的工作 d 被错误地表 为必须在 a 完工后才能开工

容内73.2P5、虚拟活动的运用网络有时需要包括由虚线表示的虚拟，活动。首先，它可以避免两个活动有相同的起点和终点；其次，使用虚拟活动可以帮助表示一些特殊的逻辑依赖关系。如前面不符合规则的图8.27，图8.29，图8.30，用添加虚工作的方法改图为图831，图8.32，图8.33就是正确的了。1h5商业中心建设活动表活动紧前活动设计A获规划局批准R招标/选择承包商A,BC商厦建设CD外部装修

内 容 5、虚拟活动的运用 网络有时需要包括由虚线表示的‘虚拟’ 活动。首先, 它可以避免两个活动有相同的起 点和终点; 其次, 使用虚拟活动可以帮助表示一些特殊的逻辑依赖关系。 如前面不符合规则的图 8 . 27 ，图 8 . 29，图 8 . 30，用添加虚工作的方法改图为图 8 . 31，图 8 . 32，图 8 . 33 就是正确的了。 商业中心建设活动表 活动 紧前活动 A 设计 － B 获规划局批准 － C 招标/选择承包商 A , B D 商厦建设 C E 外部装修 D

内容与商业机构谈判A,BF与商业机构签约GD,G使用区域分割HH内部装修进驻I,E商业中心建设网络图商业中心建设网络图6、平行工作虚工作还可以用于正确地表示平行工作与交叉工作。一道工作分为几道工作同时进行，称为平行工作，如图图8.34（a）中市场调查（2，3）中需12天，如增加人力分为三组同时进行，可画为（b）。（市场调研）图8.34(a)

内 容 F 与商业机构谈判 A , B G 与商业机构签约 F H 使用区域分割 D , G I 内部装修 H J 进驻 I , E 6、平行工作 虚工作还可以用于正确地表示平行工作与交叉工作。一道工作分为几道工作同 时进行，称为平行工作，如图图 8 . 34（a）中市场调查（2，3）中需 12 天，如增加人力 分为三组同时进行，可画为（b）

内容3(调（调2(调3)图8.34（b）7、交叉作业两件或两件以上的工作交叉进行，称为交叉工作。如工作A与工作B分别为挖沟和埋管子，那么它们的关系可以是挖一段埋一段，不必等沟全部挖好再埋，这就可以用交叉作业来表示，如把这工作各分为三段，A=al+a2+a3，B=b1+b2+b3，可用图8.35表示：图8.35如果要尽量避免弧的交叉，图8.36（a）中许多交叉的弧可以避免，整体改为（b）就比较清晰了。7图8：36（a）

内 容 7、交叉作业 两件或两件以上的工作交叉进行，称为交叉工作。如工作 A 与工作 B 分别为挖沟和 埋管子，那么它们的关系可以是挖一段埋一段，不必等沟全部挖好再埋，这就可以用交叉 作业来表示，如把这工作各分为三段，A= a1+a2+a3 , B =b1+b2+b3 ，可用图 8 . 35 表示： 如果要尽量避免弧的交叉，图 8 . 36（a）中许多交叉的弧可以避免，整体改为（b） 就比较清晰了

内容14.图8.36（b）四、给节点编号编号应注意以下规则：每条弧上起点的编号数小于终点的编号数。方法：给起点一个编号数，设想将该点为起点的弧都去掉，从而又有新的起点，依次给新的起点编号，反复这样做直到终点已经编号为止。8.6.2网络分析与计算通过网络分析可增加对项目整体的了解，并能发现活动并行执行的机会，网络分析可以分以下五个阶段：1估计完成活动需要的时间1(i,J)计算每个活动完成的平均或期望时间：根据历史数据计算平均完成时间；或通过主观估计得到完成时间的期望值2计算最早开始时间(ES)与最早完工(EF)时间从网络起点开始，用下列公式计算最早开始时间(tES)和最早完工时间(tEF)最早完工=最早开始时间+活动持续时间tEF(i,J)=tES(i,J)+t(i,J)最早开始时间=(紧前活动的)最早结束时间tES(i,J)=maxk tEF(k, i)如果一个活动有几个紧前活动，取其中最晚的最早结束时间。tES (i,)=maxk tEF (k, i)

内 容 四、给节点编号 编号应注意以下规则 : 每条弧上起点的编号数小于终点的编号数。 方法： 给起点一个编号数，设想将该点为起点的弧都去掉，从而又有新的起点，依次给 新的起点编号，反复这样做直到终点已经编号为止。 8 . 6 . 2 网络分析与计算 通过网络分析可增加对项目整体的了解,并能发现活动并行执行的机会, 网络分析可 以分以下五个阶段: 1 估计完成活动需要的时间 t (i, j) 计算每个活动完成的平均或期望时间: 根据历史数据计算平均完成时间; 或通过 主观估计得到完成时间的期望值; 2 计算最早开始时间(ES)与最早完工(EF)时间 从网络起点开始, 用下列公式计算最早开始时间(tES)和最早完工时间(tEF): 最早完工 = 最早开始时间 + 活动持续时间 tEF(i, j) = tES (i, j) + t (i, j) 最早开始时间 = (紧前活动的)最早结束时间 tES (i, j) = maxk tEF (k, i) 如果一个活动有几个紧前活动, 取其中最晚的最早结束时间。 tES (i, j) = maxk tEF (k, i)

内容tEF(i,)=tES(i,)+t(i,j)tes +t(i,j)= tEF tLFtEFitLF/tEs图8.373计算最晚开始时间与最晚结束时间从最后活动开始依次按下式计算每个活动最晚结束时间LF和最晚开始时间ILS最晚开始时间=最晚结束时间-活动持续时间tLS(i,J)=tLF(i,j)-t(i,J)最晚结束时间=（紧后活动的）最晚开始时间LF(i,J)=minktLS(,k)如果一个活动有几个紧后活动，取其中最早的最晚开始时间。tLF (i,j)=mink tLS (i,k)tLS(i,j)=tLF(i,j)-t(i,j)tes tis+t(i,j)= tLFtesTAStEstLs图8.384允许时差允许时差又称活动的机动或富裕时间.常用的时差有两种总时差：不影响总工期条件下，任务可以延迟的最大幅度，用R（i，)表示R (i,J)= tLS(i,J) - tES(i, J)=tLF (i,J) - tEF(i,)总时差=最晚开始时间－最早开始时间=最晚结束时间一最早结束时间

内 容 tEF(i, j) = tES (i, j) + t (i, j) 3 计算最晚开始时间与最晚结束时间 从最后活动开始依次按下式计算每个活动最晚结束时间 tLF 和最晚开始时间 tLS 最晚开始时间 = 最晚结束时间–活动持续时间 tLS (i, j) = tLF (i, j) - t (i, j) 最晚结束时间= (紧后活动的) 最晚开始时间 tLF (i, j) = mink tLS (j, k) 如果一个活动有几个紧后活动, 取其中最早的最晚开始时间。 tLF (i, j) = mink tLS (j, k) tLS (i, j) = tLF (i, j) - t (i, j) 4 允许时差 允许时差又称活动的机动或富裕时间,常用的时差有两种: 总时差: 不影响总工期条件下，任务可以延迟的最大幅度，用 R (i, j)表示: R (i, j) = tLS (i, j) - tES (i, j) = tLF (i, j) - tEF (i, j) 总时差 = 最晚开始时间 – 最早开始时间 = 最晚结束时间 – 最早结束时间

内容单时差：不影响紧后工作的最早开工时间的条件下，任务可以延迟的最大幅度，用r(i,)表示：r(i,j)=minktES(,k)-tEF(i,))LFEF1一一ESIS1LSESH1+单时差1S总时差图8.395确定关键路径网络计划技术根据活动持续时间之间的关系找出项目的关键活动，时差为零的活动是关键活动，它们的延误将导致整个项目完成时间延误，所有关键活动形成网络中的关键路径非关键活动是那些可在某种程度上延误而不会引起整个项目完成时间延误的活动。商业中心建设活动持续时间表活动紧前活动需要时间（周）20A设计-一10B批准8C招标A,BC24D建设D8E外装修14 F谈判A,BF10G签约6H区域分割D,GH12内装修-I,E6进驻-

内 容 单时差: 不影响紧后工作的最早开工时间的条件下, 任务可以延迟的最大幅度, 用 r (i, j)表示: r (i, j) = mink tES (j, k) - tEF (i, j) 5 确定关键路径 网络计划技术根据活动持续时间之间的关系找出项目的关键活动, 时差为零的 活动是关键活动，它们的延误将导致整个项目完成时间延误, 所有关键活动形成网络中的 关键路径, 非关键活动是那些可在某种程度上延误而不会引起整个项目完成时间延误的活 动。 商业中心建设活动持续时间表 活动 紧前活动 需要时间(周) A 设计 － 20 B 批准 － 10 C 招标 A, B 8 D 建设 C 24 E 外装修 D 8 F 谈判 A,B 14 G 签约 F 10 H 区域分割 D, G 6 I 内装修 H 12 J 进驻 I, E 6

内容H612H20824810BCDE1活动结束时间开始时间机动时间最最最早最晚晚早00A设计0202002010批准1010B0招标20202828C0建设28285252D外装修52627010E60834F谈判202842528签约344244G0H分区525258580内装修5858707010进驻70707676JEF=10LF=20BEs, 20 LS=28-FES=LS=201C：总时差=20-10=10单时差=20-10=10EF-34LF= 42Ls 42ESL34GL总时差=42-34=8.：单时差=34-34=0

内 容 活动 开始时间 结束时间 机动时间 最 早 最 晚 最早 最晚 A 设计 0 0 20 20 0 0 B 批准 0 10 10 20 10 C 招标 20 20 28 28 0 D 建设 28 28 52 52 0 E 外装修 52 62 60 70 10 F 谈判 20 28 34 42 8 G 签约 34 42 44 52 8 H 分区 52 52 58 58 0 I 内装修 58 58 70 70 0 J 进驻 70 70 76 76 0