教培参考
教育培训行业知识型媒体
发布时间: 2023-04-08 03:56:02
5.8 关键路径★3◎4
AOE-网（Activity On Edge）是指边表示活动的网，这是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。在一般情况下，AOE-网用来估计工程的完成时 间，图5-15定义了6个时间、8个活动的AOE-网。
在正确的情况下，AOE-网表示的工程只有一个开始点和一个完成点，即只有一个入度为0的顶点（源点）和一个出度为0的顶点（汇点）。
在AOE-网表示的工程中，部分活动可以并行进行，那么完成工程的最短时间是从开始点到完成点的最长路径的长度，即该条路径上所有弧的权值之和。路径长度最长的路径称为关键路径”。
在AOE-网中，事件最早发生时间”，是指从开始点到事件顶点之间的最长路径的长度，同时这个时间也是所有以此顶点为尾的弧所表示的活动的活动最早发生时间”，用e(i)表示。
活动最迟开始时间”是指在不推迟整个工程完成的前提下，活动最迟必须开始进行的时间，用l(i)表示。
最早发生时间和最迟开始时间之差l(i)-e(i)”是完成活动的时间余量，如果某活动的e(i)=l(i)，则称此活动为关键活动”，关键路径上的所有活动都是关键活动，提前完成非关键活动（不在关键路径的活动）并不能加快工程的进度。
定义事件j的最早发生时间为ve(j)和最迟发生时间为vl(j)，活动ai的最早开始时间为e(i)，最迟开始时间为l(i)，则求AOE-网的关键路径算法如下。
1．求事件的最早发生时间
从ve(0)=0开始向前递推，其中T是所有以第j个顶点为头的弧的集合，<i，j>是其中的弧（活动），dut(<i，j>)是此弧的权（活动所需的时间）：
ve[j]=max{ve[i]+dut(<i, j>)} <i, j>∈T, j=1,2,3,…,n
以图5-15为例，求事件的最早发生时间的算法如表5-9所示。
表5-9 求事件的最早发生时间
| 顶 点 | VE | 分 析 |
| V0 | 0 | 定义ve[0]=0 |
| V1 | 5 | V1只有一个直接前驱，故ve[1]=ve[0]+dut(<0,1>)=0+5=5 |
| V2 | 5 | V2只有一个直接前驱，故ve[2]=ve[0]+dut(<0,2>)=0+5=5 |
| V3 | 6 | V3有2个直接前驱，分别为V1和V0； 考察V0：有ve[0]+dut(<0,3>)=0+4=4； 考察V1：有ve[1]+dut(<1,3>)＝5+1=6； ve[3]取大值6 |
| V4 | 12 | V4有2个直接前驱，分别为V2和V3； 考察V2：有ve[2]+dut(<2,4>)=5+7=12； 考察V3：有ve[3]+dut(<3,4>)＝6+2=8； ve[4]取大值12 |
| V5 | 14 | V5有2个直接前驱，分别为V3和V4； 考察V3：有ve[3]+dut(<3,5>)=6+8=14； 考察V4：有ve[4]+dut(<4,5>)＝12+1=13； ve[5]取大值14 |
2．求事件的最迟开始时间
从vl(n-1)=ve(n-1)起向后递推，其中S是所有以第i个顶点为尾的弧的集合。
vl[j]=min{vl[i]-dut(<i, j>)} <i, j>∈T,i=n-2,n-3,…,0
以图5-15为例，求事件的最迟开始时间的算法，如表5-10所示。
表5-10 求事件的最迟开始时间
| 顶 点 | VL | 分 析 |
| V5 | 14 | 定义vl[5]=ve[5]=14 |
| V4 | 13 | V4只有一个直接后继，故vl[4]=vl[5]-dut(<4,5>)=14-1=13 |
| V3 | 6 | V3只有一个直接后继，故vl[3]=vl[5]-dut(<3,5>)=14-8=6 |
| V2 | 6 | V2只有一个直接后继，故vl[2]=vl[4]-dut(<2,3>)=13-7=6 |
| V1 | 5 | V1只有一个直接后继，故vl[1]=vl[3]-dut(<1,3>)=6-1=5 |
| V0 | 0 | V0有3个直接后继，分别为V1，V2和V3： 考察V1：vl[1]-dut(<0,1>)=5-5=0 考察V2：vl[2]-dut(<0,2>)=5-5=0 考察V3：vl[3]-dut(<0,3>)=6-4=2 vl[0]取小值0 |
事件的最早发生时间和最迟开始时间的对比，如表5-11所示。
表5-11 事件最早发生时间与最迟开始时间对比表
| V0 | V1 | V2 | V3 | V4 | V5 | |
| 最早发生时间 | 0 | 5 | 5 | 6 | 12 | 14 |
| 最迟开始时间 | 0 | 5 | 6 | 6 | 13 | 14 |
| 关键路径 | V0 | V1 | V3 | V5 |
所以图5-15的关键路径为V0、V1、V3、V5。
3．求活动的最早发生时间和最迟发生时间
活动ai由弧<j,k>（即从顶点j到k）表示，其持续时间记为dut(<j,k>)，则：
e(i) = ve(j)
l(i) = vl(k)-dut(<j,k>)
以图5-15为例，求活动的最早发生时间和最迟开始时间的算法，如表5-12所示。
表5-12 求活动的最早发生时间和最迟开始时间
| 活 动 | 弧 | E | L | 关键活动 |
| a1 | <0,1> | ve[0]=0 | vl[1]-dut(<0,1>)=5-5=0 | a1：<0,1> |
| a2 | <0,3> | ve[0]=0 | vl[3]-dut(<0,3>)=6-4=2 | |
| a3 | <0,2> | ve[0]=0 | vl[2]-dut(<0,2>)=6-5=1 | |
| a4 | <1,3> | ve[1]=5 | vl[3]-dut(<1,3>)=6-1=5 | a4：<1,3> |
| a5 | <2,4> | ve[2]=5 | vl[4]-dut(<2,4>)=13-7=6 | |
| a6 | <3,4> | ve[3]=6 | vl[4]-dut(<3,4>)=13-2=11 | |
| a7 | <3,5> | ve[3]=6 | vl[5]-dut(<3,5>)=14-8=6 | a7：<3,5> |
| a8 | <4,5> | ve[4]=14 | vl[5]-dut(<4,5>)=14-1=13 |
所以图5-15的关键活动有：a1<0,1>、a4<1,3>、a7<3,5>。
5.8 关键路径★3◎4
温馨提示：
