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

软考资料

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的最早发生时间。由此可知，必须按照拓扑序列中的顶点次序(即拓扑有序)求出各个事件的最早发生时间，这样才能保证在求一个事件的最早发生时间时，它的所有前驱事件的最早发生时间都已求出。 设Ve[k]表示vk事件的最早发生时间，Ve[j]表示vk的一个前驱事件vj的最早发生时间，dut(<j,k>)表示边<j,k>上的权，p表示vk顶点所有入边的集合，则网中每个事件vk(0≤k≤n-1)的最早发生时间Ve可由下式，按照拓扑有序计算出来。

Ve(k) = 0 (k = 0)

max{Ve[j] +dut(< j,k >)} (l≤k≤n- 1, <j,k>∈p)

按照此公式和拓扑有序计算出图所示的AOE网中每个事件的最早发生时间为： Ve(1) = 0

Ve(2) = Ve(1) +dut( <1,2 > ) =0+3=3 Ve(3) = Ve(1) + dut( <1,3 > ) =0+2 = 2

Ve(4) = max{Ve(1) + dut( < 1,4 > ), Ve(2) + dut( < 2,4 > ), Ve(3) + dut( < 3,4 > ) }= max{0 +6,3+ 2,2+1} =6 Ve(5) = max{Ve(2) + dut( < 2,5 > ),Ve(4) +dut( < 4,5 > )} = max{3+4,6 + 1}= 7 Ve(6) = Ve(3) +dut( <3,6> ) =2+3= 5

Ve(7) = max{Ve(5) +dut( < 5,7 > ), Ve(6) +dut( <6,7 > )} = max{7 + 3,5 + 4} = 10

最后得到的Ve(7)就是汇点的最早发生时间，从而可知整个工程至少需要10天完成。 3．事件的最迟发生时间与活动的最迟开始时间的关系

事件的最迟发生时间：在不影响整个工程按时完成的前提下，一些事件可以不在最早发生时间发生，而允许向后推迟一些时间发生，我们把最晚必须发生的时间叫做该事件的最迟发生时间。

同样，在不影响整个工程按时完成的前提下，一些活动可以不在最早开始时间开始，而允许向后推迟一些时间开始，我们把最晚必须开始的时间叫做该活动的最迟开始时间。AOE网中的任一个事件若在最迟发生时间仍没有发生或任一项活动在最迟开始时间仍没有开始，则必将影响整个工程的按时完成，使工期拖延。 若用Vl[k]表示顶点Vk事件的最迟发生时间，用l[i]表示Vk的一条入边<j，k>上活动ai的最迟开始时间，用dut(<j，k>)表示ai的持续时间，则有 l[i]= Vl [k]-dut(<j，k>)

因ai活动的最迟完成时间也就是它的终点事件Vk的最迟发生时间，所以ai的最迟开始时间应等于Vk的最迟发生时间减去ai的持续时间，或者说，要比Vk的最迟发生时间提前ai所需要的时间。

4．求事件的最迟发生时间

为了保证整个工程的按时完成，把汇点的最迟发生时间定义为它的最早发生时间，即Vl [n]= Ve [n] Vl。其他每个事件的最迟发生时间应等于汇点的最迟发生时间减去从该事件的顶点到汇点的最长路径长度，或者说，每个事件的最迟发生时间比汇点的最迟发生时间所提前的时间应等于从该事件的顶点到汇点的最长路径上所有活动的持续时间之和。

求一个事件Vj的最迟发生时间的常用方法是：由它的每个后继事件Vk的最迟发生时间分别减去相应出边<j，k>上的权，其值最小者就是vj的最迟发生时间。由此可知，必须按照逆拓扑有序求出各个事件的最迟发生时间，这样才能保证在求一个事件的最迟发生时间时，它的所有后继事件的最迟发生时间都已求出。

设Vl [j]表示待求的Vj事件的最迟发生时间，Vl [k]表示Vj的一个后继事件Vk的最迟发生时间，dut(<j，k>)表