🏷️ 知识点：AOE网

下面关于求关键路径的说法中，不正确的是（ ）。

A. 求关键路径是以拓扑排序为基础的 B. 一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同 C. 一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差 D. 任何一个活动的持续时间的改变可能会影响关键路径的改变

正确答案：C

结论

选 C。对弧 i→j，i 确实是弧尾；事件 i 的最迟发生时间应等于所有出边活动最迟开始时间的最小值，即 vl(i)=min(vl(j)-d(i,j))。选项 C 把活动最迟开始时间又减了一次持续时间，造成多减一次 d。

推导

按拓扑序计算 ve，再按逆拓扑序计算 vl，活动的时间余量为 vl(j)-ve(i)-d(i,j)。对每条出边 i→j，活动最迟开始时间是 vl(j)-d(i,j)；事件 i 的最迟发生时间就是这些出边活动最迟开始时间的最小值，不能再减一次 d(i,j)。详见 AOE 递推。

易错点

不要把“事件最迟发生”与“某一条出边活动的最迟开始”混为一谈；有多条出边时必须对 vl(j)-d(i,j) 取最小值，也不要把持续时间多减一次。改变任一活动持续时间也可能改变 ve、vl 或关键路径集合。

下列关于AOE网的关键路径的说法中，正确的是（ ）。

Ⅰ．改变网上某一关键路径上的任意一个关键活动后，必将产生不同的关键路径 Ⅱ．关键路径上活动的时间延长多少，整个工期也就随之延长多少 Ⅲ．缩短关键路径上任意一个关键活动的持续时间可缩短关键路径长度 Ⅳ．缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度 Ⅴ．缩短多条关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度

A. Ⅱ和Ⅴ B. Ⅰ、Ⅱ和Ⅳ C. Ⅱ和Ⅳ D. Ⅰ和Ⅳ

正确答案：C

结论

选 C，Ⅱ和Ⅳ正确。关键路径上的活动延长会等量推迟工期；要缩短工期，必须缩短所有当前关键路径共有的活动。

推导

活动松弛量为 vl(j)-ve(i)-d(i,j)，为零的活动才是关键活动。缩短只出现在一条关键路径上的活动，另一条同长路径仍会控制工期；只有覆盖全部关键路径的公共关键活动缩短，最长路径才会下降。详见 关键路径缩短条件。

易错点

“任意关键活动”不等于“所有关键路径共有的关键活动”。缩短后还需重新计算关键路径，原路径可能不再唯一；Ⅰ、Ⅲ、Ⅴ的表述都把必要条件说成了充分条件。

下表给出了某工程各工序之间的优先关系和各工序所需的时间(其中“一”表示无先 驱工序),请完成以下各题： 1)画出相应的AOE网 。 2)列出各事件的最早发生时间和最迟发生时间。 3)求出关键路径并指明完成该工程所需的最短时间。 工序代号 A B C D E F G H 所需时间 3 2 2 3 4 3 2 1

先驱工序 一 一 A A B A C、E D

[tag_link]

参考答案

可把工序表转换为下面的 AOE 边集；顶点编号只是为了表达依赖关系，虚活动可按等价方式设置。

按拓扑序正向计算事件最早发生时间，按逆拓扑序反向计算最迟发生时间：

对活动 i→j，最早开始 e=ve(i)，最迟开始 l=vl(j)-duration，时差为 l-e：

因此关键活动为 B、E、G，关键路径是 1→3→4→8，最短工期为 8 个时间单位。

易错点

活动 F 虽然直接通向汇点，但路径 1→2→8 只有 6，不决定总工期；关键活动必须满足时差为 0，不能只看是否连接汇点。