信息系统监理师考试重点难点汇总

软考资料

关键路径（CPM）

AOE网(Activity On Edge network)，即边表示活动的网络，与AOV网相对应的是。它通常表示一个工程的计划或进度。

AOE网是一个有向带权图，图1中的： 边：表示活动(子工程)，

边上的权：表示该活动的持续时间，即完成该活动所需要的时间；

顶点：表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此完成，所有出边活动从此开始。

其中有两个特殊的顶点(事件)，一个称做源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边；另一个称做汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有入边，没有出边。除这两个顶点外，其余顶点都既有人边，也有出边，是入边活动和出边活动的转接点。 在一个AOE网中，若包含有n个事件，通常令源点为第0个事件，汇点为第n-1个事件，其余事件的编号(即顶点序号)分别为1~n-2。

一个AOE网如图，该网中包含有10项活动和7个事件。

例如，边<1，2>表示活动al，持续时间(即权值)为3，假定以天为单位，即a1需要3天完成，它以V1事件为起点，以V2事件为终点；边<2，5>和<2，4>分别表示活动a4和a5，它们的持续时间分别为4天和2天，它们均以V2事件为起点，以V5和V4事件为终点。该网中的源点和汇点分别为第1个事件V1和最后一个事件V7，它们分别表示整个工程的开始和结束。

对于一个AOE网，待研究的问题是： (1)整个工程至少需要多长时间完成? (2)哪些活动是影响工程进度的关键

?

图1 AOE网

1．事件的最早发生时间与活动的最早开始时间的关系 在AOE网中，一个顶点事件的发生或出现必须在它的所有入边活动(或称前驱活动)都完成之后，即只要有一个入边活动没有完成，该事件就不可能发生。所以：

一个事件的最早发生时间是它的所有入边活动，或者说最后一个入边活动刚完成的时间。

一个活动的开始必须在它的起点事件发生之后，也就是说，一个顶点事件没有发生时，它的所有出边活动(或称后继活动)都不可能开始，所以：

一个活动的最早开始时间是它的起点事件的最早发生时间。若用Ve[j]表示顶点Vj事件的最早发生时间，用e[i]表示Vj一条出边活动ai的最早开始时间，则有e[i]=Ve[j]。

2．求事件的最早发生时间

对于源点事件来说，因为它没有入边，所以随时都可以发生，整个工程的开始时间就是它的发生时间，亦即最早发生时间，通常把此时间定义为0，从此开始推出其他事件的最早发生时间。 例如，如图所示的AOE网中，