(第八章)统筹方法.ppt

第八章统筹方法 PERT CPM 特别适用于生产技术复杂 工作项目繁多且联系紧密的一些跨部门的工作计划 如新产品开发 大型的工程项目 还可以应用在人力 物力 财力等资源的安排 PERT ProgramEvaluationandReviewTechnique 项目评审技术CPM CriticalPathMethod 关键路线法两者的区别 CPM假定每项活动的时间是确定的 而PERT假定是概率型的 PERT CPM能够回答 完成某项目总共需要多少时间 每一项特殊活动的开始日期与结束日期 为了保证项目按计划进行 哪些活动 极其重要 需要及时完成 不重要 的活动能拖延多长时间才能保证整个项目的工期不受影响 用PERT CPM编制项目计划 项目分解绘制网络图计算时间参数确定关键路线网络优化 项目分解 把项目分解为许多具体的工序 确定各工序的名称 确定各工序之间的相互衔接关系一个工序可能有几个紧前工序一个工序也可能有几个紧后工序确定各工序花费的时间对于重复性项目 管理者拥有此类项目的大量经验和历史数据 因而能精确地估计各工序花费的时间 此种情形称为确定型 用CPM方法可制定项目计划 对于较新或较独特的项目 精确估计各工序的时间非常困难 此种情形下 用一个较长的时间段来描述 而不是用一个具体的时间来描述 这种不确定型的可用PERT技术来制定项目计划 为了缩短项目工期 有些相对独立的工序可以考虑同时进行 即 平行作业 绘制网络图 一 网络图节点表示一个事件 它是一个或若干个工序的开始或结束 是相邻工序在时间上的分界点 用 表示各个节点弧表示一个工序 用表示 弧上的字母是工序的名称 数字是工序所花费的时间或资源 A 20 C 5 C工序开始 C工序结束 二 网络图的规则 相邻的两个节点之间只能有一个弧 错 网络图中不能有缺口和回路除始点和终点外 其它节点必须有箭头进 箭头出 不能有缺口 不能有回路 即不可有循环现象 错 对 引用虚工序解决平行作业问题 对 A B A B 工序时间确定型的项目 CPM方法 P241的例4 1 2 5 3 4 7 6 8 a b c d e f g h 60 15 13 38 8 10 16 5 计算时间参数 工序的最早开始时间 ES 与最早完成时间 EF 初始工序的ES 0其它工序的ES max 所有紧前工序的EF 即 工序的最早开始时间等于所有紧前工序最早完成时间的最大值工序的最晚开始时间 LS 与最晚完成时间 LF 结束工序的LF EF其它工序的LF min 所有紧后工序的LS 即 工序的最晚完成时间等于所有紧后工序的最晚开始时间的最小值 1 2 3 4 6 7 5 8 a 0 60 60 0 60 b 60 75 15 104 119 c 60 73 13 60 73 d 73 111 38 73 111 e 111 119 8 119 127 h 127 132 5 127 132 g 111 127 16 111 127 f 111 121 10 117 127 EF ES t LS LF t 确定关键路线 工序的总时差 或称容余 LS ES LF EF总时差为0的工序称为关键工序从始点到终点 依次连接关键工序形成的一条路线称为关键路线关键路线其实是从始点到终点若干条路线中最长的一条路线 它决定整个项目的工期 项目工期 关键路线上各关键工序的时间之和 用软件确定时间参数 关键路线 用关键路线程序 Route exe 求解输入工序的总数量 25个 各工序所需的时间 各工序的紧前工序输出各工序的ES EF LS LF 时差 是否是关键工序关键路线项目的工期 工序时间不确定的项目 PERT技术 工序时间不确定 可以通过评估三种时间来近似找到工序的平均时间乐观时间O 在顺利情况下工序所需的最少时间 最可能时间M 在正常情况下工序所需的最可能时间 悲观时间P 在不顺利情况下工序所需的最长时间 工序的平均时间T O 4M P 6工序的方差 P O 6 2项目的平均工期 关键路线上各关键工序的平均时间之和项目的方差 关键路线上各关键工序的方差之和关键工序的时间变动性导致整个项目工期的变动性 但整个项目工期服从正态分布 六分之一原则 波动性大小的度量 P248例6 关键路线 由a b g h i组成项目的平均工期和方差E T 15 周 方差 1 05该项目的工期服从均值为15 方差为1 05的正态分布项目在12周内完成的概率 15 12 1 05 2 927个标准差 查表知2 927个标准差对应的概率为0 0018 即项目在12周内完成的概率为0 18 说明 几乎不可能在12周内完成 项目在17周内完成的概率 17 15 1 05 1 95个标准差 查表知1 95个标准差对应的概率为0 9744 即项目在17周内完成的概率为97 44 说明 17周内完成的可能性相当大 网络优化 一 项目时间的调整项目的延误关键工序的时间比预期的延长多少天 整个项目的工期就要延长多少天非关键工序的时间延长若不超过其时差 则不影响项目工期非关键工序的时间延长若超过其时差 关键路线就改变 此时先前的非关键工序变为关键工序 项目将被延误 延误的天数取决于超过时差的数量 项目的时间压缩只有压缩关键工序的时间才能压缩整个项目的工期 而压缩非关键工序不会影响整个项目的工期但是 如果不断压缩关键工序 必然会到达一点 此时网络的其他路线成为关键路线了 当关键路线上的时间压缩超过了并行路线的时差时 并行路线就变为关键路线了 下图项目网络中 项目工期为14天 关键路线为A B C 如何将项目工期压缩到13天 11天 9天 压缩到13天 关键路线ABC上压缩1天压缩到11天 关键路线ABC上压缩2天 此时DEF也变为关键路线了 在DEF和ABC上再各压缩1天 压缩到9天 关键路线ABC上压缩2天 此时DEF也开始变为关键路线了 在DEF和ABC上再各压缩2天 此时 GHI又开始变为关键路线了 在GHI DRF和ABC上再各压缩1天 H4 三条路线 DEF 工期12 时差为2 ABC 工期14 时差为0 关键路线GHI 工期10 时差为4 二 考虑费用的时间压缩 时间 费用优化 项目的总费用 直接费用 间接费用 处罚成本压缩项目工期 间接费用和处罚成本减少 但直接费用增加需要在项目工期与总费用两者之间做权衡 项目没有按规定时间完成 人工和设备费用 管理和资金费用 P256例7要压缩20天 并行路线的时差分别为20和30 在关键路线adgij上压缩20天不超过并行路线的时差 故只在关键路线adgij上压缩即可 选择关键路线adgij上单位直接费用最低的工序i压缩10天 再选择单位直接费用次低的工序g压缩10天 直接费用增加290 10 350 10 6400最小要压缩30天 需要在关键路线adgij上压缩20天 同上 此时并行路线aehj成为关键路线了 在aehj上再压缩10天 选择关键路线上单位直接费用最低的工序i压缩10天 再选择单位直接费用次低的工序g压缩10天选择新的关键路线aehj上单位直接费用最低的工序h压缩5天 在单位直接费用次低的工序e上压缩5天增加的直接费用290 10 350 10 400 5 500 5 14900最小 压缩的线性规划模型 设xa 工序a的最早完成时间 ya 工序a的压缩数量 活动a的最早开始时间为0 故有 xa 0 60 ya 工序b的最早开始时间 工序a的最早完成时间xa 故类似的 xb xa 45 yb 依次有xc xa 10 yc xd xa 20 yd xe xa 40 ye 对于工序j xj xb 35 yj 且xj xf 35 yj 且xj xi 35 yj 且xj xh 35 yj xj 150 ya 0 yb 15 yc 5 yd 10 yj 0目标函数min 120yb 300yc 400yd 500ye 230yf 350yg 400yh 290yi P260例8 项目费用最小化问题 目标函数 压缩调整后的总费用 原工期总费用 由于压缩导致额外增加的直接费用与额外减少的间接费用minz 125000 120yb 300yc 400yd 500ye 230yf 350yg 400yh 290yi 330 170 xj s t 同前 去掉xj 150 工期为170 正常情况下 时 项目的总费用 直接费用 间接费用 1 0 45 0 375 0 625 1 2 0 033 170 12 5万 工期为最优时间160天 工序i压缩 其它工序正常 项目的总费用 直接费用 间接费用 1 0 45 0 375 0 915 1 2 0 033 160 12 46万 三 时间 资源优化 资源平整 60 70 80 90 100 110 120 130 140 d f g h i 示例工序时间工序容余 58人 80人 64人 42人 81人 65人 26人 工序推后进行平整资源用量 甘特图 资源用量图 时间 第十章动态规划 解决多阶段决策过程最优化 只是求解某类问题的一种方法 是考察问题的一种途径 而不是一种特殊算法 如线性规划是一种算法 因而没有一个标准的数学表达式和明确定义的一组规则 必须对具体问题进行具体分析处理 动态规划方法的基本思想 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件 即基本方程 所以 必须先将问题的过程分成几个相互联系的阶段 恰当地选取状态变量和决策变量及定义最优值函数 从而把一个大问题化成一族同类型的子问题 然后逐个求解 动态规划的应用 定价问题 例 某厂要确定一种新产品在今后五年内的价格 并已拟定只在5 6 7 8元这四种单价中进行选择 据预测 今后五年不同价格下每年盈利 万元 如下表所示 但是各相邻年度价格不得