工程问题（图中）

AOE 网与工程进度计算（含真题拆解）

一、 核心模型（“施工队”视角）

• 顶点（圆圈）：工期节点（事件）。它不耗时，只是一个里程碑时间点（如“材料到齐”）。

• 边（带权箭头）：施工活动。边上的数字代表耗时。

• 竣工条件：终点节点被解锁。只有指向终点的所有活动全部干完，工程才叫竣工。

• 起点（源点）：只发射箭头（入度为 0）

• 终点（汇点）：只接收箭头（出度为 0）

二、 考场四大高频问题与实战例子

1. 求工程的最短完成时间与关键活动

• 大白话：多支施工队同时开工，决定交工时间的是最慢的那条流水线（耗时最长的路径）。

• 考场步骤：

  1. 计算所有路径，或者严谨地从前向后推导各节点的最早发生时间 $ve$。

  2. 到达终点的最大时间 = 最短完成时间。

  3. 没有时间余量（最早开工=最晚开工）的活动 = 关键活动。

【真题实例演示】

真题中从起点 1 到终点 5 的几条主要路径：

• 路径 ①：$1\to 2\to 5$ （耗时 $5+2=7$）

• 路径 ②：$1\to 4\to 2\to 5$ （耗时 $3+4+2=9$）

• 路径 ③：$1\to 3\to 4\to 7\to 5$ （耗时 $2+3+4+3=12$，全图最长！）

解题结果：

• 最短完成时间：12

• 关键活动：a, e, m, n

2. 判断哪些活动可以“同时进行”

• 大白话：看两个活动的可能施工时间区间是否有重叠（哪怕只有部分重叠也算）。

• 考场步骤：

  1. 锁定目标关键活动的时间段（它没有弹性，区间死板固定）。

  2. 计算其他活动的 [最早开始时间, 最晚完成时间]，看区间是否相交。

【真题实例演示】（问：与活动 $e$ 同时进行的可能活动？）

• 活动 $e$：是关键活动，严格在 [2, 5] 期间执行。

• 活动 $b$：最早时刻 0 开工，最晚时刻 10 必须完工，区间 [0, 10]。覆盖 [2, 5]，可同时！

• 活动 $d$：最早时刻 0 开工，最晚时刻 5 必须完工，区间 [0, 5]。覆盖 [2, 5]，可同时！

• 活动 $c$：最早时刻 2 开工，最晚时刻 8 必须完工，区间 [2, 8]。覆盖 [2, 5]，可同时！

（注：活动 $f,g,j,m$ 最早都要从时刻 5 开始，正好接在 $e$ 结束之后，所以不可能同时进行。最终答案为：$b,c,d$）

3. 求“时间余量”最大的活动

• 大白话：这支施工队最多可以摸鱼/延误几天而不影响整个工程按时交工。

• 公式：$\text{时间余量}=\text{最晚必须开始时间 }l-\text{最早可能开始时间 }e$

【真题实例演示】

• 关键活动（a, e, m, n）的时间余量永远为 0。

• 看活动 $j$（从 4 到 5，耗时 1）：

  • 节点 4 最早发生时刻：5 （即 $ve(4)=5$）。

  • 工程要求完工时刻：12。$j$ 耗时 1，所以最迟必须在时刻 11 开工。

  • $j$ 的时间余量 = $11-5=6$。

  • 经计算，这是全图最大值（活动 $b$ 和 $c$ 的余量均为 5）。

重点突破：第 3 问怎么算？（时间余量最大是谁）

要算“时间余量”（也就是机动时间），最稳妥、绝不会丢分的方法是计算两个核心指标：事件的最早发生时间 $ve$ 和最迟发生时间 $vl$。

核心公式：

某个活动（边）的时间余量 = 该活动的最晚必须开始时间 $-$ 该活动的最早可能开始时间

1. 求所有节点（事件）的 $ve$ 和 $vl$

   • $ve$ (最早时间，从前往后算，取最大值)：表示到达这个节点前，所有的前置工作都做完至少要多久。

     • $ve(1)=0$

     • $ve(3)=ve(1)+2=2$

     • $ve(4)=\max (ve(1)+3,ve(3)+3)=5$ （注意：节点 4 有两条路进来，必须等最慢的干完，所以取 5）

     • $ve(2)=\max (ve(1)+5,ve(4)+4)=9$ （这里是易错点！ 节点 2 不仅依赖活动 $b$，还依赖活动 $f$。$1\to 3\to 4\to 2$ 耗时是 $2+3+4=9$）

     • 同理算出：$ve(6)=6$, $ve(7)=9$, $ve(5)=12$。

   • $vl$ (最晚时间，从后往前推，取最小值)：表示为了不拖延总工期（12天），这个节点最晚必须在什么时候完工。

     • $vl(5)=12$

     • $vl(7)=vl(5)-3=9$

     • $vl(2)=vl(5)-2=10$

     • $vl(6)=vl(7)-1=8$

     • $vl(4)=\min (vl(2)-4,vl(5)-1,vl(6)-1,vl(7)-4)=5$ （节点 4 发出 4 条边，必须满足所有后续活动不延误，取最小值）

     • 以此类推，直到 $vl(1)=0$。

2. 锁定活动 $j$ 进行计算

   看图可知活动 $j$ 是一条从节点 4 直达终点节点 5 的“捷径”，耗时仅为 $1$。

   • 最早能开工的时间：就是节点 4 最早发生的时间，即 $ve(4)=5$。

   • 最晚必须开工的时间：终点 5 最晚要求在 12 时刻完工，$j$ 需要 1 天，所以 $j$ 最晚可以在 $12-1=11$ 时刻再开工。

   • 时间余量 = $11-5=6$。

   补充验证： 我们再看看看起来余量很大的活动 $b$ 和 $c$。

   • 活动 $b$：最早 $ve(1)=0$ 开始，最晚 $vl(2)-5=10-5=5$ 开始，余量为 5。

   • 活动 $c$：最早 $ve(3)=2$ 开始，最晚 $vl(6)-1=8-1=7$ 开始，余量为 5。

     都不如 $j$ 大。所以 $j$ 是时间余量最大的活动。

4. 突发事故救场分析（某活动延迟启动/超时）

• 大白话：前面耽误了，后面怎么通过“加班”补救？

• 考场步骤：

  1. 重新计算受影响节点的新到达时间。

  2. 若未超过该节点的“原最迟发生时间 $vl$”，则不延期；若超过，则会导致总工期延长。

  3. 要想不延期，必须压缩受影响节点之后新形成的关键路径上的活动。

【真题实例演示】（活动 $b$ 在时刻 6 开工）

第一问：b 的持续时间最多是多少？

1. 为了不影响总工期 12 天，节点 2 最晚必须在时刻 10 发生（因为后续的 $k$ 耗时 2）。即 $vl(2)=10$。

2. $b$ 在时刻 6 开工，要想在时刻 10 前到达节点 2，$b$ 的耗时最多为 $10-6=4$。

第二问：若不改变 $b$ 的持续时间，压缩哪个活动？

1. $b$ 在时刻 6 开工，原本耗时 5，到达节点 2 已经是 时刻 11。

2. 从节点 2 到终点 5 只剩活动 $k$。

3. 此时经过 $b$ 和 $k$ 的新路径总耗时变为 $6(等待)+5(b)+2(k)=13$，工程超期 1 天。

4. 由于规定不能改变 $b$，我们只能压缩这根藤上的后续活动 $k$。必须把 活动 $k$ 压缩 1 天（让 $k$ 加班），才能保证 12 天顺利竣工！