已知AOE网中顶点v1,v2,v3,……v7分别表示7个时间,有向线段a1,a2,a3,……a10分别表示10个活动,线段旁的数值表示每个活动花费的天数,如下图所示。请填写下面两个表格,并用顶点序列表示出关键路径,给出关键活动。

admin2014-12-08  30

问题 已知AOE网中顶点v1,v2,v3,……v7分别表示7个时间,有向线段a1,a2,a3,……a10分别表示10个活动,线段旁的数值表示每个活动花费的天数,如下图所示。请填写下面两个表格,并用顶点序列表示出关键路径,给出关键活动。
   

选项

答案[*] 关键路径:v1 v2 v5v7 v1v4v5 v7 关键活动:a1a2a4a8a9

解析 AOE网中从源点到终点的最大路径长度(这里的路径长度是指该路径上的各个活动所需时间之和)的路径称为关键路径。关键路径长度是整个工程所需的最短工期。关键路径上的活动称为关键活动。要缩短整个工期,必须加快关键活动的进度。
    寻找关键活动时所用到的几个参量的定义。
    假设第i条弧为,dut()为弧上的权值。
    (1)事件的最早发生时间ve[k]=从源点到顶点k的最长路径长度。
    ve(源点)=0;
    ve(k)=Max{ve(j)+dut()}
    (2)事件的最迟发生时间v1[j]=从顶点j到汇点的最短路径长度。
    vl(汇点)=ve(汇点);
    vl(j)=Min{v1(k)一dut()}
    (3)活动i的最早开始时间e(i)=ve(j)。
    (4)活动i的最晚开始时间l(i)=vl(k)一dut()。
    e一l的活动就是关键活动,关键活动所在的路径就是关键路径。
转载请注明原文地址:https://kaotiyun.com/show/9Oxi777K
0

最新回复(0)