信息系统监理师重点难点总结.docVIP

关键路径（CPM） AOE网(Activity On Edge network)，即边表示活动的网络，与AOV网相对应的是。它通常表示一个工程的计划或进度。 AOE网是一个有向带权图： 边：表示活动(子工程)， 边上的权：表示该活动的持续时间，即完成该活动所需要的时间； 顶点：表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此完成，所有出边活动从此开始。 其中有两个特殊的顶点(事件)，一个称为源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边；另一个称为汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有入边，没有出边。除这两个顶点外，其余顶点都既有人边，也有出边，是入边活动和出边活动的转接点。 在一个AOE网中，若包含有n个事件，通常令源点为第0个事件，汇点为第n-1个事件，其余事件的编号(即顶点序号)分别为1~n-2。 对于一个AOE网，待研究的问题是： (1)整个工程至少需要多长时间完成? (2)哪些活动是影响工程进度的关键? 图1　AOE网 图2　关键路径 1．求出关键路径的意义 关键路径实际上就是从源点到汇点具有最长路径长度的那些路径，即最长路径。这很容易理解，因为整个工程的工期就是按照最长路径长度计算出来的，即等于该路径上所有活动的持续时间之和。当然一条路径上的活动只能串行进行，若最长路径上的任一活动不在最早开始时间开始，或不在规定的持续时间内完成，都必然会延误整个工期，所以每一项活动的开始时间余量为0，故它们都是关键活动。 可通过加快关键活动(即缩短它的持续时间)来实现缩短整个工程的工期。 但并不是加快任何一个关键活动都可以缩短整个工程的工期。只有加快那些包括在所有关键路径上的关键活动才能达到这个目的。 2．事件的最早发生时间与活动的最早开始时间的关系 在AOE网中，一个顶点事件的发生或出现必须在它的所有入边活动(或称前驱活动)都完成之后，即只要有一个入边活动没有完成，该事件就不可能发生。所以： 一个事件的最早发生时间是它的所有入边活动，或者说最后一个入边活动刚完成的时间。 一个活动的开始必须在它的起点事件发生之后，也就是说，一个顶点事件没有发生时，它的所有出边活动(或称后继活动)都不可能开始，所以： 一个活动的最早开始时间是它的起点事件的最早发生时间。 3．求事件的最早发生时间 对于源点事件来说，因为它没有入边，所以随时都可以发生，整个工程的开始时间就是它的发生时间，亦即最早发生时间，通常把此时间定义为0，从此开始推出其他事件的最早发生时间。 例如，如图所示的AOE网中， V5事件的发生必须在a4和a8活动都完成之后，而a4和a8活动的开始又必须分别在V2和V4事件的发生之后，V2和V4事件的发生又必须分别在a1和a2活动的完成之后，因a1和a2的活动都起于源点，其最早开始时间均为0，所以a1和a2的完成时间分别为3和6，这也分别是V2和V4的最早发生时间，以及a4和a8的最早开始时间，故a4和a8的完成时间分别为7和7，由此可知V5事件的最早发生时间为7，即所有入边活动中最后一个完成的时间。 从以上分析可知，一个事件的发生有待于它的所有入边活动的完成，而每个入边活动的开始和完成又有待于前驱事件的发生，而每个前驱事件的发生又有待于它们的所有入边活动的完成，……总之，一个事件发生在从源点到该顶点的所有路径上的活动都完成之后，显然，其最早发生时间应等于从源点到该顶点的所有路径上的最长路径长度。这里所说的路径长度是指带权路径长度，即等于路径上所有活动的持续时间之和。 如从源点V1到顶点V4共有三条路径，长度分别为5、6和3，所以V4的最早发生时间为6。 从源点V1到汇点V7有多条路径，通过分析可知，其最长路径长度为10，所以汇点V7的最早发生时间为10。汇点事件的发生，表明整个工程中的所有活动都已完成，所以完成图所对应的工程至少需要10天。 如何从源点V1的最早发生时间1出发，求出其余各事件的最早发生时间。 求一个事件Vk的最早发生时间(即从源点V1~Vk的最长路径长度)的常用方法是： 由它的每个前驱事件Vi的最早发生时间(即从源点V1~Vi的最长路径长度)分别加上相应入边i，k上的权，其值最大者就是Vk的最早发生时间。由此可知，必须按照拓扑序列中的顶点次序(即拓扑有序)求出各个事件的最早发生时间，这样才能保证在求一个事件的最早发生时间时，它的所有前驱事件的最早发生时间都已求出。 4．事件的最迟