数学模型3-4关键路径分析.pdf

3 4 关键路径分析 CPA 和计划 评审技术 PERT 关键路径分析算法 赶工优化问题 引言 中学课本华罗庚先生的一篇文章 统筹方 法 如何有效地安排各项活动的顺序 历史 CPM 1956年 美国杜邦公司 PERT 1958年 美国海军特种计划局 PDM Precedence Diagramming Method 1964年 美国IBM公司 现代应用 项目管理 TCP IP网络分析 项目管理 数据采集 项目活动组成 每项活动和其他活动之间的依存关系 每项活动需要延续的时间 目标 如何安排项目活动最节约时间 最 经济 一个例子 编号活动前期活动延续时间 1地基无4 0 2挖沟无1 7 3管线22 0 4砌砖1 2 315 0 5喷绘44 8 6木工48 4 7屋顶610 0 图形表示 Activity on arc AOA Activity on node AON AOA 表示 每项活动以图形的边表示 活动的延续时间作为边的权 节点代表两个活动间的连接点 人为加入 开始 和 结束 节点 需要加入空边以表示活动的依存关系 AOA 表示 例子 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 屋顶10 这里粉红色的线不代表任何活动 只是为了 表示活动的依存关系 AON 表示 每个节点代表一项活动 有向弧表示活动之间的依存关系 表示一 项活动是另一项活动的前提条件 顶点的值表示活动延续时间 人为引进 开始 和 结束 节点 AON 表示 例子 4 0 开始 地基 挖沟 管线 砌砖 喷绘 木工 屋顶 结束 1 7 2 0 15 4 8 8 4 10 总工期问题 从开工到结束至少需要多长时间 说明 乍一看似乎是一个最 短 路径问题 但由于PERT图的特殊性 只有当前的活动 结束后后面的活动才能 实际上是一个求 最长轨道的问题 关键路径算法 CPM 求解 关键路径算法 CPM 初始化 递归 终止 如果v t 停止 实例演示 初始化 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 屋顶10 0 实例演示 递归 1 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 屋顶10 0 4 1 7 实例演示 递归 2 屋顶10 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 0 4 1 7 4 实例演示 递归 3 屋顶10 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 0 4 1 7 4 19 实例演示 递归 4 屋顶10 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 0 4 1 7 4 19 23 8 27 4 实例演示 递归 5 屋顶10 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 0 4 1 7 4 19 27 4 37 4 23 8 实例演示 路径回溯 屋顶10 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 0 4 1 7 4 19 23 8 27 4 37 4 关键路径算法说明 关键路径算法给出的时间是任一活动的最 早开工时间 若e uv 则最早开工时间 E e u 关键路径上活动的拖延将会引起整个工期 延长 相反 非关键路径上的活动的是容许一定 时间的延迟的 故可考虑如下的问题 活 动的最晚开工时间是多少 最晚开工时间计算L e 若活动由边e表示 e uv 则 初始化 u v w 实例演示 最晚开工时间 屋顶10 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 0 4 1 7 4 19 23 8 27 4 37 4 37 4 27 4 19 32 6 4 4 2 0 3 0 关键路径上的活动 地基 砌砖 木工 屋顶最早开 工 最晚开工时间相等 不在关键路径上的活动 挖沟 0 0 3 管线 1 7 2 0 喷绘 19 32 6 最早开工 最晚开工时间 有一个时间差 浮动时间 记为R e R e L e E e 屋顶10 s t 挖沟1 7 地基4 管线 2 砌砖15 喷绘4 8 木工8 4 0 4 1 7 4 19 23 8 27 4 37 4 37 4 27 4 19 32 6 4 4 2 0 3 0 赶工优化问题 关键路径上的活动的任何延误将会延长总 工期 相反如果要缩短工期 在不计较代 价的情况下 自然的做法是把关键路径上 的活动耗时量缩小 如果计较代价 如何缩短总工期而且使得 赶工成本最少 这个问题就是所谓的赶工 优化问题 赶工优化问题 数学描述 设项目中活动e的最少耗时为b e 正常情况 下耗时l e 赶工成本为每天c e 现在要赶 工 T天 应该在那些活动上赶工多少天 才能使赶工总成本最小 几点考虑 待赶工活动对象 浮动时间小于要缩短的 工期 R e T 不妨称之为 准关键路径 费用网络 待赶工活动对象组成一个网 络 权取为赶工费用 注意 如果b e l e 表示该活动不能加快 故取赶工费用为 几点考虑 续 最小赶工费用 费用网络中的最大流所对 应的 最小 切割流量 一项活动的耗时量一经修改 改变了 准关 键路径的分布 需要重新计算 逐天压缩工期 故可以重复上面的考虑来 完成全部的赶工期数 赶工优化问题 解法 计算浮动时间 费用网络 费用网络的最大流所对应的切割 P Q 上的 活动赶工一天 将赶工天数减一 并将上一步得到的切割 P Q 上的活动工序减一后重复上面的步 骤 直到完成全部赶工天数为止 实例演示 1 a bcs dt 11 9 40 8 7 160 10 8 905 2 200 6 4 306 5 100 4 4 100 边上的数字对应于 l e b e c e 要把工期 提前三天 如何赶工 使得总赶工费用最小 实例演示 2 a bcs dt 11 9 408 7 160 10 8 905 2 200 6 4 306 5 100 010 6 4 4 100 1725 15 21 16 11 176 1 0 实例演示 3 分割为 s a b d t 故在sa和sb上压缩 一天工期 费用为120 a bs dt 40 30 160 120 90 90 30 30100 90 c 3 3 3 3 3 2 2 实例演示 4 a bcs dt 11 9 40 8 7 160 9 8 905 2 200 5 4 306 5 100 4 4 100 剩下的二天赶工期 实例演示 5 a bcs dt 11 9 408 7 160 9 8 905 2 200 5 4 306 5 100 09 5 4 4 100 1624 14 20 15 10 165 1 0 实例演示 6 a bs dt 40 30 160 120 90 90 30 30100 90 c 2 2 2 4 4 1 1 分割为 s a b d t 故在sa和sb上压缩 一天工期 费用为120 实例演示 7 a bcs dt 11 9 40 8 7 160 8 8 905 2 200 4 4 306 5 100 剩下的一天赶工期 实例演示 8 a bcs dt 11 9 408 7 160 8 8 905 2 200 4 4 306 5 100 08 4 4 4 100 1523 13 19 14 9 154 1 0 实例演示 9 a bs dt 40 40 160 40 40 c 1 1 1 5 5 0