已知AOE网中顶点V1,V2,V3,V4,V5,V6,V7分别表示7个时间,有向线段a1,a2,a3,a4,a5,a6,a7,a8,a9,a10。分别表示10个活动,线段旁的数值表示每个活动花费的天数,如下图所示。请填写下面两个表格,并用顶点序列表示出关键路径,给出关键活动。

事件 | V1 | V2 | V3 | V4 | V5 | V6 | V7 |
最早发生时间 | | | | | | | |
最晚发生时间 | | | | | | | |
参考答案:AOE网中从源点到终点的最大路径长度(这里的路径长度是指该路径上的各个活动所需时间之和)的路径称为关键路径。关键路径长度是整个工程所需的最短工期。
关键路径上的活动称为关键活动。要缩短整个工期,必须加快关键活动的进度。
寻找关键活动时所用到的几个参量的定义:
假设第i条弧为<j,k>,dut(<j,k>)为弧<j,k>上的权值。
(A)事件的最早发生时间ve[k]=从源点到顶点k的最长路径长度。
ve(源点)=0;
ve(k)=Max{ve(j)+dut(<j,k>)}
(B)事件的最迟发生时间vl(k)=从顶点j到汇点的最短路径长度。
vl(汇点)=ve(汇点);
vl(j)=min{vl(k)-dut(<j,k>)}
(C)活动i的最早开始时间e(i)=ve(j)。
(D)活动i的最晚开始时间l(i)=vl(k)-dut(<j,k>)。
e[i]=l[j]的活动就是关键活动,关键活动所在的路径就是关键路径。 事件 | VA | VB | VC | VD | VE | VF | VG |
最早发生时间 | 0 | C | B | F | G | E | A0 |
最晚发生时间 | 0 | C | C | F | G | F | A0 |
活动 | aA | aB | aC | aD | aE | aF | aG | aH | aI | aA0 |
最早发生时间 | 0 | 0 | 0 | C | C | B | B | F | G | E |
最晚发生时间 | 0 | 0 | A | C | D | E | C | F | G | F |
时间余量 | 0 | 0 | A | 0 | A | C | A | 0 | 0 | A |