|
|
知识路径： > 应用数学 > 图论应用 > 图论应用 >
|
|
考试要求：掌握
相关知识点：4个
|
|
|
|
|
在AOV网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。例如，下图所示为一个具有10个活动某个工程的AOE网络。图中有7个结点，分别表示事件1～7，其中1表示工程开始状态，7表示工程结束状态，边上的权表示完成该活动所需的时间。
|
|
|
|
|
|
|
|
因AOE网络中的某些活动可以并行地进行，所以完成工程的最少时间是从开始结点到结束结点的最长路径长度，称从开始结点到结束结点的最长路径为关健路径（临界路径），关键路径上的活动为关键活动。为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量：
|
|
|
|
Ve(j)、Vl(j)：结点j事件最早、最迟发生时间。
|
|
|
|
|
|
从源点Vl到某结点Vj的最长路径长度，称为事件Vj的最早发生时间，记作Ve(j)。Ve(j)也是以Vj为起点的出边<Vj，Vk>所表示的活动ai的最早开始时间e(i)。
|
|
|
|
在不推迟整个工程完成的前提下，一个事件Vj允许的最迟发生时间，记作Vl(j)。显然，l(i)=Vl(j)-(ai所需时间)，其中j为ai活动的终点。满足条件l(i)=e(i)的活动为关键活动。
|
|
|
|
求顶点Vj的Ve(j)和Vl(j)可按以下两步来做：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
要求一个AOE的关键路径，一般需要根据以上变量列出一张表格，逐个检查。例如，求上图中AOE的关键路径的表格如下表所示。
|
|
|
|
|
|
|
|
因此，上图中的关键活动为a1，a2，a4，a8和a9，其对应的关键路径有两条，分别为（V1，V2，V5，V7）和（V1，V4，V5，V7），长度都是10。
|
|
|
|
一般来说，不在关键路径上的活动时间的缩短，不能缩短整个工期。而不在关键路径上的活动时间的延长，可能导致关键路径的变化，因此可能影响整个工期。
|
|
|
|
在实际解答试题时，一般所给出的活动数并不多，可以采取观察法求得其关键路径，即路径最长的那条路径就是关键路径。
|
|
|
