AOE网(带权有向无环图)_时间余量

1. 用顶点表示事件， 用有向边表示活动，边上的权值表示活动的持续时间。                               (事件:例如:完成外壳的生产， 活动:如生产外壳)                                                                              2. AOE网中入度为0的顶点称为源点，出度为0的顶点称为终点(汇点)                                                3. 从源点到汇点的有向路径可能有多条，所有路径中，具有组大路径长度的路径称为关键路径，把关键路径上的活动称为关键活动。

AOE网可以回答下列问题:  

1.完成整个工程至少需要多少时间          2. 为缩短完成工程所需的时间，应加快哪些活动

 AOE网的性质:1. 只有在某个顶点所代表的事件发生后，从该顶点出发的各活动才能始;                  2. 只有在进入某顶点的各活动都结束，该顶点所代表的时间才能发生.

关键路径:                                                                                                                                         1.在AOE网中，从源点到终点具有最大路径长度(该路径上各活动所持续的时间之和)的路径称为关键路径;  （关键路径可能不止一条）

关键活动:   关键路径上的所有活动称为关键活动

需要四个关键活动有关量:    ve[2]表示2这个时间最在开始的时间                                                     事件的最早发生时间ve[k]       事件最晚发生时间vl[k]                                                                        活动的最早发生时间ee[i]      活动的最晚发生时间el[i]                                                                  d[i]表示时间余量，就是用最晚发生时间减去最早发生时间就是时间余量  （时间余量为0的活动就是关键活动,找到关键活动就确定了对应的边，相应的就知道了关键路径）

从源点开始推算出每个活动的最早开始时间，  从终点开始，往源点推算，计算出每个活动最晚要什么时候开始，否则会耽误整个活动的工程

注意:

1.若关键活动耗时增加，则整个工程的工期将增加

2.缩短关键活动的时间，可以缩短整个工程的工期

3.当缩短到一定程度时，关键活动可能会变成非关键活动

4.可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括所有关键路径上的关键活动才能达到缩短整个工期的目的

5.

步骤：                                                                                                                                                 1.求所有事件的最早发生时间 ve[], 按照拓扑排序序列，依次求各个顶点的 ve[i];  设置ve[0]=0,，ve[k]=Max{ve[j]+weight(vj,vk) },(取大的，因为当前一个事件结束了才可以做这个活动，如果一个时间短的活动结束了，但是时间长的没有结束，这个活动仍然不可以开始)  vj 为vk的任意前驱,

 

2.求所有事件的最迟发生时间，按照逆拓扑排序序列，依次求各个顶点的最晚发生时间，汇点(终点)的最晚发生时间就是汇点最早发生时间，如果汇点再延迟，整个工期一定会延迟。v[k]=min{vl(j)-weight(vk,vj)} (选择小的，因为一个最晚6点开始，一个最晚7点开始，如果选择大的7点开始，则6开始的活动一定完成不了，所以最晚发生时间选择小的)

 3.求所有活动的最早发生时间， 若 <vj,vk>表示活动ai, 则有e(i)=ve(k);  某个活动的最早发生时间，就是该活动弧尾所连的事件的最早发生时间  

 4. 所有活动的最晚发生时间， 若边<vk,vj>表示活动ai, 则有l(i)=vl(j)-weight(vk,vj);   v5为前驱， v6为后继，v5的最迟发生时间就是 v6的最晚发生时间-a8这个活动的时间，（为什么是最晚呢，因为如果选最早5点开始，a8需要一小时，则计算结果为4点开始，因为5时候v6的最早开始，所以v6还可以拖延一会，反推得，应该选择最晚发生时间-weight）

5.求所有时间余量:  时间余量就是用活动的最晚发生时间减去最早发生时间，就是活动余量。