关键路径的相关计算

相关参量定义

事件vk最早发生时间ve(k):是指从源点v1到顶点vk的最长路径长度。事件vk决定了所有从vk开始的活动能够开工的最早时间。ve(源点)=0,ve(k)=Max{ve(j)+weight(vj,vk)},vk是vj的后继节点,weight(vj,vk)表示vj到vk的权值。从前向后计算。

事件vk最迟发生时间vl(k):是指后继事件vj在最迟发生时间vl(j)能够发生时,该事件最迟必须发生的时间。vl(汇点)=ve(汇点),vl(k)=Min{vl(j)-Weight(vk,vj)},vk为vj的任意前驱。从后向前面计算

活动ai的最早发生时间e(i):该活动的弧起点所表示的事件最早发生时间。即边<vk,vj>表示活动ai,此时e(i)=ve(k)。

活动ai的最迟发生时间l(i):指活动弧终点表示的事件的最迟发生时间与活动所需时间之差。即边<vk,vj>表示活动ai,就存在l(i)=vl(j)-Weight(<vk,vj>)。

活动最迟开始时间l(i)减去最早开始时间e(i),d(i)=l(i)-e(i)。即活动完成的时间余量。

若一个活动的时间余量为0,则说明该活动必须如期完成,否则会拖延整个工程的进度,即l(i)-e(i)=0那么此活动就是关键活动。

注意:
1、关键路径上的所有活动都是关键活动,不能任意关键活动,可能导致关键活动变为非关键活动。
2、关键路径并不唯一,多余包含多条关键路径的网,需要加快所有关键路径上的关键活动才能达到缩短工期的目的。

例题

例1

1、先计算时间最早发生时间ve——从前往后,v1写0,到下一个点有多条路径出现写最大的,只要一条路径加上权值即可。

2、计算时间最迟发生时间vl——从后往前,最后一个点不变,往回倒退,多条路径可退回来选最小的,只有一条减去权值即可。

3、计算活动最早发生时间e——边的起点的最早发生时间

4、计算活动最迟发生时间l——边的终点的最晚发生时间减去边权值

5、活动最迟开始时间与与最早开始时间之差

v1v2v3v4v5v6
ve(k)032668
vl(i)042678
a1a2a3a4a5a6a7a8
e(i)00332266
l(i)10442567
l(i)-e(i)10110301

例2

2013年统考

即:

所以选c。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注