某项目主要由A〜I任务构成，其计划图（如下图所示）展示了各任务之间的前后关系以..

PERT图是一个有向图，图中的箭头表示任务，它可以标上完成该任务所需的时间；图中的节点表示流入节点的任务的结束，并开始流出节点的任务，这里把节点称为事件。只有当流入该节点的所有任务都结束时，节点所表示的事件才出现，流出节点的任务才可以开始。事件本身不消耗时间和资源，它仅表示某个时间点。一个事件有一个事件号和出现该事件的最早时刻和最迟时刻。最早时刻表示在此时刻之前从该事件出发的任务不可能开始；最迟时刻表示从该事件出发的任务必须在此时刻之前开始，否则整个工程就不能如期完成。每个任务还可以有一个松弛时间（slack time），表示在不影响整个工期的前提下，完成该任务有多少机动余地。为了表示任务间的关系，图中还可以加入一些空任务（用虚线箭头表示），完成空任务的时间为0。下图是PERT图的一个实例。不难看出，下图中的松弛时间为0的这些任务是完成整个工程的关键路径，其事件流为1→2→3→4→6→8→10→11。

PERT图实例

PERT图不仅给出了每个任务的开始时间、结束时间和完成该任务所需的时间，还给出了任务之间的关系，即哪些任务完成后才能开始另外一些任务，以及如期完成整个工程的关键路径。图中的松弛时间则反映了完成某些任务时可以推迟其开始时间或延长其完成所需的时间。但是，PERT图不能反映任务之间的并行关系。

关键路径

在AOV网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。例如，下图表示一个具有10个活动的某个工程的AOE网络。图中有7个结点，分别表示事件V₁~V₇，其中V₁表示工程开始状态，V₇表示工程结束状态，边上的权表示完成该活动所需的时间。

AOE网络的例子

因AOE网络中的某些活动可以并行地进行，所以完成工程的最少时间是从开始结点到结束结点的最长路径长度，称从开始结点到结束结点的最长路径为关健路径（临界路径），关键路径上的活动为关键活动。为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量：

V_e（j）、V₁（j）：结点j事件最早、最迟发生时间。

e（i）l（i）：活动i最早、最迟开始时间。

从源点V₁到某结点V_j的最长路径长度，称为事件V_j的最早发生时间，记作V_e（j）。V_e（j）也是以V_j为起点的出边<V_j，V_k>所表示的活动a_i的最早开始时间e（i）。

在不推迟整个工程完成的前提下，一个事件V_j允许的最迟发生时间，记作V₁（j）。显然，l（i）=V₁（j）-（a_i所需时间），其中j为a_i活动的终点。满足条件l（i）=e（i）的活动为关键活动。

求结点V_j的V_e（j）和V₁（j）可按以下两步来做：

由源点开始向汇点递推

其中，E₁是网络中以V_j为终点的入边集合。

由汇点开始向源点递推

其中，E₂是网络中以V_j为起点的出边集合。

要求一个AOE的关键路径，一般需要根据以上变量列出一张表格，逐个检查。例如，求上图所示的AOE的关键路径的表格如下表所示。

求关键路径的过程

因此，上图的关键活动为a₁、a₂、a₄、a₈和a₉，其对应的关键路径有两条，分别为（V₁，V₂，V₅，V₇）和（V₁，V₄，V₅，V₇），长度都是10。

一般来说，不在关键路径上的活动时间的缩短，不能缩短整个工期。而不在关键路径上的活动时间的延长，可能导致关键路径的变化，因此可能影响整个工期。

在实际解答试题时，一般所给出的活动数并不多，我们可以采取观察法求得其关键路径，即路径最长的那条路径就是关键路径。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5