运筹学网络计划

1、1第九章网络计划第九章网络计划 9.1 网络图网络图 9.2 时间参数计算时间参数计算 9.3网络计划的优化网络计划的优化2 大型项目的开发涉及很复杂的项目协调大型项目的开发涉及很复杂的项目协调和管理问题，为使项目管理人员对项目进度和管理问题，为使项目管理人员对项目进度有全面的了解，进行有效的控制，必须使用有全面的了解，进行有效的控制，必须使用科学的管理方法科学的管理方法. 网络计划法是使用最广泛的方法之一，网络计划法是使用最广泛的方法之一，关键路径法关键路径法(CPM)和项目评审技术和项目评审技术(PERT)是是两种使用最广泛的网络计划技术。两种使用最广泛的网络计划技术。3 网络计划方法的优

2、点使它适用于生产技网络计划方法的优点使它适用于生产技术复杂，工作项目繁多，且紧密联系的一些术复杂，工作项目繁多，且紧密联系的一些跨部门的工作计划，如：跨部门的工作计划，如： 新产品研制开发新产品研制开发 大型工程项目建设大型工程项目建设 生产技术准备生产技术准备 复杂设备的大修计划复杂设备的大修计划4网络计划方法的基本原理网络计划方法的基本原理 将工程项目分解为相对独立的活动，根将工程项目分解为相对独立的活动，根据各活动先后顺序、相互关系以及完成所需据各活动先后顺序、相互关系以及完成所需时间做出反映项目全貌的网络图；从项目完时间做出反映项目全貌的网络图；从项目完成全过程着眼，找出影响项目进度的

3、关键活成全过程着眼，找出影响项目进度的关键活动和关键路线，通过对资源的优化调度，实动和关键路线，通过对资源的优化调度，实现对项目实施的有效控制和管理。现对项目实施的有效控制和管理。5网络计划方法的主要功能网络计划方法的主要功能 1 用网络图描述一个实际项目的管理问用网络图描述一个实际项目的管理问题题 (画网络图画网络图) ; 2 计算项目的最早、最晚完成和开工时计算项目的最早、最晚完成和开工时间间 (网络计算网络计算) ; 3 寻找关键活动和关键路径寻找关键活动和关键路径(网络分析网络分析); 4 根据以上分析对网络进行优化。根据以上分析对网络进行优化。6 复杂工程项目可被分解为一系列小的事复

4、杂工程项目可被分解为一系列小的事件或活动，各种事件和活动之间的逻辑顺序件或活动，各种事件和活动之间的逻辑顺序可以表述为一个由一系列弧和节点组成的网可以表述为一个由一系列弧和节点组成的网络图；络图； 网络图中的有向弧代表各种活动网络图中的有向弧代表各种活动(或工或工作作), 活动完成需要的时间写在弧上；活动完成需要的时间写在弧上； 节点表示事件节点表示事件 (或事项或事项), 表示活动的开表示活动的开始与结束始与结束, 每个节点有唯一节点号；每个节点有唯一节点号；7 位于弧的起点和终点的节点表示活动或位于弧的起点和终点的节点表示活动或事件的开始和结束事件的开始和结束, 每个活动有一每个活动有一

5、个起点和一个起点和一个终点个终点:125a 圆圈和里面的数字代表各事项，写在箭圆圈和里面的数字代表各事项，写在箭杆中间的数字杆中间的数字 5 表示完成本工作所需时间，表示完成本工作所需时间，即工作即工作 a ( 1 , 2 )，事项：，事项： ( 1 , 2 )。图图 9 . 18 整个网络的方向按惯例从左到右地反映整个网络的方向按惯例从左到右地反映活动的逻辑顺序活动的逻辑顺序, 并有唯一的起点和终点。并有唯一的起点和终点。 虚工作用箭线虚工作用箭线“ ” 表示。它表示。它表示工时为零，不消耗任何资源的虚构工作。表示工时为零，不消耗任何资源的虚构工作。其作用只是正确表示工作的前行后继关系。其作

6、用只是正确表示工作的前行后继关系。画网络图有以下四个阶段画网络图有以下四个阶段:一、列出所有活动一、列出所有活动 一个完整的项目必须被分解为一系列独立一个完整的项目必须被分解为一系列独立9活动（称为工序）活动（称为工序）, 分解程度取决于项目计划分解程度取决于项目计划的需要以及相应的管理职能。的需要以及相应的管理职能。二、确定每个活动的紧前工序二、确定每个活动的紧前工序 项目执行的连续性确定了项目各项活动项目执行的连续性确定了项目各项活动的前后顺序的前后顺序, 为了从逻辑上搞清楚活动之间的为了从逻辑上搞清楚活动之间的顺序关系顺序关系, 需要需要确定每项活动可以开始之前必确定每项活动可以开始之前

7、必须完成的活动须完成的活动紧前工序。紧前工序。 区分习惯上发生的顺序和它们在逻辑区分习惯上发生的顺序和它们在逻辑上应该发生的顺序上应该发生的顺序, 例如例如, 寄出一个发票的一般寄出一个发票的一般10方法是方法是: (1) 检查发票检查发票 (2) 将发票放入信封将发票放入信封 (3) 封上信封封上信封 (4) 在信封上写地址在信封上写地址这不是唯一正确方法这不是唯一正确方法, 网络图应能反映网络图应能反映所有可能性所有可能性, 而不仅仅是传统方法。而不仅仅是传统方法。三、画网络图三、画网络图 画网络图应注意以下规则画网络图应注意以下规则:111、网络只能有一个总起点和一个总终点、网络只能有一

8、个总起点和一个总终点;123456789 图图 9. 2中，有两个总起点事项中，有两个总起点事项， ；三个总终点事项三个总终点事项，不符合规则。，不符合规则。图图 9 . 2122、网络图为有向图、网络图为有向图, 且不能有回路；且不能有回路；1234567 图图9. 3 中中 是回路，不是回路，不符合规则符合规则图图 9 . 3133、两个节点之间不能有两条或两条以上的弧、两个节点之间不能有两条或两条以上的弧（两个及两个以上的工作）（两个及两个以上的工作）;12ab图图9 . 4 不符合规则。不符合规则。4、应正确表示活动之间的前行后继关系、应正确表示活动之间的前行后继关系;如如 4 道工作

9、道工作a , b , c , d 的关系为：的关系为： c 必须在必须在a , b 均完成后才能开工，而均完成后才能开工，而 d 只要在只要在 b 完工后完工后图图 9 . 414即可开工，如画成下图是错误的，因本来与即可开工，如画成下图是错误的，因本来与 a 工作无关的工作无关的d 被错误地表为必须在被错误地表为必须在 a 完工完工后才能开工。后才能开工。a12345bcd5、虚拟活动的运用、虚拟活动的运用 网络有时需要包括由虚线表示的网络有时需要包括由虚线表示的虚拟虚拟 活活图图 9 . 515动。首先动。首先, 它可以避免两个活动有相同的起点它可以避免两个活动有相同的起点和终点和终点;

10、其次其次, 使用虚拟活动可以帮助表示一使用虚拟活动可以帮助表示一些特殊的逻辑依赖关系。些特殊的逻辑依赖关系。如前面不符合规则的如前面不符合规则的图图 9 . 4 ，图，图 9 . 2，图，图 9 . 5，用添加虚工作的方法改图为，用添加虚工作的方法改图为图图 9 . 6，图，图 9 . 7，图，图 9 . 8就是正确的了。就是正确的了。132ab图图 9 . 616132456789 图图 9 . 7图图 9 . 8123456abcd176、平行工作、平行工作 虚工作还可以用于正确地表示平行工作与虚工作还可以用于正确地表示平行工作与交叉工作。一道工作分为几道工作同时进行，交叉工作。一道工作分

11、为几道工作同时进行，称为平行工作，如图称为平行工作，如图图图9 . 9（a）中市场调查中市场调查（2，3）中需）中需12天，如增加人力分为三组同天，如增加人力分为三组同时进行，可画为（时进行，可画为（b）。）。143212（市场调研）（市场调研） 图图 9 . 9（a）184123456（调（调2）44（调（调1）（调（调3）图图9 . 9（b）7、交叉作业、交叉作业两件或两件以上的工作交叉进行，称为交叉两件或两件以上的工作交叉进行，称为交叉工作。如工作工作。如工作 A 与工作与工作 B 分别为挖沟和埋管分别为挖沟和埋管子，那么它们的关系可以是挖一段埋一段，子，那么它们的关系可以是挖一段埋一段

12、，不必等沟全部挖好再埋，这就可以用交叉作不必等沟全部挖好再埋，这就可以用交叉作19业来表示，如把这工作各分为三段，业来表示，如把这工作各分为三段，A= a1+a2+a3 , B =b1+b2+b3 ，可用，可用图图 8 . 35表示：表示：1234567a1a2a3b1b2b3 图图9. 10 8、要尽量避免弧的交叉，、要尽量避免弧的交叉，图图 9 . 10（a）中）中许许多交叉的弧可以避免，整体改为（多交叉的弧可以避免，整体改为（b）就比较）就比较清晰了。清晰了。201234567891011121314图图 9 . 10（a）211234567891011121314 图图 9 . 10（

13、b）22四、给节点编号四、给节点编号 编号应注意以下规则编号应注意以下规则 : 每条弧上起点的每条弧上起点的编号数小于终点的编号数。编号数小于终点的编号数。 编号不一定要连续，留些间隔便于修改编号不一定要连续，留些间隔便于修改和增加工作。和增加工作。方法：方法： 给起点一个编号数，设想将该点为起点的弧给起点一个编号数，设想将该点为起点的弧都去掉，从而又有新的起点，依次给新的起点都去掉，从而又有新的起点，依次给新的起点编号，反复这样做直到终点已经编号为止。编号，反复这样做直到终点已经编号为止。23商业中心建设活动表商业中心建设活动表活动活动 紧前活动紧前活动 A 设计设计 B 获规划局批准获规划

14、局批准 C 招标招标/选择承包商选择承包商A , B D 商厦建设商厦建设C E 外部装修外部装修D F 与商业机构谈判与商业机构谈判A , B G 与商业机构签约与商业机构签约F H 使用区域分割使用区域分割D , G I 内部装修内部装修 H J 进驻进驻I , E24商业中心建设网络图商业中心建设网络图410JI6F8H132ABC7G5D9E25错误的依赖关系错误的依赖关系9314510628ABCDGHEFJI26 通过网络分析可增加对项目整体的了解通过网络分析可增加对项目整体的了解,并并能发现活动并行执行的机会能发现活动并行执行的机会, 网络分析可以网络分析可以分以下五个阶段分以下

15、五个阶段:1 估计完成活动需要的时间估计完成活动需要的时间 t (i, j)计算每个活动完成的平均或期望时间计算每个活动完成的平均或期望时间: 根据历史数据计算平均完成时间根据历史数据计算平均完成时间; 或通过或通过主观估计得到完成时间的期望值主观估计得到完成时间的期望值;272 计算最早开始时间计算最早开始时间(ES)与最早完工与最早完工(EF)时间时间从网络起点开始从网络起点开始, 用下列公式计算最早开用下列公式计算最早开始时间始时间(tES)和最早完工时间和最早完工时间(tEF): 最早完工最早完工 = 最早开始时间最早开始时间 + 活动持续时间活动持续时间 tEF(i, j) = tE

16、S (i, j) + t (i, j) 最早开始时间最早开始时间 = (紧前活动的紧前活动的)最早结束时间最早结束时间tES (i, j) = maxk tEF (k, i)如果一个活动有几个紧前活动如果一个活动有几个紧前活动, 取其中最取其中最晚的最早结束时间。晚的最早结束时间。28tES (i, j) = maxk tEF (k, i) tEF(i, j) = tES (i, j) + t (i, j)tEStEFtEFtLFtLFtES+ t (i, j) =图图9 . 11293 计算最晚开始时间与最晚结束时间计算最晚开始时间与最晚结束时间 从最后活动开始依次按下式计算每个活从最后活动

17、开始依次按下式计算每个活动最晚结束时间动最晚结束时间 tLF 和最晚开始时间和最晚开始时间tLS 最晚开始时间最晚开始时间 = 最晚结束时间最晚结束时间活动持续时活动持续时间间tLS (i, j) = tLF (i, j) - t (i, j)最晚结束时间最晚结束时间= (紧后活动的紧后活动的) 最晚开始时间最晚开始时间 tLF (i, j) = mink tLS (j, k)如果一个活动有几个紧后活动如果一个活动有几个紧后活动, 取其中取其中最早的最晚开始时间最早的最晚开始时间。30tLF (i, j) = mink tLS (j, k)tLS (i, j) = tLF (i, j) - t

18、 (i, j)tLStEStLFtES+ t (i, j) =tLStEStLS图图 9 . 12314 允许时差允许时差允许时差又称活动的机动或富裕时间允许时差又称活动的机动或富裕时间,常用的时差有两种常用的时差有两种:总时差总时差: 不影响总工期条件下，任务可不影响总工期条件下，任务可以延迟的最大幅度，用以延迟的最大幅度，用R (i, j)表示表示: R (i, j) = tLS (i, j) - tES (i, j) = tLF (i, j) - tEF (i, j)总时差总时差 = 最晚开始时间最晚开始时间 最早开始时间最早开始时间 = 最晚结束时间最晚结束时间 最早结束时间最早结束时

19、间32w单时差单时差: 不影响紧后工作的最早开工时间不影响紧后工作的最早开工时间的条件下的条件下, 任务可以延迟的最大幅度任务可以延迟的最大幅度, 用用r (i, j)表示表示: r (i, j) = mink tES (j, k) - tEF (i, j)LFEFLSESLSES总时差总时差单时差单时差图图 9 . 13335 确定关键路径确定关键路径网络计划技术根据活动持续时间之间网络计划技术根据活动持续时间之间的关系找出项目的关键活动的关系找出项目的关键活动, 时差为零的活时差为零的活动是关键活动动是关键活动，它们的延误将导致整个项目它们的延误将导致整个项目完成时间延误完成时间延误, 所

20、有关键活动形成网络中的所有关键活动形成网络中的关键路径关键路径, 非关键活动是那些可在某种程度非关键活动是那些可在某种程度上延误而不会引起整个项目完成时间延误的上延误而不会引起整个项目完成时间延误的活动。活动。34商业中心建设活动持续时间表商业中心建设活动持续时间表活动活动 紧前活动紧前活动 需要时间需要时间(周周)A 设计设计20B 批准批准 10C 招标招标A, B 8D 建设建设C24E 外装修外装修D 8F 谈判谈判A,B14G 签约签约F10H 区域分割区域分割D, G 6I 内装修内装修 H12J 进驻进驻I, E 635ABCDGHEFJI314591062871020 824

21、861410612 0202028523452587076587052524276282020 036 活动活动 开始开始 时间时间 结束时间结束时间 机动时间机动时间 最早最早 最晚最晚 最早最早 最晚最晚A 设计设计 0 02020 0B 批准批准 010102010C 招标招标20202828 0D 建设建设28285252 0 E 外装修外装修5262607010 F 谈判谈判20283442 8 G 签约签约34424452 8 H 分区分区52525858 0 I 内装修内装修58587070 0 J 进驻进驻70707676 0 总总单时差单时差01000100800037 网络

22、图上时间表示法：网络图上时间表示法：最早开始，需要时间，最早结束最早开始，需要时间，最早结束最晚开始，最晚开始， 时时 差差 ，最晚结束，最晚结束38LF = 42EF = 34LS = 42ES = 34总时差总时差 = 42 - 34 = 8单时差单时差 = 34 - 34 = 0 FGLF = 20EF = 10LS = 28ES = 20总时差总时差 = 20 - 10 = 10单时差单时差 = 20 - 10 = 10 BFCES =LS = 2039 关键工序有：关键工序有：A、 C、 D、 H、 I、 J 关键路径为：关键路径为：1234578910401234567891011

23、121314743565865486735846075111091118141916262430 26 24 30 16 19 23 19 11 13 10 14 7 5041练习：工序 紧前工序工序时间/d工序紧前工序 工序时间/dag,m3gb,c2bh4h-5c-7ia,l2dl3kf,i1ec5lb,c7fa,e5mc3要求要求：（1）绘制网络图；）绘制网络图；（2）计算各工序的最早开工、最早完工、最迟开工、最迟）计算各工序的最早开工、最早完工、最迟开工、最迟完工时间及总时差、单时差，并指出关键工序。完工时间及总时差、单时差，并指出关键工序。42 关键工序：hbgafk13247856

24、91011c7e5f5k1i2d3a3l7b4h5005578161711141414141416171919202099m3g2439.3 网络计划的优化网络计划的优化 一、不确定因素的处理一、不确定因素的处理 大型项目活动的完成时间分布具有单峰和对称性，大型项目活动的完成时间分布具有单峰和对称性，这与这与 分布很接近，根据这一假定可以得到以分布很接近，根据这一假定可以得到以下近似计算公式：下近似计算公式：（1）每项活动的期望完成时间为：）每项活动的期望完成时间为： 期望完成时间期望完成时间= 乐观乐观+4最可能最可能+悲观悲观644 （2）活动完成时间的方差：）活动完成时间的方差：26乐观

25、时间悲观时间方差 （3）项目完成时间的方差：）项目完成时间的方差： 项目方差项目方差=每个关键活动方差之和每个关键活动方差之和 （4）项目完成时间的标准差：）项目完成时间的标准差： 标准差标准差2=项目方差项目方差45 （5）如果项目由许多独立活动组成，整个项目）如果项目由许多独立活动组成，整个项目完成时间的分布符合正态分布，期望值是项目的完成时间的分布符合正态分布，期望值是项目的期望完成时间，标准差由（期望完成时间，标准差由（d)计算，置信区间可计算，置信区间可以用经验公式计算，以用经验公式计算，95%的置信区间位于期望值的置信区间位于期望值加减两倍标准差之间：加减两倍标准差之间： 95%置

26、信区间置信区间=期望时间期望时间2标准差标准差 如果需要其它的或者更精确的置信区间，需如果需要其它的或者更精确的置信区间，需要查正态分布曲线表；要查正态分布曲线表；46二、网络优化二、网络优化 网络优化是指通过网络方案的调整，达到网络优化是指通过网络方案的调整，达到缩短工期，节约资源，减低成本的目的，缩短工期，节约资源，减低成本的目的，使用的方法为：使用的方法为：1、寻找并行作业的机会、寻找并行作业的机会2、利用作业时差、利用作业时差3、合理分配资源、合理分配资源47（一）缩短工程进度（一）缩短工程进度 在现有资源的条件下，缩短工程进度的主要途径有：在现有资源的条件下，缩短工程进度的主要途径有

27、：（1）采取适当的技术措施，组织力量对关键工序进行攻关，）采取适当的技术措施，组织力量对关键工序进行攻关，压缩关键工序的工序时间。压缩关键工序的工序时间。（2）改变工序：在工艺流程允许的条件下，把关键路线上）改变工序：在工艺流程允许的条件下，把关键路线上串联的关键工序改为平行工序或交叉工序，合理调配工程串联的关键工序改为平行工序或交叉工序，合理调配工程技术人员，缩短工期。技术人员，缩短工期。（3）利用时差：由于非关键工序都有时差，所以这些工序）利用时差：由于非关键工序都有时差，所以这些工序在开工时间上、具体工时上都有一定得弹性。因此从非关在开工时间上、具体工时上都有一定得弹性。因此从非关键工序

28、上抽调部分人力、物力到关键工序上，缩短关键工键工序上抽调部分人力、物力到关键工序上，缩短关键工序的时间。序的时间。48（二）有限资源的合理分配（二）有限资源的合理分配 在编制网络计划时，合理安排有限资源，通常是在编制网络计划时，合理安排有限资源，通常是按照每单位时间的需要量，根据资源对完成工程按照每单位时间的需要量，根据资源对完成工程计划的重要性，对不同的资源合理安排的一般算计划的重要性，对不同的资源合理安排的一般算法。法。 调整得基本原则是：调整得基本原则是：（1）尽量保证关键工序的单位资源需求量；）尽量保证关键工序的单位资源需求量；（2）利用非关键工序的时差错开各工序的使用资）利用非关键工

29、序的时差错开各工序的使用资源时间；源时间；（3）在技术规则允许的条件下，可适当延长时差）在技术规则允许的条件下，可适当延长时差大的工序的工时，或切断某些非关键工序，以减大的工序的工时，或切断某些非关键工序，以减少日总需求量。少日总需求量。49（三）最低成本日程（三）最低成本日程 项目或任务的成本一般可以分成两类：项目或任务的成本一般可以分成两类：（1）直接费用：如完成各项工作直接所需人力、资）直接费用：如完成各项工作直接所需人力、资源、设备等费用。源、设备等费用。在一定范围内，工序的作业时间越短，直接费用越大。在一定范围内，工序的作业时间越短，直接费用越大。（2）间接费用：如管理人员的工资、办

30、公费、采购）间接费用：如管理人员的工资、办公费、采购费用、设备租金等。费用、设备租金等。在一定条件下，工序时间长，间接费用越大。在一定条件下，工序时间长，间接费用越大。 通过计算网络计划的不同完工期相应的总费用，以通过计算网络计划的不同完工期相应的总费用，以求得成本最低的日程安排就是：求得成本最低的日程安排就是：“最低成本日程最低成本日程”，又称又称“工期工期成本优化成本优化”。50网络的加急分析网络的加急分析 时间成本替代关系加急成本正常成本加急时间正常时间斜率（加急比率）：即每缩短一天需增加的费用。斜率（加急比率）：即每缩短一天需增加的费用。51 单位时间加急成本是加急成本增量与减少单位时

31、间加急成本是加急成本增量与减少时间之比率，从这一比率出发可以找到一时间之比率，从这一比率出发可以找到一最低成本达到缩短项目总完成时间的活动，最低成本达到缩短项目总完成时间的活动，这样的活动在进行网络加急分析时应首先这样的活动在进行网络加急分析时应首先考虑。考虑。 在例在例9.1中打算中打算56周完成，考虑怎样调整使周完成，考虑怎样调整使增加的成本最少。增加的成本最少。52正常正常时间时间正常正常成本成本加急加急时间时间加急加急成本成本最大最大减少减少成本成本/时间时间比率比率A*2030128086.25B101010100-C*81061623.0D*242300202340410.0E81

32、10412042.5F1412102042.0G10808800-H*62022541.25I*121601017025.0J*6106100-53 只有关键活动才考虑进行加急处理；只有关键活动才考虑进行加急处理； 检查关键路径上的活动找出有最小加急成检查关键路径上的活动找出有最小加急成本的活动；本的活动； 减少该活动的完成时间直到达到最大可能减少该活动的完成时间直到达到最大可能的减少时间，或者另一个并行路径也称为的减少时间，或者另一个并行路径也称为关键路径；关键路径； 关键活动关键活动H有最小的加急比率，它可减少有最小的加急比率，它可减少4周而不改变关键路径，项目完成时间减到周而不改变关键路

33、径，项目完成时间减到72周，成本增加周，成本增加5万；万；54HG410JI6F8132ABC75D9E52, 8,6062,10,70 0,20,20 0, 0,20 0,10,1010,10,2020, 8,2820, 0,2824,24,5228, 0,5270, 6,7670, 0,7620,14,3428, 8,4234,10,4442, 8,5252, 6,5852, 0,5858,12,7058, 0,7055 0,20,20 0, 0,20HG410JI6F8132ABC75D9E52, 8,6058, 6,66 0,10,1010,10,2020, 8,2820, 0,282

34、4,24,5228, 0,5266, 6,7266, 0,7220,14,3428, 8,4234,10,4442, 8,5252, 2,5452, 0,5454,12,6654, 0,6656 重新检查所有活动，下一个有最小加急成重新检查所有活动，下一个有最小加急成本的活动本的活动C可减少可减少2周，完成时间可降到周，完成时间可降到70周，成本再增加周，成本再增加6万元；万元； 下一个有最小加急成本的活动下一个有最小加急成本的活动 I 可减少可减少2周，周，完成时间进一步降到完成时间进一步降到68周，成本再增加周，成本再增加10万元；万元；57HG410JI6F8132ABC75D9E50, 8,5850, 6,64 0,10,1010,10,2020, 6,2620, 0,2626,24,5026, 0,5064, 6,7064, 0,7020,14,3426, 6,403