题目

某 AOE 网描述了 12 个工程活动及其持续时间（活动名跳过 i、l 避免与数字 1、字母 l 混淆）。

请回答下列问题：

(1) 完成该工程的最短时间是多少？哪些是关键活动？

(2) 若以最短时间完成工程，则与活动 e 同时进行的活动可能有哪些？

(3) 时间余量最大的活动是哪个？其时间余量是多少？

(4) 假设工程从时刻 0 启动，因某种原因，活动 b 在时刻 6 开始，为保证工程不延期，在其它活动持续时间保持不变的情况下，b 的持续时间最多是多少？若不改变 b 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？

解析

(1) 最短工期与关键活动

答案：最短工期 = 12，关键活动 a、e、m、n。关键路径：

推导——按拓扑序 v1, v3, v4, v2, v6, v7, v5 正向算 ve（取入边贡献最大值），逆序算 vl（取出边贡献最小值，从 vl(v5)=ve(v5) 起步）：

顶点	推导		推导
v1	起点	0		0
v3		2		2
v4		5		5
v2		9		10
v6		6		8
v7		9		9
v5		12	汇点	12

最短工期 = ve(v5) = 12。

再算各活动 的 、，余量 = 。余量为 0 即关键活动：

活动	弧	w	ee	le	余量	关键
a	v1→v3	2	0	0	0	★
b	v1→v2	5	0	5	5
c	v3→v6	1	2	7	5
d	v1→v4	3	0	2	2
e	v3→v4	3	2	2	0	★
f	v4→v2	4	5	6	1
g	v4→v6	1	5	7	2
h	v6→v7	1	6	8	2
j	v4→v5	1	5	11	6
k	v2→v5	2	9	10	1
m	v4→v7	4	5	5	0	★
n	v7→v5	3	9	9	0	★

编者注（生僻术语）：「时间余量」也叫松弛时间 / slack = 。这张表是后续 (2)(3)(4) 所有问题的"原始数据"，先算出来再回答更省事。

(2) 与活动 e 同时进行的活动

答案：b、c、d。

活动 e 是关键活动，时间窗被锁死在 执行。非关键活动 X 可在 任选起始时刻 ，占用 。X 能与 e 同时进行 ⟺ 存在 使 与 有正长度交集，等价于：

逐项检查（关键活动 a/e/m/n 跳过）：

活动			满足？
b	0	10	✓
c	2	8	✓
d	0	5	✓
f	5	10	✗（）
g	5	8	✗
h	6	9	✗
j	5	12	✗
k	9	12	✗

编者注（生僻术语）：题问「可能有哪些」——是「存在某个合法调度让两者重叠」的活动，不要求必然同时。看窗口能否相交即可。

(3) 时间余量最大的活动

答案：活动 j（v4→v5），余量 = 6。

直观地：j 工期 1，但从最早能开始的时刻 5 到必须完成的时刻 12 有 7 单位窗口，松弛 6 单位——即使 j 比理想推迟 6 个单位再开始，工程仍能 12 天完工。

(4) 活动 b 在时刻 6 才开始

(4a) 保持其他活动不变，b 的持续时间最多是多少？答案：4。

b 推迟到时刻 6 开始只改变 b 自己的执行窗口，其余顶点 ve/vl 不变。要不延期，b 必须不晚于 完成：

(4b) 不改 b 的持续时间（仍为 5），压缩哪个活动？答案：压缩 k（v2→v5）1 单位（从 2 减到 1）。

b 持续 5、从时刻 6 开始 → b 在时刻 11 完成 → （原本 9）。传到 v5：

要追回 1 单位，必须压缩当前最长路径 上、且不是 b 的活动——只剩 k。k 从 2 压到 1：

压缩 f、n 等其他活动都没用——它们不在当前最长路径上，压缩后 v2 路径仍是 13。