10分钟了解关键路径及如何求得关键路径 |
您所在的位置：网站首页 › 圆珠笔的怎么画 › 10分钟了解关键路径及如何求得关键路径 |
10分钟了解关键路径及如何求得关键路径
|
文章目录
一，什么是关键路径二，求解关键路径需要的4个描述量三，如何求得关键路径
视频参考：
6.6.4关键路径2–求解关键路径
一，什么是关键路径
【引例 1】某项目的任务是对A公司的办公室重新进行装修 如果10月1日前完成装修工程，项目最迟应该合适开始？ （需要完成的活动、每个活动所需时间、及先期需完成工作如下图所示） 事件表示在它之前的活动已经完成，在它之后的活动可以开始。 
对于AOE网，我们关心两个问题： 完成整项工程至少需要多少时间？ — 求关键路径长度哪些活动是影响工程进度的关键？ — 求关键路径上经过的顶点（活动）关键路径 — 路径长度最长的路径。 路径长度 — 路径上各活动持续时间之和。
l(i) - e(i) ---- 表示完成活动 ai 的时间余量。 例：l(3) - e(3) = 90 关键活动 ---- 关键路径上的活动，即 l(i) == e(i)即（l(i) - e(i) = 0）的活动。 三，如何求得关键路径那么我们如何找到满足 l(i) == e(i)的关键活动？ 设活动 ai 用弧 < j, k > 表示，其持续时间记为：wj,k 则有： e(i) == ve(j)l(i) = vl(k) - wj,k
如何求得 ve(j) 和 vl(j) ？ 从 ve(1) = 0 开始向前地推 ve(j) = Maxi{ ve(j) + wi,j }，< i, j >∈T，2 ≤ j ≤ n 其中 T 是所有以 j 为头的弧的集合。从 vl(n) = ve(n) 开始向后递推 vl(j) = Minj{ vl(j) + wi,j }，< i, j >∈S，1 ≤ i ≤ n-1
关键路径的讨论 若网中有几条关键路径，则需要加快同时在几条关键路径上的活动。 如：a11、a10、a8、a7。如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间。 如：a1、a4。处于所有关键路径上的活动完成时间不能缩短太多，否则会是的原来的关键路径变成非关键路径。这时，必须重新寻找关键路径。 如：a1 由 6天变成 3天，就会改变关键路径。 |
【引例 2】准备一个小型家庭宴会，晚6点宴会开始，最迟几点开始准备？压缩哪项活动时间可以使总时间减少？ 
我们把工程计划表示为边表示活动的网络，即 AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。
【引例 3】设一个工程有 11项活动，9 个事件。
最终，这道题就变成了求解关键路径的问题。
确定关键路径之前，我们需要定义4个描述量（以上图为例）：
下边我们通过一个例子来说明，求得关键路径的步骤（视频：28min开始） 
【本文地址】
今日新闻 |
推荐新闻 |