求关键路径
1. 首先求关键节点
求关键节点的方法，若求关键节点，则须知该节点最早发生的时间V(i)e和最晚发生的时间V(i)l
最早发生时间V(i)e=max{ V(j)e+dut(j,i)} 其中dut(j,i)表示从节点j到节点i代价即活动的代价；
例如
V(1)e=0; V(1) 表示1结点
V(2)e=max{ V(1)e+dut(1,2)}=0+6=6;
V(3)e=max{ V(1)e+dut(1,3)}=0+4=4;
V(4)e=max{ V(1)e+dut(1,4)}=0+5=5;
V(5)e=max{ V(2)e+dut(2,3) , V(3)e+dut(3,5) }=max{ 6+1, 4+1 }=7;
V(6)e=max{ V(4)e+dut(4,6)}=7;
V(7)e=max{ V(5)e+dut(5,7)}=7+7=14;
V(8)e=max{ V(5)e+dut(5,8) , V(6)e+dut(6,8)}=max{7+5 , 7+ 4}=12
V(9)e=max{ V(7)e+dut(7,9), V(8)e+dut(8,9)}= 16;
最晚发生时间V(i)l)
v(i)l=min{v(k)l-dut(<i,k>)}
从最后一个节点算
V(9)l=16;
V(8)l=min{ V(9)l - dut(8,9) }=12
V(7)l=min{ V(9)l-dut(7,9)}=14;
V(6)l=min{ V(8)l-dut(6,8)}=8
V(5)l=min{ V(7)l-dut(5,7), V(8)l-dut(5,8)}=7;
………..
V(1)l=min{V(2)l-dut(I,2) , V(3)l-dut(1,3 ), V(4)-dut(1,4)}=0;
若最早和最晚时间相等则该节点时关键点
V(i)e=V(i)l;
结点 |
Ve |
Vl |
1 |
0 |
0 |
2 |
6 |
6 |
3 |
4 |
6 |
4 |
5 |
6 |
5 |
7 |
7 |
6 |
7 |
8 |
7 |
14 |
14 |
8 |
12 |
12 |
9 |
16 |
16 |
关键结点是1， 2， 5 ， 7 ， 8 ， 9
2. 求关键活动，其中a1,a2…….a11 就是活动
若求关键活动，必须求各个活动最早开始时间e[i]和最晚开始时间l[i]
每个活动的最早开始时间就是其前一个结点的最早开始时间
如a1 的最早开始时间就是0结点最早开始时间， 所以
a1最早开始时间是0；也就是e[1]=0;
a2的最早开始时间也是0结点最早开始的时间，所以
a2最早开始时间是0；也就是e[2]=0;
依次如此
a3最早开始时间是0；也就是e[3]=0;
a4 的最早开始时间也是2结点最早开始的时间，所以
a4最早开始时间是4；也就是e[4]=6;
a5 的最早开始时间也是3结点最早开始的时间，所以
a5最早开始时间是4；也就是e[5]=4;
a6 的最早开始时间也是4结点最早开始的时间，所以
a6最早开始时间是5；也就是e[6]=5;
a7 的最早开始时间也是5结点最早开始的时间，所以
a7最早开始时间是7；也就是e[5]=7
a8 的最早开始时间也是5结点最早开始的时间，所以
a8最早开始时间是7；也就是e[8]=7;
a9 的最早开始时间也是6结点最早开始的时间，所以
a9最早开始时间是7；也就是e[9]=7;
a10 的最早开始时间也是7结点最早开始的时间，所以
a10最早开始时间是14；也就是e[10]=14;
a11 的最早开始时间也是8结点最早开始的时间，所以
a11最早开始时间是12；也就是e[11]=12;
再求活动最晚开始时间也是从后面开始计算；
活动最晚开始时间等于结点最晚开始时间减去活动时间；
如上图：
这里的V(i)l根据上面的表就可以知道
L[11]=V(9)l-dut(8,9)=16-4=12; 就是9结点最晚开始时间减去a11活动时间；
L[10]=V(9)l-dut(7,9)=16-2=14; 就是9结点最晚开始时间减去a10活动时间；
L[9]=V(8)l-dut(6,8)=12-4=8; 就是8结点最晚开始时间减去a9活动时间；
L[8]=V(8)l-dut(5,8)=12-5=7; 就是8结点最晚开始时间减去a8活动时间；
L[7]=V(7)l-dut(5,7)=14-7=7; 就是7结点最晚开始时间减去a7活动时间；
L[6]=V(6)l-dut(4,6)=8-2=6; 就是6结点最晚开始时间减去a6活动时间；
L[5]=V(5)l-dut(3,5)=7-1=6; 就是5结点最晚开始时间减去a5活动时间；
L[4]=V(5)l-dut(2,5)=7-1=6; 就是5结点最晚开始时间减去a4活动时间；
L[3]=V(4)l-dut(1,4)=6-5=1; 就是4结点最晚开始时间减去a3活动时间；
L[2]=V(3)l-dut(1,3)=6-4=2; 就是3结点最晚开始时间减去a2活动时间；
L[1]=V(2)l-dut(1,2)=6-6=0; 就是2结点最晚开始时间减去a1活动时间；
关键活动就是活的最晚时间减去最早时间等于0的活动；
如表；
活动 |
E[i] |
L[i] |
L[i]-e[i] |
A1 |
0 |
0 |
0 |
A2 |
0 |
2 |
2 |
A3 |
0 |
1 |
1 |
A4 |
6 |
6 |
0 |
A5 |
4 |
6 |
2 |
A6 |
5 |
6 |
1 |
A7 |
7 |
7 |
0 |
A8 |
7 |
7 |
0 |
A9 |
7 |
8 |
1 |
A10 |
14 |
14 |
0 |
A11 |
12 |
12 |
0 |
看表可知关键活动 a1 , a4, a7 , a8, a10 ,a11