《网络计划运筹学》PPT课件.ppt

1 补充：网络计划技术 (统筹法 ) 基本概念 确定性网络计划 网络图的优化 不确定性网络计划 2020/10/14 2 一. 什么是网络计划技术 /统筹法 对于任何一项生产制造、科学实验、工程实施、军事 作战等项目活动，为了充分利用有限的时间、空间 与资源（人力、物力、财力），都必须编制一个科 学的工作组织计划来有效地组织、调度与控制该项 活动的进程，以实现最佳的效应和效益。而这种为 编制科学的组织计划的有效方法统称为统筹方法。 例 1 甲、乙两工程师从早上六时起床到上班前有一系 列活动要做。对于同样的活动过程，有人忙乱不堪， 甚至迟到，有人则又快又好，关键在于一个科学的活 动实施计划。 穿衣 刷牙 洗脸 做稀饭 热馒头 吃早饭 收拾房间 整理 出门上班 甲 出 门 上 班 穿衣 洗脸刷牙 收拾房间 整理 吃 早 饭 做稀饭 热馒头 乙 例 2 大型工程项目（三峡工程、南水北调工程、人造卫星 工程、宇航工程等）有如下活动： 产品设计、仿真、试制、中试 原材料设备定货、采购、运输、入库 厂房、设备施工建筑、安装 产品计划、生产、销售、安装、调试、维护 参与单位涉及国家各部门、各行业、事业单位，为高速 度、低成本、高质量，并在规定期限内完成该工程项目， 其关键在： 抓好科学技术 抓好项目管理，组织协调好各单位、各任务、各工 序的完成。 例 3 三军联合作战演习 空军夺取制空权，对敌实施地面攻击，运送空降兵 海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩头阵地 登陆完成后的巩固阵地与纵深发展 电子对抗部队实施情报收集分析与电子对抗 参与兵种：海军航空兵、海军陆战队、水面舰艇部队、空军 歼击机、攻击机、轰炸机、电子对抗机各团、大队，坦克、 炮兵、步兵、防化兵、通讯兵、侦察兵、导弹部队等。 需迅速订好科学的作战演习计划，以便对作战演习过程演习 过程进行有效的管理与控制。 6 网络计划 作为一个管理者，常常面临着一些复杂、大型的工程项目，这些工程项 目涉及到众多部门和单位的大量的独立的工作或活动，如何来编制计划、 安排进度并进行有力的控制，这是管理的重要内容。 统筹方法是解决这些问题的强有力的工具 关键路线法（ CPM， Critical Path Method），美国杜邦公司提出，用于协调 公司不同部门 计划评审法（ PERT， Program Evaluation and Review Technique），美国海 军武装部提出，用于导弹项目的管理和计划 目前统称为 PERT/CPM方法 统筹方法可以应用在各种不同的项目计划上，特别适用于一些跨部门的 工作计划，例如，新产品的研制开发，大型工程项目的建设，大型复杂 设备的维修以及新系统的设计与安装等计划 网络计划技术（统筹法）的功能 完成工程需做哪些工序，各工序需多长时间完成？ 总工期预计多长时间？ 完成工程的各工序采用什么样的逻辑顺序关系？关 键工作是什么？如何加快工程的完成。 环境发生变化时，该工程的风险分析。 计划网络图（ PERT图） 计划网络图 反映一个工程项目中各项作业（工序）的内在逻辑 关系的一种有向图称为计划网络图，又称统筹图， 工序流线图， PERT图等，以符号 G表示。此中“内 在逻辑关系”是指由于工程本身的工艺与组织性要 求，而对各工序提出的在时间上和空间上所要求的 先后处理关系。 10 PERT网络图 PERT网络图的一些基本概念 定义 1（工序）指任何消耗时间或资源的行动、人、财、物、工时， 用 表示。 紧前工序表示的是在另一项工序开始前，必须完成该工序 紧后工序 表示的是在一项工序结束后，立即开始的工序 定义 2（事项或事件）标志工序的开始或结束。不需消耗时间和资 源。用 表示。 定义 3（路线）指 PERT网络图中，从最初事项到最终事项的由各项 工序连贯组成的一条路。 路线的时间是路线上各工序时间的总和。 其中，各项工序累计时间最长的那条路线，决定完成网络图上所有 工序需要的最短时间，称为关键路线。 总的持续时间短于关键路线，却长于其他诸路线的路线称为次关键 路线。 其余路线称为非关键路线。 1 2 3初 步 设 计 技 术 设 计 11 确定型网络图 例：建筑项目管理 建 筑 工 程 项 目 的 工 序 一 览 表 工 序 工 序 说 明 紧 前 工 序 工 序 时 间 A B C D E F G 挖 掘 2 打 地 基 A 4 承 重 墙 施 工 B 1 0 封 顶 C 6 安 装 外 部 管 道 C 4 安 装 内 部 管 道 D ， E 5 外 墙 施 工 D 7 12 1，某公司研制新产品的部分工序与所 需时间以及它们之间的相互关系都显示 在其工序进度表如下表所示，请画出其 统筹方法的网络图 13 14 例 2：我们把例 1的进度表作一些扩充，如下表所示，请画 出其统筹方法的网络图。 6 f ?是否正确 由于 d是 f 的紧前工序，所以 d的 结束应该是 f 的开始，所以代表 f 的弧的起点应该是，但是， b工 序的结束也是 ，所以 b工序也成 了 f 工序的紧前工序，这和题意不 符合 。 15 为此引入虚工序。虚工序是实际上并不存在而虚设的 工序。仅用来表示相邻工序之间的衔接关系，虚工序 不需要人力、物力等资源与时间，在图中用虚线表示。 本例中虚工序所需时间为 0。 f 6 d 38 f 10 6 16 在网络图上添上 g， h工序就得网络图如图如下： 上图中 、两点间有 2条弧。但是 在计算机上，两点 之间不管有多少弧，都认为是一条。 因此再增加一个节点 和 引入虚工序。 17 PERT网络图的绘制 绘制 PERT网络图时，一般 从左到右，从上到下。事 项的编号，箭头处必须大 于箭尾处。 工序关系的表达方式： （ a）工序 a结束后才开始 b和 c （ b) c在 a和 b结束后才开始 （ c） a和 b均结束后才可以开 始 c和 d （ d） c在 a结束后开始， d在 a 和 b结束后才开始 18 网络时间和关键路线 在绘制出网络图之后，我们可以用网络图求出： (1)完成此工程项目所需的最少时间 (2)每个工序的开始时间与结束时间 (3)关键路线及其相应的关键工序 (4)非关键工序在不影响工程的完成时间的前提下， 其开始时间与结束时间间可以推迟多久 19 例： 某公司装配一条新的生产线，其装配过程中的各 个工序与其所需时间以及它们之间的相互衔接关系如下表 所示，求：完成此工程所需最少时间，关键路线及相应关 键工序，各工序的最早开始时间及结束时间和非关键工序 在不影响工程完成时间的前提下，其开始时间与结束时间 可以推迟多久 20 绘制网络图，如下： 21 首先从网络的始点开始，按顺序计算出每个工序的 最早开始时间 (ES)和最早结束时间 (EF)。 我们设一个工序所需时间为 t，则对同一个工序来说，有 EF ES十 t 由于工序 a最早开始时间 ES 0，所需时间 t 60，可知工序 a的最 早结束时间 EF 0+60=60。我们在网络的弧 a的上面，字母 a的右 边标上这对数据下图。 由于任一工序只有当其所有的紧前工序结束之后才能开始，所以 任一工序的最早开始时间应该等于其所有紧前工序最早结束时间 中的最后的时间。上述的等量关系我们称之为最早开始时间法则， 运用这个法则以及 EF ES t的关系，我们可以依次算出此网络图 中的各弧的最早开始时间与最早完成时间。 最早开始时间和最早结束时间的计算 22 ES, EF 在上图中，例如工序 h的最早开始时间应取工序 d和 e 的最早结束时间中的最后时间，即在 80与 100中取最大 者 100而其最早结束时间 EF ES t 100十 15 115故在弧 h上标以 100， 115 最早开始时间和最早结束时间的计算 23 其次，我们从网络图的终点开始计算出在不影响整个 工程最早结束时间的情况下各个工序的 最晚开始时间 (缩写为 LS)和 最晚结束时间 (缩写为 LF)，显然对同一工 序来说，有 LS=LF-t。 对工序 j可知其 LF=170， t=35，可计算出 LS=170- 35=135我们把这两个数据标在网络图弧 j的下面 t右边 的方括号内。 由于任一工序必须在其所有的紧后工序开始之前结束， 这样我们得到了最晚时间法则：在不影响整个工程最 早结束时间的情况下，任一工序的最晚结束时间等于 其所有紧后工序的最晚开始时间中的最早时间。 运用这个法则和 LS LF-t的关系式，我们可以从收点 开始计算出每个工序的 LF与 LS如下图所示 最晚开始时间和最晚结束时间的计算 24 例如在图中，工序 b的 LF的值是从其紧后工序 j的 LS值 得到，即工序 b的 LF 135，而工序 b的 LS的值为 LF- t=135-45 90。故在弧 b下面标以 90， 135。 LS, LF 最晚开始时间和最晚结束时间的计算 25 接着，我们可以计算出每一个工序的时差，我们把在不影响工程最 早结束的条件下，工序最早开始 (或结束 )的时间可以推迟的时间，称 为该工序的时差，对每一个工序来说其时差记为 TS，有 TS LS-ES LF-EF 例如，对工序 b来说，其时差 TS LS ES 90 60 30。 这就是说工序 b至多可以推迟 30天开始，不至于影响整个工程的最早 结束时间。我们称工序 b是非关键工序。 而对工序 g来说，其时差 TS LS ES 80 80 0。 这也就是说工序 g的提前与推迟开始 (或结束 )都会使整个工程最早结 束时间提前与推迟。我们称工序 g是关键工序。 由所有关键工序组成的线路称为关键线路（关键路径）。 最后将各工序的时差，以及其他信息构成工序时间表，如下表所示。 时差的计算 26 27 关键路径 28 用 WinQSB来求解关键路线 采用 PERT-CPM模块 29 网络图的优化 1，时间资源优化 在编制网络图计划安排工程进度时，我们要合理地 利用现有资源，并缩短工程周期为了使工程进度 与资源利用都得到比较合理安排，我们采取以下的 做法： (1)优先安排关键工序所需要的资源。 (2)利用非关键工序的时差，错开各工序的开始时间， 拉平资源需要量的高峰。 (3)要统筹兼顾工程进度的要求和现有资源的限制， 往往要经过多次综合平衡，才能得到比较合理的计 划方案。 30 下面列举一个拉平资源需要量高峰的实例在前例中，若完成工序 d， f， g， h， i的机械加工工人人数为 65人，并假定这些工人可以完成这五个 工序中的任一个工序，下面我们来寻求一个时间资源优化方案 有关 d， f， g， h， i工序所需的工人人数及上述工序开始时间，所需时 间及时差如下表所示 31 若上述各工序都按最早开始时间安排，那么从第 60天至第 135天的 75天里，所需的机械加工工人的人数如下图所示 从图可见，在第 70 80天 和第 100 110天这两段 时间，需要工人数达到 80 与 81人，远超过了现有工 人人数。 另一方面在第 90 100天 和第 115 135天所需工 人数仅有 42人和 26人，远 远少于现有工人数 这种安排的资源负荷是不 均匀的，不妥当的。 32 我们应该优先安排关键工序所需的工人，再利用非关键工序的时差，错 开各工序的开始时间，从而拉平工人需要量的高峰 经过调整，我们让非关键工序 f从第 80天开始，工序 h从第 110天开 始找到了时间 -资源优化的方案 . 如下图所示，在不增加工人的情况下保证了工程按期完成 开始时间 7080 开始时间 100100 33 2，时间费用优化问题 在编制网络计划时，我们要考虑这样一些时间与费用的问题：在 既定的时间前工程完工的前提下，使得所需要的费用最少，或者 在不超过工程预算的条件下，使得工程最早完工这些就是时 间 费用优化要研究和解决的问题 加快工程进度的一个关键概念是应急处理。应急完成工序是指通 过某些高费用的途径（如加班，雇佣临时工，使用特殊设备或材 料等），把工序的完成时间减少到正常水平之下。 应急 正常 34 时间费用的优化问题可以化为线性模型来求 解 规划问题：若考虑工程项目的成本，包括应急 费用，那么问题是在项目工期小于或等于项目 管理者期望水平的限制条件下，使得总成本最 小化。 决策： （ 1）每项工序的开始时间 （ 2） 进行应急处理后每项工序的工期减少量 （ 3）项目的期望完成时间。 35 设 xi为工序 i的最早完成时间， yi为工序 i的应急时间。假定工程开始时间 为 0，则对于工序 1，有 x1t1-y1，即 x1+y1t1，其中 t1为工序 1的正常完成 时间。 对其他紧相邻工序 i和 j，有 xj-xi tj-yj，即 xj+yj-xi tj。其中 tj为工序 j的正常 完成时间 则线性规划模型为 其中 si为工序 i的成本斜率， Ci为工序 i说允许的最大应急时间， T为工程 要求的完成时间。 36 举例： 继续前面的例子，下表给出了在装配过程中各道工序 所需正常完工时间与最快完工时间，以及对应正常完 工时间与最快完工时间的所需的直接费用和每缩短一 天工期所需增加的直接费用。 该工程要求在 150天内完工，问每个工序应比正常完工 时间提前多少天完成，才能使整个工程因缩短工期而 增加的直接费用为最少。 37 38 设此网络 图上第 i点发生的时间为 xi，工序 (i， j)提前完 工的时间为 yij，则 39 40 结果： 我们缩短工序 g的 10天工期，缩短工序 i的 10天工期，这样我 们 可以多付出最少的直接费用 6400元，提前 20天即在 150天里 完成整个工程 41 对于该问题 我们也可以用 PERT图求解。在绘制了计划网络图、计算 了工序的时间、找出关键路线之后，由于要求我们在 150天里完成工 程，缩短了正常工期的 20天时间。我们在关键路线上，找出直接费 用变动率最低的关键工序，最大限度的缩短其完成时间从前表上 可知其关键工序 a,d,g,i,j中，工序 i的直接费用变动率最低，其次是工 序 g。已知这两个工序都至多只能缩短 10天，这样我们就缩短工序 i和 g各 10天时间，而不需经缩短其他的关键工序和非关键工序就能保证 在 150天完成整个工程。为缩短这 20天的工期付出的最少的直接费用 为 290 x10 350 x10 6400。这个答案是和线性规划的答案一样的 。 2020/10/14 42 工序延续时间估计 经验法与专家法（平均值）：适用于重复性工作，不确定 性因素少 三点估计法（又称六分法） 其中 a对工序 e延续时间的最乐观时间（在顺利情况下工序 e完成的最短可能时间） b对工序 e延续时间的最悲观时间（最不顺利下工序 e 完成的最长可能时间） M对工序 e延续时间的最可能时间（在正常情况下工序 e完成耗费的时间） 验值）延续时间的估计（或试次试验）对工序 （或重复进行的第为专家其中 e jjtntT n j jje 1 6 4 bMaT e 2020/10/14 43 三点估计法 这是由于通常认为工序延续时间 ）；，（ rsba 36 )( 6 4 )1()( )( )( 2 )1()1( )(m a x 00,)()( ),()( 2 2 2 11 2 ab D bMa E M srsr rs abD sr r abaE sr sarb xfM srbaxxbax srBab f sr sr 得如下近似等式代入上述两式经化简可以 从而有 ， 2020/10/14 44 随机性网络时间参数与关键路线 问题与求解 例 (培训计划制订 ) 序号 工序 紧前 工序 乐观时间 ai 最可能 时间 mi 悲观时 间 bi 1 a - 1.5 2.0 2.5 2 0.028 2 b a 2.0 2.5 6.0 3 0.445 3 c - 1.0 2.0 3.0 2 0.111 4 d c 1.5 2.0 2.5 2 0.028 5 e b, d 0.5 1.0 1.5 1 0.028 6 f E 1.0 2.0 3.0 2 0.111 7 g b, d 3.0 3.5 7.0 4 0.445 8 h g 3.0 4.0 5.0 4 0.111 9 i f, h 1.5 2.0 2.5 2 0.028 6 4 iii bma 22 )6( iii ab 2020/10/14 45 解 1. 计算各工序的期望与方差 (见上表右 ) 2. 绘制计划网络图 6 1 2 5 3 4 6 7 8 0 2 2 5 9 13 15 i13,15 213,15 2020/10/14 46 解 3. 计算各工序的有关时间参数 ES、 LS、 EF、 LF、 R (i, j) 序号 工序 最早开始 时间 (ES) 最晚开始 时间 (LS) 最早完成 时间 (EF) 最晚完成 时间 (LF) 工序时序 R=LS ES 是否 关键工 序 1 a 0 0 2 2 0 2 b 2 2 5 5 0 3 c 0 1 2 3 1 4 d 2 3 4 5 1 5 e 5 10 6 11 5 6 f 6 11 8 13 5 7 g 5 5 9 9 0 8 h 9 9 13 13 0 9 i 13 13 15 15 0 2020/10/14 47 解 4. 寻找使 R (i, j)=0的关键工序及使 R(i)=0的对应途经节点输 出关键路线与关键工序 5. 计算总工期 T的期望和方差 E(T) = Ta+Tb+Tg+Th+Ti=CP =2+3+4+4+2=15（天） 结论 ： 1. 该计划网络 G关键路线 CP： a b g h i 2. 该计划网络 G总工期 T的期望 CP=E(T)=15天 )(025.105.1 05.1028.0111.0445.0445.0028.0 222222 天 T ingbaT 天或天 025.105.105.1 222 CPTCP 2020/10/14 48 结论：设 n为计划网络 G的工序数， CP为大型工程计 划网络 G的关键路线， T为 G的任务总工期。若 n1 ，则有： 1. ， 其中 与 分别为关键路 线 CP路长的期望与方差 2. 对 ， G在规定工期 T0内完工的概率有 aij工序（ i, j ）的最乐观时间 bij工序（ i, j ）的最悲观时间 mij工序（ i, j ）的最可能时间 总 工期的概率特性 ),( 2CPCPNT CP 2 CP 00 T 2 ),( 2 ),( 20 0 ) 6 ( 6 4 2 1 )()()( 2 CPji ijij CP CPji ijijij CP x t CP CP r abbma dtex T TTP ， ，此中 2020/10/14 49 在上例中取工期 T0分别为 15， 17， 18， 20周，求 1. 该计划网络按期 T0内完工的概率 2. 欲使按期完工的概率达到 95%或 99%，试确定相应的工程 任务总工期 T。 解： 1. 对 有 现取 T0=15，则 此中 CP=15， CP=1.025，已由上例中求得。类似地有 00 T )()( 00 CP CPTTTP 21)0()025.1 1515()15( TP 1)878.4() 025.1 1520 ( 9982.0)9269.2() 025.1 1518 (974.0)95.1() 025.1 1517 ( ， 2020/10/14 50 )(37.17025.133.215 33.2 025.1 15 99.0) 025.1 15 ()( )(68.16025.164.115 64.1 025.1 15 )1,0(95.0) 025.1 15 ()( 0 00 0 0 00 0 周 ，故有，查表有又若有 周 ，故有表有，查有 T TT TT T T N T TTP T0 15 17 18 20 P(TT0) 0.5 0.974 0.9982 1 2.欲使按期完工的概率达到 95%，则 2020/10/14 51 最关键路线与计划难易系数 定义：若在 G中有关键路线 CPi， i=1k，此中各关键路线有 对应路长的期望与方差 ， ， i=1,2k，（此中显然 有 ），若有 ，则 称 为 G的最关键路线（即方差最大的关键路线称为最 关键路线） 若 表执行最关键路线 的对应工期，则有 ， j=1k，即对任何给定工期 T0，执行最关键路线时要在 T0内完成的可能性最小，而考虑 到只有该 （最关键路线）上所有工序全部完成后工程方 能完工，因此在 G设计时应对 上的工序予以特别关注 。 lCP 2 iCPiCP 2 1 2 m a x jl CPkjCP kCPCPCP 21 )()( 00 TTPTTP jl lT lCP lCP lCP 2020/10/14 52 定义：设 T为 G的工期（随机变量）， CP为 G的关键路线， CP 与 为 CP路长的期望与方差，则称 为执行给定工期 T0的计划难易系数。 例 对于上例的计划网络 G，求解给定工期 T0分别取 13,15,17,18,20（周）时的计划难易系数 0。 解： 代入有取，将 20,18,17,15,13025.1 1522)( 00000 TTTT CP CP T0 13 15 17 18 20 0 -3.90 0 3.90 5.85 9.75 太保守，有潜力 可挖 完成可能性很大 完成可能性很大 完成可能性较大 完成可能性小 2CP CP CPTT 000 2)( 作业 某购物中心正在计划对其现有的商业购物中心进行改革和扩 张。该项目预计能提供一些新的商业空间，通过私人投资， 资金已安排到位。该购物中心的业主所需做的就是策划、安 排和完成该扩张项目，下表是所需工序一览表，试据此求出 关键路线。 表： 某购物中心工序一览表 53 工序 工序名称 紧前工序 工序时间 工序 工序名称 紧前工序 工序时间 A 设计建筑图 5 B 确定潜在租户 6 C 为租户写计划书 A 4 D 选择承包商 A 3 E 准备 建筑 许可 A 1 F 获得建筑许可 E 4 G 施工 D， F 14 H 招收租户 B， C 12 I 租户进住 G， H 2