苏大 张芳华 运筹学课件第八章 网络计划

第八章 网络计划 Network Programming 2 2 网络计划技术 1 理解网络技术中的相关概念； 2 掌握网络图的绘制方法； 3 能够计算有关时间参数； 4 正确寻找关键路线 第八章 网络计划 3 3 网络是进行计划工作的有效工具 第八章 网络计划 4 4 横道图 时间3月4月5月6月 开题报告 英文翻译 文献查阅 论文撰写 论文答辩 优点：直观、易懂、便于检查 缺点：不能反映相互之间联系和影响 ，无法找出关键工作。 第八章 网络计划 5 5 关键路线法（CPM）:时间估计为确定型 计划评审技术（PERT）：时间估计为概率 型 上述两者统称为网络计划协调技术（PERT- CPM） 网络计划技术 第八章 网络计划 6 6 网络计划技术的优点 明确表示各项活动之间的相互联系和影响; 可找出关键路线和关键活动; 优化技术，尽量缩短工期，降低成本; 方法简便，易学易用。 第八章 网络计划 7 7 实施网络计划技术的步骤 第一阶段：绘制网络图 把工程中的各项活动的前后次序和相互关系，用一张网 络图清晰地表示出来。 第二阶段：安排日程表 根据网络图计算出每项活动的开始时间和结束时间，指 出关键活动和非关键活动，并计算机动时间。 第三阶段：控制工程的实施 第八章 网络计划 8 8 网络计划的绘制 双代号网络 活动 名称 ji 活动 时间 规则： 1、时间不可逆，故图中 不允许有回路。 2、图中不能有缺口。 3、两支箭的相关结点不 能全同。 4、必要时引入虚活动。 第八章 网络计划 9 9 虚活动（1） 21 A B 不正确 31 2 B A C 正确 第八章 网络计划 1010 虚活动（2） 不正确 正确 AC A D B B A C D B AC D E 第八章 网络计划 1111 绘制网络图的步骤 1、分解任务，列出活动关系表 2、做网络图 3、结点编号 第八章 网络计划 1212 轮船 动 力 系 统 A 段 电 气 系 统 管 道 系 统 船 体 轴 系 木 作 系 统 轮 机 系 统 上 层 房 间 B 段 C 段 D 段 E 段 F 段 G 段 H 段 K 段 钢 材 除 锈 下 料 加 工 小 组 装 配 套 存 放 大 组 装 船 台 焊 接 0 0级级 1 1级级 2 2级级 3 3级级 A A B B C C D D F F E E G G H H K K 船体分段示意图船体分段示意图 WBS举例:轮船建造 1313 生日晚会 1.0 晚宴 1.1生日蛋糕 1.2饮料 1.3清洗 1.3.1食品 1.3.2餐具 1.4做菜 1.4.1凉菜 1.4.2熟菜 1 1.4.2.1.4.2.1蔬菜类蔬菜类 1.4.2.21.4.2.2海鲜类海鲜类 1.4.2.31.4.2.3其它类其它类 2.0娱乐 2.1音响 2.2灯光布置 2.3室内布置 2.4CD/VCD光碟 1414 生日宴会WBS 1515 确定各活动的相互关系 紧前活动：只有活动A完成，才能开始活动B，则称 A为B的紧前活动； 紧后活动：B为A的紧后活动； 平行活动；若活动开始进行时，活动C也可以同时 进行，则称A和C为平行活动。 确定每项活动的活动时间 列出活动关系表 第八章 网络计划 1616 多个紧前紧后工作情况 A E C B D 1717 几种工作关系的表达(3) 搭接关系的表达 搭接关系一般用单代号网络表示 A B C D SS5 FS10FF4 1818 几种工作关系的表达(3续) 搭接关系的表达 搭接关系一般用单代号网络表示 A B C D SS5 FS10 FF4 1919 作网络图 按时间顺序从左到右排列； 起始点在图的最左边，终点在图的最右边。 第八章 网络计划 2020 活动代号活动描述紧后活动活动时间（周） A B C D E F G H I J K L 系统分析和总体设计 输入和输出设计 模块1详细设计 输入和输出程序设计 模块1程序设计 模块2详细设计 输入和输出及模块1测试 模块2程序设计 模块1测试 系统总调试 稳当编写 系统测试 B,C D E,F G,I G,I H J I,K J L 无 无 3 4 6 8 8 5 3 6 3 5 8 3 绘制网络图：某机械厂管理信息系统开发活动清单 2121 12 3 461098 57 A 3 B 4 C 6 D 8 E 8F 5 H 6 G 3 J 5 L 3 K 8 I 3 2222 关键活动 其最早开始日期不能推迟 非关键活动 其最早开始时间可以适当推迟 各项活动的参数是通过结点的时间参数来表示的。 时间参数的计算 第八章 网络计划 2323 结点和活动的最早时间 结点和活动的最迟时间 时差和关键路线 时间参数的计算 第八章 网络计划 2424 结点和活动的最早时间 最早开始时间ES ESMAX紧前工作的EF 最早结束时间EF EFES工作延续时间t 一般地，TE（1）= 0 TE（j）= max TE（i）+tij,所有的活动（i,j） TES（i,j）= TE（i） TEF（i,j）= TE（i）+ tij 第八章 网络计划 2525 A 3 E 8 C 7F 6 D 4 B 2 G 5 代号 时间 示例： 最早参数计算(练习) 2626 A 3 E 8 C 7F 6 D 4 B 2 G 5 代号 时间 示例： 最早参数计算(练习) 0 310 3 3 10 183 5 10 7 18 16 23 2727 结点和活动的最迟时间 最迟结束时间LF LFMIN紧后工作的LS 最迟开始时间LS LSLF工作延续时间t 一般地， TL（n）= TE（n） 从终点开始计算 TL（i）= min TL（j）-tij, 所有的活动（i,j） TLS（i,j）= TL（j）-tij TLF（i,j）= TLS（i,j） + tij = TL（j） 第八章 网络计划 2828 A 3 E 8 C 7F 6 D 4 B 2 G 5 代号 时间 示例： 03 35 310 37 1018 10161823 最迟参数计算(练习) 2929 A 3 E 8 C 7F 6 D 4 B 2 G 5 代号 时间 示例： 03 35 310 37 1018 10161823 最迟参数计算(练习) 2318 18 18 10 12 10 10 128 8 3 03 3030 时差和关键路线 q 总时差的计算 总时差LFEF 或 总时差LSES q 自由时差 自由时差minES(紧后工作) EF 一般地， R（i,j）= TLF（i,j）- TEF（i,j） = TL（j）- TE（i）- tij 总时差为零是关键路线的特征。 单时差（局部时差）r(i,j) r(i,j) = TE（j）- TE（i）- tij 第八章 网络计划 3131 A 3 E 8 C 7F 6 D 4 B 2 G 5 代号 时间 示例： 03 35 310 37 1018 10161823 2318 1812 1810 128 103 108 30 时差(机动时间)计算(练习) 3232 1.改进组织管理：对关键活动尽量采用平行活 动和交叉活动。 2.采用技术措施，增加投入：提高工作效率， 投入更多人力物力 。 网络计划的调整和优化工程进度的调整(介绍) 第八章 网络计划 3333 均衡使用资源主要包括： 资源一定，如何组织、安排和调配资源保证项 目按期完工。 资源不足时，如何协调内部资源和采取应急措 施(加班、雇工、增加设备、改进施工工艺)保 证项目按期完成。 资源、时间和成本的整体调整和系统优化。 网络计划的调整和优化均衡使用资源(介绍) 第八章 网络计划 3434 例如：资源的平衡（平衡前） 活动 天数 a c b 31 5 工人 25 a 2 4 6 8 c b 3535 资源的平衡（平衡后） 活动 天数 a c b 31 5 工人 25 2 4 6 8 b c a 3636 例如：工期约束下的资源均衡问题 3737 5 3 7 8 7 4 5 开 始 结束 05 03 07 513 51213171722 22171713 136 136 135 52 50 00 2 6 100 0 01 0 6 2 0 ES 最早开始 NO 活动编号 D 持续时间 LS 最迟开始 FF 自由时差 LF 最迟完成 TF 总时差 EF 最早结束 3838 最早开始进度计划相应的甘特图 5 3 7 8 7 4 5 开始结束 05 03 07 513 51213171722 22171713 136 136 135 52 50 00 2 6 100 0 01 0 6 2 0 1、最早开始进度计划 3939 35712 131722 3 5 7 9 10 13 17 资源（每天工时） 天 最早开始进度计划相应的资源需求图 4040 天 需求量（工时） 1 17 2 17 3 17 4 13 5 13 6 10 7 10 8 5 9 5 10 5 11 5 天 需求量（工时） 12 5 13 3 14 9 15 9 16 9 17 9 18 7 19 7 20 7 21 7 22 7 最早开始进度计划相应的资源需求量表 35712 131722 3 5 7 9 10 13 17 资源（每天工时） 周 4141 2、 最迟开始进度计划 最迟开始进度计划相应的甘特图 5 3 7 8 7 4 5 开始结束 05 03 07 513 51213171722 22171713 136 136 135 52 50 00 2 6 100 0 01 0 6 2 0 4242 2561317 22 3 7 8 9 10 12 资源（每天工时） 天 最迟开始进度计划相应的资源需求图 4343 天 需求量（工时） 1 8 2 8 3 12 4 12 5 12 6 3 7 10 8 10 9 10 10 10 11 10 天 需求量（工时） 12 10 13 10 14 9 15 9 16 9 17 9 18 7 19 7 20 7 21 7 22 7 最迟开始进度计划相应的资源需求量表 9 2561317 22 3 7 8 10 12 资源（每天工时） 天 4444 在该项目中，最早开始计划图与最迟开始计划图之间 存在着一定的差别。 在最迟开始计划中，对资源需求的最高点从最早开始进 度计划的第1天到第3天，转移到了第2天第5天； 资源使用的最大值也从每天17个工时减少到每天12个 工时，最小值没有改变，仍为每天3个工时； 在最迟开始计划中，该项目的资源需求的变动范围减小 到123=9个工时。 4545 资源均衡的一般操作步骤： （1）计算各阶段平均的工时数 整个项目总共需要196个工时。每 天需要19622 = 8.9个工时，为 方便起见，以每天需9个工时计。 （2）以最早开始进度计划和非关键活动为依据，从那些具有最大 自由时差的活动开始，逐渐推迟某个活动的开始时间。 3、资源均衡 5 3 7 8 7 4 5 开始结束 05 03 07 513 51213171722 22171713 136 136 135 52 50 00 2 6 100 0 01 0 6 2 0 活动的自由时差为6,最大 4646 （1）活动的最早开始时间向后推迟3天 调整了进度计划的甘特图 资源需求的最高点是1-3天 4747 10 13 7 13 3 5101722 3 5 9 12 12 资源（每天工时） 天 调整了进度计划的资源需求图 4848 天 需求量（工时） 1 12 2 12 3 12 4 13 5 13 6 10 7 10 8 10 9 10 10 10 11 5 天 需求量（工时） 12 5 13 3 14 9 15 9 16 9 17 9 18 7 19 7 20 7 21 7 22 7 10 13 7 13 3 5101722 3 5 12 12 天 9 资源（每天工时） 调整了进度计划相应的资源需求量表 4949 （2）将活动再推迟2天,即安排在活动完成之后再开始 调整了进度计划的甘特图 资源需求的最高点是4-5天 5050 9 13 8 12 351722 3 7 10 12 资源（每天工时） 天 调整了进度计划的资源需求图 5151 天 需求量（工时） 1 12 2 12 3 12 4 8 5 8 6 10 7 10 8 10 9 10 10 10 11 10 天 需求量（工时） 12 10 13 3 14 9 15 9 16 9 17 9 18 7 19 7 20 7 21 7 22 7 13 8 12 351722 3 7 10 12 资源（每天工时） 天 9 调整了进度计划相应的资源需求量表 资源的最大需求量是12个工时（每天）发生在第1天 第3天；最小的资源需求量仍然是每天3个工时。该项目 中，资源需求的变化范围减少至123 = 9个工时。 5252 （3）将活动向后推迟1天 调整了进度计划的甘特图 活动的自由时差为1 5353 10 8 12 9 7 5 3 612131722 资源（每天工时） 天 调整了进度计划的资源需求图 5454 天 需求量（工时） 1 12 2 12 3 12 4 8 5 8 6 8 7 10 8 10 9 10 10 10 11 10 天 需求量（工时） 12 10 13 5 14 9 15 9 16 9 17 9 18 7 19 7 20 7 21 7 22 7 10 8 12 7 5 3 612131722 资源（每天工时） 天 9 调整了进度计划相应的资源需求量表 5555 网络计划的调整和优化工期、成本的优化(介绍) 第八章 网络计划 c2 c1 o t2t1 突击点 正常点 成本 时间 正常时间 正常成本 突击成本：与突击时间对应的成本 突击时间：通过增加直接成本缩短时间达到一定限度，无 论成本怎么增加，工期不会缩短，这个限度称突击时间。 成本斜率： 5656 例如：时间一成本平衡法 时间成本平衡法是一种用最低的相关成本的增加来缩 短项目工期的方法 ，该方法基于以下假设： （1）每项活动有两组工期和成本估计： 正常时间（normal time）是指在正常条件下完成某项活动需 要的估计时间。 应急时间（crash time）是指完成某项活动的最短估计时间。 正常成本（normal cost）是指在正常时间内完成某项活动的 预计成本。 应急成本（crash cost）是指在应急时间内完成某项活动的预 计成本。 5757 （2）一项活动的工期可以被大大地缩短，从正常时间减 至应急时间，这要靠投入更多的资源来实现 。 （3）无论对一项活动投入多少额外的资源，也不可能在 比应急时间短的时间内完成这项活动。 （4）当需要将活动的预计工期从正常时间缩短至应急时 间时，必须有足够的资源作保证。 （5）在活动的正常点和应急点之间，时间和成本的关系 是线性的。 5858 缩短工期的单位时间成本可用如下公式计算： 例: 开始 A N=7：50000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D N=8：30000美元 C=6：42000美元 C N=10：40000美 元 C=9：45000美元 结束 注：N=正常估计；C=应急估计 5959 开始 A N=7：50000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D N=8：30000美元 C=6：42000美元 C N=10：40000美元 C=9：45000美元 结束 如果仅考虑正常工期估计 AB: 工期:16; 费用:130000 CD : 工期:18; 费用:70000 关键路径 : CD 项目周期: 18周 总费用: 200000 6060 如果全部活动均在它们各自的应急时间内完成 开始 A N=7：50000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D N=8：30000美元 C=6：42000美元 C N=10：40000美元 C=9：45000美元 结束 AB:工期:11; 费用:172000 CD : 工期:15; 费用:87000 关键路径:CD 项目周期: 15周 总费用: 259000 6161 用时间成本平衡法来压缩那些使总成本增加最 少的活动的工期，确定项目最短完成时间。 开始 A N=7：50000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D N=8：30000美元 C=6：42000美元 C N=10：40000美元 C=9：45000美元 结束 关键路径的工期决定着项目的总工期 关键路径:CD 每项活动每提前一周的成本是： 活动A：6000美元周； 活动B：10000美元周； 活动C：5000美元周； 活动D：6000美元周。 6262 为了将项目的工期从18周减至17周，首先必须找出关键路径 CD。然后，才能确定关键路径上哪项活动能以最低的每周 成本被加速。 活动C：5000美元周； 活动D：6000美元周。 开始 A N=7：50000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D N=8：30000美元 C=6：42000美元 C N=10：40000美元 C=9：45000美元 结束 9/45000 关键路径:CD 项目周期: 17 总费用: 50000+80000+45000+30000= 205000 6363 活动C：5000美元周； 活动D：6000美元周。 开始 A N=7：50000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D N=8：30000美元 C=6：42000美元 C 修=9：45000美元 C=9：45000美元 结束 关键路径: CD 项目周期: 16 总费用: 50000+80000+45000+36000=211000 为了再缩短一个时间段，从17周缩短至16周，必须再次找出 关键路径，两路径的工期分别是AB为16周，CD为17周， 因此关键路径仍是CD，它必须再次被减少。 虽然活动C比活动D每周加速成 本低，但活动C已达到它的应急 时间9周了。因此，仅有的 选择是加速活动D的进程. 7/36000(42000-6000) AB 6464 再次将项目工期缩短1周，从16周降至15周。有两条关键路 径。为了将项目总工期从16周减至15周，必须将每个路径都 加速1周。 开始 A N=7：50000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D 修=7：36000美元 C=6：42000美元 C 修=9：45000美元 C=9：45000美元 结束 AB 活动A：6000美元周； 活动B：10000美元周； CD 压缩A 压缩D 6/56000 6/42000 活动D：6000美元周。 关键路径:CD 项目周期: 15 总费用: 56000+80000+45000+42000=223000 AB 6565 从15周降至14周。有两条相同的关键路径。必须将两条路径同 时加速1周。 开始 A 修=6：56000美元 C=5：62000美元 B N=9：80000美元 C=6：110000美元 D 修=6：42000美元 C=6：42000美元 C 修=9：45000美元 C=9：45000美元 结束 路径CD，均已达到它们的应急时间。加速路径AB的进程 会毫无意义 6666 时间成本平衡 项目工期（周） 关键路径 总项目成本（美元） 18 CD 200000 17 CD 200000+5000 = 205000 16 CD 205000+6000 = 211000 15 CD，AB 211000+6000 = 223000 项目总工期减少l周，项目总成本将增加5000美元； 项目工期减少2周，项目总成本将增加l1000美元； 项目工期减少3周，项目总成本将增加23000美元。 6767 直接成本：计算相应关 键路线和总工期，通过 压缩哪些成本斜率较小 的关键活动，将每压缩 一次得到的较短工期和 较大成本的点连接起来 ，即可得到成本工期 曲线。 间接成本：按照时间分 摊，工期长，间接成本 越多。 网络计划的调整和优化工期、成本的优化(介绍) 第八章 网络计划 0 突出工期最优工期 成本 总成本 间接成本 直接成本 正常工期工期 6868 各项活动所需时间是一个预先知道的准确数，这种网络称为肯定型网 络。 各项活动时间是一个随机变量，相应的网络计划就称为非肯定型(或随 机)网络计划。 一、PERT时间分析的特点 三种时间估计值 :即对活动持续时间t做出to 、tm 、tp 三个估计 值。其理论依据是将t视为一个连续型的随机变量 （1）乐观时间（optimistic time， to） （2）最可能时间（most likely time，tm ） （3）悲观时间（pessimistic time，tp） 非肯定型网络计划 (介绍) 第八章 网络计划 6969 假定三个估计均服从概率分布（beta probability distribution）。在 这个假定基础上，由每项活动的三个时间估计可以为每项活动计算 一个期望（平均或折衷）工期（te）和方差2 。 期望值 : 方差 : 7070 例1: 一项活动的乐观时间为1周，最可能时间为5周，悲观时间为 15周，这项活动的期望工期和方差为： 其概率分布如图所示: 1 t0 5 tm 6 te 15 tp 概率 时间 二. 有关参数的计算 1. 活动的工期和方差的估计 7171 例2: 另一活动的乐观时间为10周，最可能时间为15周， 悲观时间为20周，这项活动的期望工期为： 其概率分布如图所示: 10 to 15 te 20 tp 时间 概率 7272 曲线的峰值代表了每项活动各自的最可能时间。期望工期（te）把 概率分布曲线下的总面积分成相等的两部分 ， 概率分布曲线下 50的面积在te的左边，50的面积在te的右边。 对于正态分布，期望值两边一个标准方差的范围内，曲线下面积约 占总面积的68；两个标准方差范围内，曲线下面积约占总面积的 95；三个标准差范围内，曲线下面积约占总面积的99%。 68% 平均值 123+1+2 +3 95% 99% 7373 标准差是衡量分布离散程度的尺度 下图给出了两个正态分布: a中的概率分布比b中的概率分布更宽，这样，a中分布就有较大的 标准差。 然而，对于任何两个正态分布，在其平均值两侧的一个标准差范围 内部包含了各自总面积的68% 1 +1 （a） 1 +1 (b) 7474 网络图中关键路径上的所有活动工期的总概率分布是一个正态分布 ，其均值等于各项活动期望工期之和，方差等于各项活动的方差之 和 . 例3: 考虑简单的网络图，假定项目的开始时间为0,并且必须在第40 天之前完成。每项活动工期的概率分布如图所示: B 12 34 AC 246 51315 131835 (1) 期望工期计算： 活动A： 活动B： 活动C： : 分开计算,后加总 7575 把这三个分布值加总，可以得到一个总平均值，即总的te： 总te = 在第36天之前完成项目的概率为0.5，在第36天之后完成项目的概 率也是0.5。 总te = 4+12+20=36 : 先加总,再计算 活动 to tm tp A 2 4 6 B 5 13 15 C 13 18 35 总计 20 35 56 7676 (2) 活动方差的计算： 活动A : 活动B : 活动C: 总分布是一个正态分布，它的方差是三项活动的方差之和，即: 总分布的标准差是： 总方差 = 0.444+2.778+13.444 = 16.666 7777 1 1 2 3 2 3 2