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

1 3 4 关键路径分析 CPA 和计划 评审技术 PERT 关键路径分析算法 赶工优化问题 引言 中学课本华罗庚先生的一篇文章 统筹 方法 如何有效地安排各项活动的顺序 历史 CPM 1956年 美国杜邦公司 PERT 1958年 美国海军特种计划局 PDM Precedence Diagramming Method 1964年 美国IBM公司 现代应用 项目管理 TCP IP网络分析 项目管理 数据采集 项目活动组成 每项活动和其他活动之间的依存关系 每项活动需要延续的时间 目标 如何安排项目活动最节约时间 最经济 一个例子 10 06屋顶7 8 44木工6 4 84喷绘5 15 01 2 3砌砖4 2 02管线3 1 7无挖沟2 4 0无地基1 延续时间前期活动活动编号 图形表示 Activity on arc AOA Activity on node AON AOA 表示 每项活动以图形的边表示 活动的延续时间作为边的权 节点代表两个活动间的连接点 人为加入 开始 和 结束 节点 需要加入空边以表示活动的依存关系 2 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 3 实例演示 递归 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 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 屋顶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 赶工优化问题 关键路径上的活动的任何延误将会延长 总工期 相反如果要缩短工期 在不计 较代价的情况下 自然的做法是把关键 路径上的活动耗时量缩小 如果计较代价 如何缩短总工期而且使 得赶工成本最少 这个问题就是所谓的 赶工优化问题 赶工优化问题 数学描述 设项目中活动e的最少耗时为b e 正常 情况下耗时l e 赶工成本为每天c e 现 在要赶工 T天 应该在那些活动上赶工 多少天 才能使赶工总成本最小 5 几点考虑 待赶工活动对象 浮动时间小于要缩短 的工期 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 6 实例演示 4 a bcs dt 11 9 40 8 7 160 9 8 905 2 200 5 4 306 5 1004 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