运筹学网络计划

1、第三讲 网络计划与新产品开发(PERT/CPM）,2007年8月 龙子泉,第一节 概述,一、问题提出 通常情况下，项目的策划、安排及控制等活动包含许多独立的工作或由大量不同部门或个人负责。 由于项目大且复杂，管理人员一般难以记住与项目相关的策划、安排以及进展等所有信息； 此时，网络计划技术就能显示出极为重要的作用。,2007年8月 龙子泉,第一节 概述,二、网络计划的产生和发展 网络计划（Network Programming，NP）用网络图编制的计划称为网络计划；产生于20世纪50年代末。 网络计划技术由计划评审技术（Program Evaluation and Review Techniq

2、ue，PERT）和关键路线法（Critical-Path Method，CPM）组成。 PERT主要用于解决活动时间不确定的项目，而CPM主要是为活动时间已知或确定的项目而设计的。但由于PERT的基础是CPM，它们有时共同解决问题。因此，通常一起讨论PERT和CPM，统称为网络计划或网络计划技术（PERT/CPM）,2007年8月 龙子泉,第一节 概述,二、网络计划的产生和发展 网络计划技术主要用于解决项目的策划、安排及控制。如：新产品研制与开发、大型工程项目的建设、复杂机器的维修、新系统的设计与安装等； 网络计划被发达国家认为是当前最为行之有效的管理方法之一；实践证明：网络计划技术的应用可使

3、项目时间缩短20%左右，使成本降低10%左右；,2007年8月 龙子泉,第二节 关键路线法,一、网络计划的编制 通过一个小型案例来说明网络计划的编制过程。 例 小山购物中心的业主正在计划对其现有的32个商业购物中心进行现代化改革和扩张。该项目计划能为810个新的商业提供空间，通过私人投资，资金已到位。该购物中心的业主所需要做到的就是策划、安排和完成该扩张项目。小山购物中心扩张项目的所有活动如表所示，从A到I描述了9项活动，同时注明了每项活动的紧前活动。紧前活动表示紧接着某项活动的前项活动。,2007年8月 龙子泉,第二节 关键路线法,2007年8月 龙子泉,项目网络图的绘制,2007年8月 龙

4、子泉,项目网络图的绘制另一种画法,2007年8月 龙子泉,二、关键路线,将图1改造成图3的形式。在图中，定义： 从起点S到终点T之间的任何一个活动序列都称为一个路线，各活动的时间之和为该路线的时间，时间最长的路线称为关键路线； 举例,图3 小山购物中心项目网络图3,2007年8月 龙子泉,三、关键路线的确定,定义： ES = 一项活动的最早开始 时间 EF = 一项活动的最早结束 时间 t = 活动时间 这样有 EF = ES + t,某一活动的最早开始时间计算公式 ESi = max EFi|j J 其中 J为活动i的紧前活动的下标集,ESH = max EFC，EFB =max6，9=9,

5、2007年8月 龙子泉,同样可以得到整个网络各活动的ES和EF，如下图,三、关键路线的确定,2007年8月 龙子泉,三、关键路线的确定,定义： LS = 一项活动的最晚开始时间 LF = 一项活动的最晚结束时间 这样有 EF = ES t 某一活动的最晚结束时间计算公式 LFi = min LSi|j J 其中 J为活动i的紧后活动的下标集 即：一项活动的最晚结束时间是该项活动紧后活动中最晚开始时间的最小值； LS，LF的计算从右向左,2007年8月 龙子泉,整个网络各活动的LS和LF，如下图,三、关键路线的确定,2007年8月 龙子泉,三、关键路线的确定,定义： 松弛时间（总时差） 一项活动

6、的最晚开始时间与最早开始时间的差 或最晚结束时间与最早结束时间的差 TST = LS-ES = LF-EF 单时差在不影响紧后活动最早开始时间的条件下，活动最早结束时间可以推迟的时间； 当一项活动的松弛时间为0时，意味着如果不增加整个项目完成时间，该活动时间就不能延迟，因此： 当某一活动的松弛时间为0，则该活动为关键活动； 网络图中，由关键活动组成的从始点到终点的路线就是关键路线；图中AEFGI即为关键路线； 关键路线可能不是唯一的，在活动时间不确定的情况下，关键路线可能会发生变化； 任何一项关键活动被延迟，整个项目就会被延迟，因此，项目经理必须密切关注关键活动的进展,2007年8月 龙子泉,

7、三、关键路线的确定,小山项目的活动时间表,2007年8月 龙子泉,对于一个项目的管理工作，关键路线可以帮助我们回答如下问题： （1）完成项目总共需要的时间； 小山项目：26周 （2）每一活动的开始时间及结束时间安排； 小山项目：上表给出了各活动的ES，EF，LS，LF （3）哪些活动极为重要，需要及时完成； 小山项目：A，E，F，G，I （4）在保证整个项目完成时间不被延迟的情况下，非重要活动最多能拖延多长时间；,四、关键路线的作用,2007年8月 龙子泉,有很多软件可以对较小的项目进行计算与求解，如Management Scientist ；winQSB 等；对于大型复杂的项目，有P3，Pr

8、oject 2000等； （1） Management Scientist 对小山项目的求解 （2）winQSB 对小山项目的求解,五、关键路线的计算机求解,2007年8月 龙子泉,六、PERT/CPM 总结,第一步：列举构成项目的所有活动 第二步：决定项目中每项活动的前期活动 第三步：预期每项活动完成时间 第四步：画出项目网络图 第五步：利用网络图从左向右计算出每项活动的时间 参数ES、EF，最后一项活动的最早完成时间 就是整个项目完成所需要的时间 第六步：在上一步的基础上，从右向左计算出每项活动 的时间参数LS、LF； 第七步：计算每项活动的松弛时间TST=LS ES 第八步：找出松弛为0

9、的活动，即关键活动 第九步：设计这个项目的活动时间表,2007年8月 龙子泉,第三节 网络计划与新产品开发,新产品的研究与开发，可以将其中许多工作分解成若干活动。由于是新产品，许多活动都有很大的任意性和可变性，主要表现在这些活动的时间的不确定性。因此，新产品的研究与开发的项目通常称为活动时间不确定性的项目计划 用一个小型案例来说明整个过程,2007年8月 龙子泉,第三节 网络计划与新产品开发,案例描述 Daught 公司一直从事工业真空吸尘器系统的制造。最近，公司产品开发组建议：公司考虑生产无绳真空吸尘器。该产品被称为Porta-Vac，其可携带性和无绳的方便性将使这种产品深受大众喜爱。 公司

10、管理层希望对这种产品的可行性进行研究，以便决定是否生产这种产品。为完成该项任务，公司需从研发部、产品测试部、生产部、成本估计部以及市场研究部等部门获得信息，试图获得可行性研究需要的时间、是否可以缩短时间等相关决策信息。,2007年8月 龙子泉,第三节 网络计划与新产品开发,一、列出活动计划 根据各部门提供的信息、新产品特点和以往经验获得,2007年8月 龙子泉,二、画出网络计划图 根据上表信息画出网络计划图,2007年8月 龙子泉,三、活动时间的不确定性分析 如前所述，对于新项目或较独特的项目，要准确地估计出每项活动的时间非常困难。事实上，活动时间往往是一个较长的不确定性时间段，因此可以将其看

11、成是一个服从一定概率分布的随机变量。 1. 活动时间的随机性描述 在PERT方法中，用以下三个时间参数来描述一项活动的随机性： 乐观时间a = 每件事情进展顺利条件下的最小活动时间 最可能时间m = 正常情况下的最可能的活动时间 悲观时间b = 遇重大延误情况下的最大活动时间,2007年8月 龙子泉,三、活动时间的不确定性分析 Porta-Vac 项目的时间估计,2007年8月 龙子泉,三、活动时间的不确定性分析 2. 活动时间计算的理论基础 假设一：乐观时间与悲观时间的跨度是6个标准差，即： 6 = b a 该假设的合理性在于：很多概率分布的取值主要集中在其均值两端的3个标准差之内，即两端之

12、间的6个标准差之内。如标准正态分布，99.74%的取值均在两端之间的6个标准差之内。而6 原理常常用于产品的质量管理之中； 这样某一活动的活动时间方差的计算公式即为： 2 = (b a)/62,2007年8月 龙子泉,三、活动时间的不确定性分析 2. 活动时间计算的理论基础 假设二：各活动的活动时间的概率分布为贝塔分布，如图所示：,2007年8月 龙子泉,三、活动时间的不确定性分析 2. 活动时间计算的理论基础 假设三：项目中各活动的活动时间均为相互独立的随机变量； 若定义以各活动期望活动时间为基础的关键路线上各关键活动的期望活动时间为期望项目时间，在假设三的基础上有：期望活动时间的方差等于关

13、键路线上各活动的活动时间方差之和； 假设四：项目时间的概率分布为正态分布； 该假设的理论基础是李雅普诺夫中心极限定理,2007年8月 龙子泉,三、活动时间的不确定性分析 3. 活动时间有关参数的计算公式 某活动的活动时间方差 2 = (b a)/62 某活动的期望活动时间 te=2m+(a+b)/2/3 = (a+4m+b)/6 (假设二) 期望项目活动时间 zn = te 项目时间的方差为 n2 = 2 (假设三) 项目活动时间服从正态分布 z N(zn , n2 ) (假设四) 给定一个时间Z0 , 则项目完成时间不超过Z0的概率为 P(z Z0) = (Z0 zn)/ n ),2007年

14、8月 龙子泉,三、活动时间的不确定性分析 4. Porta-Vac 项目活动时间等有关参数计算,2007年8月 龙子泉,四、关键路线确定 1. 以上表中期望时间为基础, 计算各活动的最早开始时间和最早结束时间, 具体计算在下图中从左向右进行,2007年8月 龙子泉,四、关键路线确定 2. 在下图中从右向左进行计算各活动的最晚完成时间和晚开始时间,2007年8月 龙子泉,四、关键路线确定 3. 时间活动表,2007年8月 龙子泉,五、项目完成时间的可变性分析 从上述图表中可知，Porta-Vac 项目的关键路线为：AEHIJ，期望项目完成时间为：17周 关键路线上关键活动的可变性将导致整个项目完成时间的变动； 关键活动的可变性导致活动时间的减少将导致整个项目时间的缩短，相反，则会导致整个项目完成时间的增加； 非关键活动的可变性一般不会影响项目完成时间，但如果非关键活动启动过晚，导致延迟时间增大，非关键活动可能变成关键活动，关键路线会发生改变；整个项目是完成时间可能会延长。,2007年8月 龙子泉,五、项目完成时间的可变性分析 因为关键路线为：AEHIJ； 因此，期望项目完成时间为： EZ= tA+tE+tH+tI+tJ =6+3+4+2+2=17（周） 项目完成时间的方差为： n2 = A2 + E2 + H2 + I2 + J2 = 1.78 + 0