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

《数学模型3-3关键路径分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、333.3关键路径分析(CPA)和计划评审技术(()PERT)关键路径分析算法赶工优化问题引言•中学课本华罗庚先生的一篇文章：统筹方法:如何有效地安排各项活动的顺序。•历史：–CPM－1956年，美国杜邦公司。–PERT－1958年，美国海军特种计划局。–PDM(PPDM(PrecedenceDiagrammingMethod)－1964年，美国IBM公司。•现代应用：项目管理，TCP/IP网络分析项目管理•数采集数据采集–项目活动组成.–每项活动和其他活动之间的依存关系.–每项活动需要延续的时间.•目标：如何安排项目活动最节约时间、最经济.一个例子编

2、号活动前期活动延续时间1地基无404.02挖沟无1.73管线22.04砌砖1，2，315.05喷绘44.86木工4848.47屋顶610.0图形表示•Activityonarc(AOA)•Activityonnode(AON)AOA表示•每项活动以图形的边表示.•活动的延续时间作为边的权.•节点代表两个活动间的连接点.•人为加入“开始”和“结束”节点.•需要加入空边以表示活动的依存关系.AOA表示：例子地基4喷绘4.8st木工8.4砌砖15挖沟171.7管线2屋顶10这里粉红色的线不代表任何活动，只是为了表示活动的依存关系AON表示•每个节点代表一项活

3、动。•有向弧表示活动之间的依存关系，表示一项活动是另一项活动的前提条件。•顶点的值表示活动延续时间。•人为引进“开始”和“结束”节点。AON表示：例子4.04.815地基喷绘砌砖结束开始木工挖沟屋顶管线1.78.4102.0总工期问题•从开工到结束至少需要多长时间？•说明：乍一看似乎是一个最“短”路径问题，但由于PERT图的特殊性(只有当前的活动结束后后面的活动才能)，实际上是一个求最长轨道的问题。•关键路径算法(CPM)求解关键路径算法(CPM)•初始化：•递归•终止：如果v=t停止实例演示：初始化地基4喷绘484.8s0t木工8.4砌砖15挖沟1.

4、7管线2屋顶10实例演示：递归(1)4地基4喷绘484.8s0t木工8.4砌砖15挖沟1.7管线2屋顶101.7实例演示：递归(2)4地基4喷绘4.84s0t木工848.4砌砖15挖沟1.7管线2屋顶101.7实例演示：递归(3)4地基4喷绘4.84s0t木工8.4砌砖1519挖沟171.7管线2屋顶10171.7实例演示：递归(4)423.8地基4喷绘4.84s0t木工8.4砌砖1519挖沟171.7管线2屋顶10171.727427.4实例演示：递归(5)423.8地基4喷绘4.84s0t木工8.437.4砌砖1519挖沟171.7管线2屋顶101

5、71.727427.4实例演示：路径回溯423.8地基4喷绘4.84s0t木工848.437.4砌砖1519挖沟1.7管线2屋顶101.727.4关键路径算法说明•关键路径算法给出的时间是任一活动的最早开工时间。若e=[uv],则最早开工时间E(e)=λ(u).•关键路径上活动的拖延将会引起整个工期延长。•相反，非关键路径上的活动的是容许一定时间的延迟的，故可考虑如下的问题：活动的最晚开工时间是多少？最晚开工时间计算L(e)•若活动由边e表示,e=[uv]则wuv•初始化实例演示：最晚开工时间4423.8地基4喷绘484.837437.404432.6

6、s0t木工8.40.3砌砖151937.419挖沟171.7管线2屋顶1027.427.41.724423823.8地基4喷绘4.837.404432632.6s0t木工8.4030.3砌砖151937437.419挖沟1.7管线2屋顶1027427.427427.41.72关键路径上的活动：地基，砌砖，木工，屋顶最早开工、最晚开工时间相等。不在关键路径上的活动：挖沟(003)(0,0.3)，管线(1720)(1.7,2.0)，喷绘(19,32.6)。最早开工、最晚开工时间有一个时间差－浮动时间，记为R(e),R(e)R(e),R(e)L(e)=L(e

7、)-E(e).赶工优化问题•关键路径上的活动的任何延误将会延长总工期。相反如果要缩短工期，在不计较代价的情况下，自然的做法是把关键路径上的活动耗时量缩小。•如果计较代价，如何缩短总工期而且使得赶工成本最少，这个问题就是所谓的赶工优化问题。赶工优化问题－数学描述•设项目中活动e的最少耗时为b(e),正常情况下耗时l((),e),赶工成本本每为每天c(e),现在要赶工ΔT天，应该在那些活动上赶工多少天，才能使赶工总成本最小？基本考虑•待赶工活动对象－浮动时间小于要缩短的工期。R(()e)<ΔT.不妨称之为“准关关路径键路径”•如果只在关键路径上赶工，准关键

8、路径可能变成关键路径，而且并没有达到预期的赶工目的。例子(1)66171725adt11806