408 高频考点精讲:关键路径(Critical Path Method in AOE Network)¶
模块归属:数据结构 · 图结构及应用
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:4 次(2016~2025 年:2019#5、2020#8、2022#7、2025#42)
- 历年总考查频次:6 次(含 2013#8、2014#8)
- 出题形式:单项选择题与综合解答题并重。2025 年以算法应用大题压轴形式呈现(第 42 题,分值 10 分),此前以单项选择题形式考查基础参数计算与概念辨析。
- 命题特点:
- 考查深度梯次递增:早年集中于关键路径概念辨析(最长路径而非边数最多)与单一活动参数计算(最早/最迟开始时间);近年来重点转向活动时间余量(总时差)的横向比较、多条关键路径的动态演化、工期压缩极限分析以及并行活动的执行区间判定。
- 算法逻辑严密:高度依赖拓扑排序与逆拓扑排序两个正反向动态规划递推过程,涉及事件参数(\(ve, vl\)$ \text{)与活动参数(} $\(e, l\))的严格转换。
- 综合性与工程性强:试题常以实际工程调度为背景,考查延期分析、资源瓶颈识别与调度优化策略。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
- - - √ √ - √ - - √
(#5) (#8) (#7) (#42)
二、 具体考察内容¶
1. AOE 网的基本模型与图论定义¶
在带权有向无环图(Directed Acyclic Graph, DAG)中,根据顶点与边所代表的工程实体不同,网络图分为两类: * AOV 网(Activity on Vertex Network):顶点表示活动,边表示活动之间的优先制约关系。 * AOE 网(Activity on Edge Network):有向边表示活动(Activity),边的权值表示该活动的持续时间(Duration);顶点表示事件(Event),事件是其所有入边代表的活动已经完成、其所有出边代表的活动可以启动的时点标志。
AOE 网的形式化约定¶
- 源点(Source)与汇点(Sink):
- 网中仅存在一个入度为 0 的顶点,称为源点,表示整个工程的开始。
- 网中仅存在一个出度为 0 的顶点,称为汇点,表示整个工程的结束。
- 若实际工程存在多个起始点或结束点,可通过引入权值为 0 的虚拟边将其连接至统一的虚拟源点或虚拟汇点。
- 事件发生与活动启动的制约条件:
- 只有在进入某事件顶点的所有活动全部完成后,该事件才能发生。
- 只有在某事件发生之后,从该顶点出发的各项活动才能开始执行。
2. 四大核心时间参数的递推体系¶
设 AOE 网为 \(G = (V, E)\)$ \text{,其中顶点集合} $\(V = \{v_1, v_2, \dots, v_n\}\)$ \text{,边集合} $\(E\)$ \text{。活动} $\(a_i = \langle v_j, v_k \rangle\)$ \text{表示从事件} $\(v_j\)$ \text{到事件} $\(v_k\)$ \text{的活动,其持续时间记为} $\(\text{weight}(a_i)\)。
a_i = <v_j, v_k>, weight(a_i)
(v_j) -----------------------------> (v_k)
事件 j 事件 k
ve(j) ve(k)
vl(j) vl(k)
活动 a_i:
最早开始时间 e(i) = ve(j)
最迟开始时间 l(i) = vl(k) - weight(a_i)
时间余量 TF(i) = l(i) - e(i)
(1)事件最早发生时间 \(ve(k)\)(Earliest Event Time)¶
- 定义:从源点 \(v_1\)$ \text{到顶点} $\(v_k\)$ \text{的最长路径长度。只有该最长路径上的所有活动全部执行完成,事件} $\(v_k\) 才能发生。
- 计算规则:按拓扑序列正向递推,源点初始化为 0,其余顶点取各前驱路径的最大值: $\(ve(v_1) = 0\)$ $\(ve(v_k) = \max_{v_j \in P(v_k)} \{ ve(v_j) + \text{weight}(\langle v_j, v_k \rangle) \}\)$ 其中 \(P(v_k)\)$ \text{为顶点} $\(v_k\) 的直接前驱顶点集。
- 工程含义:决定了从 \(v_k\) 发出的所有活动能够启动的最早物理边界。
(2)事件最迟发生时间 \(vl(j)\)(Latest Event Time)¶
- 定义:在不推迟整个工程完成时间(即汇点 \(v_n\)$ \text{的最早发生时间} $\(ve(v_n)\)$ \text{)的前提下,事件} $\(v_j\) 允许发生的最迟时间。
- 计算规则:按逆拓扑序列反向递推,汇点初始化为其最早发生时间,其余顶点取各后继要求的最小值: $\(vl(v_n) = ve(v_n)\)$ $\(vl(v_j) = \min_{v_k \in S(v_j)} \{ vl(v_k) - \text{weight}(\langle v_j, v_k \rangle) \}\)$ 其中 \(S(v_j)\)$ \text{为顶点} $\(v_j\) 的直接后继顶点集。
- 工程含义:该时点是后继活动按计划完工所允许的最晚启动基准。
(3)活动最早开始时间 \(e(i)\)(Earliest Activity Start Time)¶
- 定义:活动 \(a_i\) 允许开始的最早时刻。
- 计算规则:活动必须在它的起点事件发生后才能启动,因此活动的最早开始时间等于其起点事件的最早发生时间: $$ \text{e(i) = ve(v_j), \quad \text{其中 } a_i = \langle v_j, v_k \rangle} $$
(4)活动最迟开始时间 \(l(i)\)(Latest Activity Start Time)¶
- 定义:在保证整个工程不延期的情况下,活动 \(a_i\) 必须开始的最迟时刻。
- 计算规则:活动的完成时间不得晚于其终点事件的最迟发生时间,因此其最迟开始时间等于终点事件的最迟发生时间减去该活动的持续时间: $$ \text{l(i) = vl(v_k) - \text{weight}(a_i), \quad \text{其中 } a_i = \langle v_j, v_k \rangle} $$
(5)活动完成时间衍生参数¶
- 活动最早完成时间:\(ef(i) = e(i) + \text{weight}(a_i) = ve(v_j) + \text{weight}(a_i)\)
- 活动最迟完成时间:\(lf(i) = l(i) + \text{weight}(a_i) = vl(v_k)\)
3. 时间余量、关键活动与关键路径¶
(1)活动时间余量(Total Float, \(TF(i)\),又称总时差)¶
- 定义:活动的最迟开始时间与最早开始时间之差(亦等于最迟完成时间与最早完成时间之差): $\(TF(i) = l(i) - e(i) = lf(i) - ef(i)\)$ 将事件参数代入可得统一计算公式: $\(TF(i) = vl(v_k) - ve(v_j) - \text{weight}(a_i)\)$
- 代数性质:恒有 \(TF(i) \ge 0\)。 证明:根据逆拓扑反推定义,对于任意边 \(\langle v_j, v_k \rangle\)$ \text{,必有} $\(vl(v_j) \le vl(v_k) - \text{weight}(\langle v_j, v_k \rangle)\)$ \text{;又因任何事件的最迟发生时间不早于最早发生时间,即} $\(ve(v_j) \le vl(v_j)\),故: $\(TF(i) = vl(v_k) - \text{weight}(\langle v_j, v_k \rangle) - ve(v_j) \ge vl(v_j) - ve(v_j) \ge 0\)$
- 物理意义:该活动在不影响整个工程总工期的前提下,可以拖延或持续时间延长的最大裕量。
(2)自由时差(Free Float, \(FF(i)\))¶
- 定义:在不影响所有紧后活动最早开始时间的前提下,活动 \(a_i\) 允许延误的时间: $\(FF(i) = ve(v_k) - ve(v_j) - \text{weight}(a_i)\)$
- 性质:恒有 \(0 \le FF(i) \le TF(i)\)$ \text{。当且仅当终点事件} $\(v_k\)$ \text{的最早发生时间等于其最迟发生时间(} $\(ve(v_k) = vl(v_k)\)$ \text{)时,} $\(FF(i) = TF(i)\)。
(3)关键活动(Critical Activity)¶
- 充要条件:时间余量为零的活动,即满足: $\(TF(i) = 0 \iff l(i) = e(i)\)$
- 工程含义:关键活动没有任何时间储备,其实际工期的任何延长都会直接导致整个工程延期。
(4)关键路径(Critical Path)¶
- 定义:从源点到汇点具有最大路径长度(路径上各活动持续时间之和最大)的路径。
- 关键路径与工程工期:关键路径的长度即为完成整个工程所需的最短时间(总工期)。
- 关键路径与关键活动的关系:
- 关键路径上的所有活动必定全部是关键活动。
- 由关键活动串联起来的从源点到汇点的路径即为关键路径。
(5)关键事件与关键活动的判定陷阱¶
- 关键事件:满足 \(ve(v) = vl(v)\) 的顶点称为关键事件。
- 重要辨析:
- 关键路径上的所有顶点必定是关键事件;
- 两个关键事件之间的活动不一定是关键活动。 反例:设顶点 \(v_j, v_k\)$ \text{均为关键事件,即} $\(ve(v_j) = vl(v_j)\)$ \text{且} $\(ve(v_k) = vl(v_k)\)$ \text{。若存在一条弧} $\(a = \langle v_j, v_k \rangle\)$ \text{,其持续时间} $\(\text{weight}(a) < ve(v_k) - ve(v_j)\)$ \text{,则该活动的时间余量} $\(TF(a) = vl(v_k) - ve(v_j) - \text{weight}(a) > 0\)$ \text{,故活动} $\(a\) 不是关键活动。
- 活动 \(a_i = \langle v_j, v_k \rangle\) 成为关键活动的充要条件是: $\(ve(v_j) + \text{weight}(a_i) = vl(v_k)\)$
4. 关键路径的动态演化与工程调度法则¶
(1)关键路径的多重性¶
AOE 网中从源点到汇点的最长路径可能不止一条,即可能存在两条或多条长度并列第一的关键路径。
(2)延长活动的效应(非对称性)¶
- 延长任一关键活动的时间:必定延长整个工程的工期。 原理:关键活动位于最长路径上,延长任何一个关键活动的持续时间,都会使该关键路径的长度变长,因而总工期必然增加。
- 延长非关键活动的时间:
- 若延长时间 \(\Delta t \le TF(i)\),不会影响总工期;
- 若延长时间 \(\Delta t > TF(i)\),超出部分将转化为总工期的延期,且该非关键路径将演变为新的关键路径。
(3)缩短关键活动的效应(协同性与压缩极限)¶
- 单关键路径情形:缩短关键路径上的任意关键活动,都会缩短工程工期。
- 多关键路径情形:单单缩短其中一条关键路径上的关键活动,不能缩短整个工程的工期。必须采取以下两种方式之一:
- 缩短所有关键路径所共有的关键活动;
- 同时缩短每一条关键路径上各自的关键活动。
- 压缩极限与路径转移:
- 压缩某一关键活动的时间存在上限。
- 当压缩幅度过大时,该关键路径的长度会减小到小于或等于原本的次长路径长度。此时,原次长路径转变为新的关键路径。继续单方面压缩该活动,工程总工期将不再减少。
5. 并行活动(并发执行区间)判定模型¶
在工程调度问题中,若要求以最短时间完成工程,必须准确识别在某一特定时间段内能够同时执行的活动集合。
(1)活动的时间执行窗口¶
对于任意活动 \(a_i = \langle v_j, v_k \rangle\)$ \text{,其持续时间为} $\(d_i = \text{weight}(a_i)\): * 最早可能执行区间:\([e(i), e(i) + d_i] = [ve(v_j), ve(v_j) + d_i]\) * 最迟必须执行区间:\([l(i), l(i) + d_i] = [l(i), vl(v_k)]\) * 整个活动所占用的有效时域范围:\([ve(v_j), vl(v_k)]\)
(2)两活动能够并行的充分必要条件¶
设有两个活动 \(a_1, a_2\),它们能够同时进行必须同时满足: 1. 拓扑不可达性(无先后依赖约束):在 AOE 网中,\(a_1\)$ \text{的终点到} $\(a_2\)$ \text{的起点不存在有向路径,且} $\(a_2\)$ \text{的终点到} $\(a_1\) 的起点也不存在有向路径(两者无拓扑先后顺序); 2. 时域存在交集:两活动各自的执行时间区间存在非空的重叠时段。 * 特别地,对于关键活动,由于 \(e(i) = l(i)\)$ \text{,其执行区间严格固定为} $\([e(i), e(i) + d_i]\)。任意其他非关键活动只要其时域窗口与该固定区间相交,即存在并发执行的调度可行性。
6. 关键路径算法实现流程与时间复杂度分析¶
+-----------------------------------------------------------+
| 步骤 1: 拓扑排序计算 ve[] |
| - 统计各顶点入度 inDegree[],源点入队 |
| - 拓扑出队,正向松弛更新后继顶点: ve[k] = max(ve[k], ve[j] + w)|
| - 若出队顶点数小于 n,则网中含环,算法终止 |
+-----------------------------------------------------------+
|
v
+-----------------------------------------------------------+
| 步骤 2: 逆拓扑排序计算 vl[] |
| - 利用拓扑序列的逆序(或栈结构)反向遍历顶点 |
| - 汇点初始化: vl[汇点] = ve[汇点] |
| - 逆向松弛更新前驱顶点: vl[j] = min(vl[j], vl[k] - w) |
+-----------------------------------------------------------+
|
v
+-----------------------------------------------------------+
| 步骤 3: 遍历所有边计算活动参数 |
| - 对每条弧 a_i = <v_j, v_k>, 权值为 w: |
| e[i] = ve[j] |
| l[i] = vl[k] - w |
| TF[i] = l[i] - e[i] |
| - 若 TF[i] == 0,标记 a_i 为关键活动,加入关键路径集合 |
+-----------------------------------------------------------+
时间与空间复杂度分析¶
- 时间复杂度:
- 基于邻接表表示的 AOE 网,计算入度与拓扑排序耗时 \(O(|V| + |E|)\);
- 逆拓扑排序遍历所有顶点的出边,耗时 \(O(|V| + |E|)\);
- 遍历所有边求 \(e(i), l(i)\)$ \text{耗时} $\(O(|E|)\);
- 总时间复杂度为 \(O(|V| + |E|)\)。
- 空间复杂度:
- 需要维护 \(ve[\cdot], vl[\cdot]\)$ \text{数组、入度数组以及拓扑序列栈,空间复杂度为} $\(O(|V|)\)。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2025 年 408 第 42 题 · 综合应用解答题¶
题目
某工程由 12 个活动组成,其对应的 AOE 网如下图所示。顶点 1 为工程源点,顶点 5 为工程汇点。各活动的持续时间分别为:
\(a(1 \to 3) = 2\),\(b(1 \to 2) = 5\),\(c(3 \to 2) = 1\),\(d(3 \to 6) = 3\),\(e(3 \to 4) = 3\),\(f(6 \to 5) = 4\),\(g(4 \to 6) = 1\),\(h(4 \to 7) = 4\)$ \text{(标记为活动} $\(m\)),\(j(4 \to 5) = 1\),\(k(2 \to 5) = 2\),\(m(4 \to 7) = 4\),\(n(7 \to 5) = 3\)。
(2)
^ | \
b=5/ |c=1 \ k=2
/ v \
(1) -> (3) (5) [汇点]
\ | ^ ^
a=2\ |e=3 / |
v v /j=1|
(4) | n=3
/ \ |
g=1/ \m=4 |
v v |
(6) ----> (7)
f=4 (至5)
请回答下列问题:
(1) 完成该工程的最短时间是多少?哪些是关键活动?
(2) 若以最短时间完成工程,则与活动 \(e\) 同时进行的活动可能有哪些?
(3) 时间余量最大的活动是哪个?其时间余量是多少?
(4) 假设工程从时刻 0 启动,因某种原因,活动 \(b\)$ \text{在时刻 6 开始,为保证工程不延期,在其它活动持续时间保持不变的情况下,} $\(b\)$ \text{的持续时间最多是多少?若不改变} $\(b\) 的持续时间,则压缩哪个活动的持续时间也能保证工程不延期?
【解析】¶
1. 第一问:求解工期与关键活动¶
第一步:求各事件的最早发生时间 \(ve\)(按拓扑序列正推,取最大值)
* 源点初始化:\(ve(1) = 0\)
* 顶点 3:只有入弧 \(\langle 1, 3 \rangle\)$ \text{(活动} $\(a\)),\(ve(3) = ve(1) + 2 = 2\)
* 顶点 4:只有入弧 \(\langle 3, 4 \rangle\)$ \text{(活动} $\(e\)),\(ve(4) = ve(3) + 3 = 5\)
* 顶点 6:有入弧 \(\langle 3, 6 \rangle\)$ \text{(活动} $\(d\)$ \text{)与} $\(\langle 4, 6 \rangle\)$ \text{(活动} $\(g\)),
\(ve(6) = \max\{ ve(3) + 3, ve(4) + 1 \} = \max\{ 2 + 3, 5 + 1 \} = 6\)
* 顶点 7:只有入弧 \(\langle 4, 7 \rangle\)$ \text{(活动} $\(m\)),\(ve(7) = ve(4) + 4 = 9\)
* 顶点 2:有入弧 \(\langle 1, 2 \rangle\)$ \text{(活动} $\(b\)$ \text{)与前驱输入,在不延误网络中,} $\(ve(2)\)$ \text{根据各入边前驱综合确定;若由} $\(1 \to 2\)$ \text{直接驱动,} $\(ve(2) = 5\)(若存在其他紧前活动约束,按图示汇聚计算)
* 汇点 5:汇聚多条入弧:
来自顶点 7(活动 \(n\)):\(ve(7) + 3 = 9 + 3 = 12\)
来自顶点 6(活动 \(f\)):\(ve(6) + 4 = 6 + 4 = 10\)
来自顶点 4(活动 \(j\)):\(ve(4) + 1 = 5 + 1 = 6\)
来自顶点 2(活动 \(k\)):\(ve(2) + 2 = 5 + 2 = 7\)
取最大值:\(ve(5) = \max\{ 12, 10, 6, 7 \} = 12\)
完成该工程的最短时间为 12。
第二步:求各事件的最迟发生时间 \(vl\)(按逆拓扑序列反推,取最小值)
* 汇点初始化:\(vl(5) = ve(5) = 12\)
* 顶点 7:出弧至顶点 5(活动 \(n\)),\(vl(7) = vl(5) - 3 = 12 - 3 = 9\)
* 顶点 6:出弧至顶点 5(活动 \(f\)),\(vl(6) = vl(5) - 4 = 12 - 4 = 8\)
* 顶点 2:出弧至顶点 5(活动 \(k\)),\(vl(2) = vl(5) - 2 = 12 - 2 = 10\)
* 顶点 4:出弧至 6(活动 \(g\)$ \text{)、7(活动} $\(m\)$ \text{)、5(活动} $\(j\)),
$vl(4) = \min{ vl(6)
-
1, vl(7)
-
4, vl(5)
-
1 } = \min{ 8
-
1, 9
-
4, 12
-
1 } = \min{ 7, 5, 11 } = 5$
- 顶点 3:出弧至 4(活动 \(e\)$ \text{)、6(活动} $\(d\)),
\(vl(3) = \min\{ vl(4) - 3, vl(6) - 3 \} = \min\{ 5 - 3, 8 - 3 \} = \min\{ 2, 5 \} = 2\) - 源点 1:\(vl(1) = \min\{ vl(3) - 2, vl(2) - 5 \} = \min\{ 2 - 2, 10 - 5 \} = 0\)
事件时间参数汇总表:
| 顶点序号 | \(ve\) | \(vl\) | 关键事件判定 |
|---|---|---|---|
| 1 | 0 | 0 | 是 |
| 2 | 5(或拓扑值) | 10 | 否 |
| 3 | 2 | 2 | 是 |
| 4 | 5 | 5 | 是 |
| 5 | 12 | 12 | 是 |
| 6 | 6 | 8 | 否 |
| 7 | 9 | 9 | 是 |
第三步:计算关键活动
关键活动判定条件为 $$ \text{TF(i) = vl(\text{终点}) - ve(\text{起点}) - \text{持续时间} = 0} $$:
* 活动 \(a(1 \to 3)\):\(TF(a) = vl(3) - ve(1) - 2 = 2 - 0 - 2 = 0\) \(\implies\) 关键活动
* 活动 \(e(3 \to 4)\):\(TF(e) = vl(4) - ve(3) - 3 = 5 - 2 - 3 = 0\) \(\implies\) 关键活动
* 活动 \(m(4 \to 7)\):\(TF(m) = vl(7) - ve(4) - 4 = 9 - 5 - 4 = 0\) \(\implies\) 关键活动
* 活动 \(n(7 \to 5)\):\(TF(n) = vl(5) - ve(7) - 3 = 12 - 9 - 3 = 0\) \(\implies\) 关键活动
关键活动为:\(a, e, m, n\)$ \text{(构成的关键路径为} $\(1 \to 3 \to 4 \to 7 \to 5\))。
2. 第二问:分析与活动 e 同时进行的活动¶
- 活动 \(e\) 位于关键路径上,其起点为事件 3,终点为事件 4。
- 关键事件 3 的发生时间为时刻 2,关键事件 4 的发生时间为时刻 5。
- 活动 \(e\)$ \text{的执行时间区间严格固定为 } $\([2, 5]\)。
- 考察网中其他活动在工程以最短时间 12 完成时的执行窗口:
- 活动 \(b\)$ \text{:起点为事件 1,最早可在时刻 0 开始,持续时间为 5,其最早执行区间为} $\([0, 5]\)$ \text{。在时刻} $\(2 \sim 5\)$ \text{之间,活动} $\(b\)$ \text{正在执行,故活动} $\(b\)$ \text{可以与} $\(e\) 同时进行。
- 活动 \(d(3 \to 6)\)$ \text{:起点为事件 3,持续时间为 3。事件 3 在时刻 2 发生,活动} $\(d\)$ \text{最早可在时刻 2 启动,执行区间可为} $\([2, 5]\)$ \text{。故活动} $\(d\)$ \text{可以与} $\(e\) 同时进行。
- 活动 \(c\)$ \text{:作为与顶点 3 或 2 相关的分支活动,其持续时间为 1,在时刻} $\([2, 5]\) 之间同样具备可调度性。
- 与活动 \(e\)$ \text{可能同时进行的活动为:} $\(b, d, c\)。
3. 第三问:计算最大时间余量¶
活动的时间余量计算公式为:$$ \text{TF(i) = vl(\text{终点}) - ve(\text{起点}) - \text{持续时间}} $$。
分别计算各非关键活动的时间余量:
* 活动 \(j(4 \to 5)\):持续时间为 1。
$\(TF(j) = vl(5) - ve(4) - 1 = 12 - 5 - 1 = 6\)$
* 活动 \(d(3 \to 6)\):持续时间为 3。
$\(TF(d) = vl(6) - ve(3) - 3 = 8 - 2 - 3 = 3\)$
* 活动 \(g(4 \to 6)\):持续时间为 1。
$\(TF(g) = vl(6) - ve(4) - 1 = 8 - 5 - 1 = 2\)$
* 活动 \(f(6 \to 5)\):持续时间为 4。
$\(TF(f) = vl(5) - ve(6) - 4 = 12 - 6 - 4 = 2\)$
* 活动 \(b(1 \to 2)\)$ \text{与} $\(k(2 \to 5)\)$ \text{:总富余时间不超过} $\(12 - 7 = 5\)。
对比可知,时间余量最大的活动是 \(j\),其时间余量为 6。
4. 第四问:活动 b 延期与工期优化计算¶
工程从时刻 0 启动。若活动 \(b\) 在时刻 6 才开始执行:
1. 确定路径约束不等式:
包含活动 \(b\)$ \text{的工程路径为} $\(1 \xrightarrow{b} 2 \xrightarrow{k} 5\)。
到达汇点 5 的完工时刻为:
$$ \text{T_{\text{完成}} = \text{开始时刻}(b) + \text{duration}(b) + \text{duration}(k)} $$
将已知参数代入:
$$ \text{T_{\text{完成}} = 6 + \text{duration}(b) + 2 = 8 + \text{duration}(b)} $$
2. 求解 \(b\) 的最大持续时间:
为保证工程不延期,总工期不得超过 12:
$\(8 + \text{duration}(b) \le 12 \implies \text{duration}(b) \le 4\)$
在其它活动持续时间不变的情况下,\(b\) 的持续时间最多是 4。
3. 不改变 \(b\) 的持续时间时的压缩策略:
若保持 \(\text{duration}(b) = 5\) 不变,则该路径耗时为:
$\(6 + 5 + \text{duration}(k) \le 12 \implies \text{duration}(k) \le 1\)$
已知原 \(\text{duration}(k) = 2\)$ \text{。因此,只需将后续活动 } $\(k\) 的持续时间压缩至 1(压缩 1 个时间单位),即可确保工程不延期。
【正确答案】¶
(1) 最短时间为 12;关键活动为 \(a, e, m, n\)。
(2) 可能同时进行的活动有 \(b, d, c\)。
(3) 时间余量最大的活动是 \(j\),其时间余量是 6。
(4) \(b\)$ \text{的持续时间最多是 4;若不改变} $\(b\)$ \text{的持续时间,压缩活动 } $\(k\) 的持续时间也能保证工程不延期(压缩为 1)。
【真题 2】2022 年 408 第 7 题 · 时间余量极值比较¶
题目
下图是一个有 10 个活动的 AOE 网,时间余量最大的活动是( )。
a=2 d=3 f=4
(1) -------> (2) -------> (4) -------> (6)
\ ^ | ^
\b=5 |c=1 h=1| j=1|
\ | v |
------> (3) --------> (5) ---------
g=1
A. \(c\) B. \(g\) C. \(h\) D. \(j\)
【解析】¶
1. 计算各事件的最早发生时间 ve(拓扑正推)¶
- 顶点 1(源点):\(ve(1) = 0\)
- 顶点 2:入弧来自 1(权值 2),\(ve(2) = ve(1) + 2 = 2\)
- 顶点 3:入弧来自 1(权值 5)、2(活动 \(c\),权值 1),
\(ve(3) = \max\{ ve(1) + 5, ve(2) + 1 \} = \max\{ 5, 2 + 1 \} = 5\) - 顶点 4:入弧来自 3(权值 3),\(ve(4) = ve(3) + 3 = 5 + 3 = 8\)
- 顶点 5:入弧来自 4(活动 \(h\)$ \text{,权值 1),} $\(ve(5) = ve(4) + 1 = 8 + 1 = 9\)
- 顶点 6(汇点):入弧来自 4(活动 \(f\)$ \text{,权值 4)、3(活动} $\(g\)$ \text{,权值 1)、5(活动} $\(j\),权值 1),
\(ve(6) = \max\{ ve(4) + 4, ve(3) + 1, ve(5) + 1 \} = \max\{ 8 + 4, 5 + 1, 9 + 1 \} = \max\{ 12, 6, 10 \} = 12\)
2. 计算各事件的最迟发生时间 vl(逆拓扑反推)¶
- 顶点 6(汇点):\(vl(6) = ve(6) = 12\)
- 顶点 5:出弧至 6(权值 1),\(vl(5) = vl(6) - 1 = 12 - 1 = 11\)
- 顶点 4:出弧至 6(权值 4)、5(权值 1),
\(vl(4) = \min\{ vl(6) - 4, vl(5) - 1 \} = \min\{ 12 - 4, 11 - 1 \} = \min\{ 8, 10 \} = 8\) - 顶点 3:出弧至 4(权值 3)、6(权值 1),
\(vl(3) = \min\{ vl(4) - 3, vl(6) - 1 \} = \min\{ 8 - 3, 12 - 1 \} = \min\{ 5, 11 \} = 5\) - 顶点 2:出弧至 3(权值 1),\(vl(2) = vl(3) - 1 = 5 - 1 = 4\)
- 顶点 1:\(vl(1) = \min\{ vl(2) - 2, vl(3) - 5 \} = \min\{ 4 - 2, 5 - 5 \} = 0\)
3. 计算选项中各活动的时间余量¶
活动时间余量公式:$$ \text{TF = vl(\text{终点}) - ve(\text{起点}) - \text{持续时间}} $$。
* 选项 A(活动 \(c\)):起点为 2,终点为 3,持续时间为 1。
$\(TF(c) = vl(3) - ve(2) - 1 = 5 - 2 - 1 = 2\)$
* 选项 B(活动 \(g\)):起点为 3,终点为 6,持续时间为 1。
$\(TF(g) = vl(6) - ve(3) - 1 = 12 - 5 - 1 = 6\)$
* 选项 C(活动 \(h\)):起点为 4,终点为 5,持续时间为 1。
$\(TF(h) = vl(5) - ve(4) - 1 = 11 - 8 - 1 = 2\)$
* 选项 D(活动 \(j\)):起点为 5,终点为 6,持续时间为 1。
$\(TF(j) = vl(6) - ve(5) - 1 = 12 - 9 - 1 = 2\)$
数值对比:\(TF(g) = 6 > TF(c) = TF(h) = TF(j) = 2\)$ \text{。时间余量最大的活动是} $\(g\)。
正确答案:B
【真题 3】2020 年 408 第 8 题 · 关键路径与工期性质辨析¶
题目
若使用 AOE 网估算工程进度,则下列叙述中正确的是( )。
A. 关键路径是从源点到汇点边数最多的一条路径
B. 关键路径是从源点到汇点路径长度最长的路径
C. 增加任一关键活动的时间不会延长工程的工期
D. 缩短任一关键活动的时间将会缩短工程的工期
【解析】¶
- 选项 A 辨析:错误。关键路径的定义依据是路径长度(即路径上所有活动持续时间的代数和),而非边(活动)的数量。一条仅包含少数高耗时活动的路径,其权值和完全可能远大于包含大量短耗时活动的路径。
- 选项 B 辨析:正确。AOE 网中,从源点到汇点的具有最大路径长度的路径即为关键路径,该长度决定了完成工程所需的最短总工期。
- 选项 C 辨析:错误。关键活动必定位于最长路径上。若增加任何一个关键活动的持续时间,将直接导致该关键路径的长度增加,工程总工期必然随之延长。
- 选项 D 辨析:错误。当 AOE 网中存在两条或多条关键路径时,若仅仅缩短其中一条关键路径上的某个非共有关键活动,其他关键路径的长度并未改变,整个工程的工期依然由其他关键路径决定,工期不会缩短。只有缩短所有关键路径共有的关键活动,或者同时缩短各关键路径上的关键活动,才能缩短工期。此外,若压缩幅度过大,原本的关键路径可能变为非关键路径,产生压缩极限。
正确答案:B
【真题 4】2019 年 408 第 5 题 · 活动最早与最迟开始时间求解¶
题目
下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 \(d\) 的最早开始时间和最迟开始时间分别是( )。
(2) ------ d=7 ------> (4)
^ \ ^ \
a=3/ \ | \ g=6
/ c=8 \ e=6 | \
(1) v | v
\ (3) -------------/ (6) [汇点]
b=4\ f=10 ^
v | h=9
... -----------------------------
A. 3 和 7 B. 12 和 12 C. 12 和 14 D. 15 和 15
【解析】¶
1. 计算活动 d 的最早开始时间 \(e(d)\)¶
- 活动的最早开始时间等于其起点事件的最早发生时间。
- 活动 \(d\)$ \text{的起点为事件 2,即} $\(e(d) = ve(2)\)。
- 观察到达事件 2 的有向路径:
- 路径一:\(1 \xrightarrow{a=3} 2\),耗时为 3;
- 路径二:\(1 \xrightarrow{b=4} 3 \xrightarrow{c=8} 2\)$ \text{,耗时为} $\(4 + 8 = 12\)。
- 事件 2 必须等待其所有紧前活动均完成方可发生,取路径最大值: $\(ve(2) = \max\{ 3, 12 \} = 12\)$
- 故活动 \(d\) 的最早开始时间为: $\(e(d) = ve(2) = 12\)$
2. 计算活动 d 的最迟开始时间 \(l(d)\)¶
- 活动的最迟开始时间等于其终点事件的最迟发生时间减去该活动的持续时间。
- 活动 \(d\) 的终点为事件 4,持续时间为 7,即: $\(l(d) = vl(4) - \text{weight}(d) = vl(4) - 7\)$
- 整个工程的关键路径总长度(汇点 6 的完成时间)为 27,即 \(ve(6) = vl(6) = 27\)。
- 从汇点 6 沿后继有向边逆向推导事件 4 的最迟发生时间:
- 从事件 4 到汇点 6 的活动持续时间为 6(活动 \(g = 6\))。
- 逆推可得:\(vl(4) = vl(6) - 6 = 27 - 6 = 21\)。
- 将 \(vl(4) = 21\) 代入活动最迟开始时间公式: $\(l(d) = 21 - 7 = 14\)$
综合可得:活动 \(d\) 的最早开始时间为 12,最迟开始时间为 14。
正确答案:C
四、 核心解题套路与易错陷阱¶
1. 核心解题套路¶
套路一:“正推取大,逆推取小”双向参数速算法¶
面对 AOE 网求解大题或多参数计算题,统一采用三步列阵法: 1. 正推算 \(ve\)$ \text{:按拓扑顺序从源点向后推进,源点设为 0。遇到多条入边汇聚的顶点,取所有分支累加值的最大值(} $\(\max\)$ \text{)。汇点算得的} $\(ve\) 即为整个工程的最短总工期。 2. 逆推算 \(vl\)$ \text{:按逆拓扑顺序从汇点向前倒推,汇点设为} $\(vl = ve\)$ \text{。遇到从该顶点分出的多条出边,取各分支反向减去边权后的最小值(} $\(\min\))。 3. 查边求 \(TF\)$ \text{:对目标边} $\(\langle u, v \rangle\),代入统一差值公式: $$e = ve(u), \quad l = vl(v)
-
\text{weight}, \quad TF = l
-
e = vl(v)
-
ve(u)
-
\text{weight}$$ 若 \(TF = 0\),即判定为关键活动。
套路二:时间余量极值题的“结构快筛法”¶
选择题若要求快速找出“时间余量最大的活动”,无须计算所有边: * 时间余量公式 \(TF = vl(v) - ve(u) - w\)$ \text{表明:起点} $\(u\)$ \text{发生越早(} $\(ve(u)\)$ \text{极小)、终点} $\(v\)$ \text{要求越晚(} $\(vl(v)\)$ \text{极大)、边权} $\(w\) 越小的跨层长弧,时间余量必然最大。 * 重点排查直接跨越多层、连接网络前端与后端的“细长旁路”(如 2022 年第 7 题中的弧 \(g(3 \to 6)\),边权仅为 1,直接跨越多个中间阶段直达汇点)。
套路三:工程延期与工期调整的“路径不等式法”¶
解答题涉及活动延期、工期压缩时,严禁凭直觉估算,必须建立路径累加方程: 1. 找出包含目标活动的所有自源点至汇点的有向路径; 2. 设目标活动实际开始时间为 \(T_{\text{start}}\)$ \text{,持续时间为} $\(d\); 3. 对每条包含该活动的路径列出完工不等式: $$ \text{T_{\text{start}} + d + \sum_{\text{后续路径}} \text{weight} \le T_{\text{总工期}}} $$ 4. 联立求解不等式,即可得到该活动允许的最大持续时间,或需压缩的紧后关键活动耗时。
2. 易错陷阱防线¶
+---------------------------------------------------------------------------------------+
| 常见命题陷阱及学术反驳 |
+=======================================================================================+
| 陷阱一:混淆“边数最多”与“路径权值和最大” |
| - 错误认知:认为包含活动数量最多的路径就是关键路径。 |
| - 学术纠正:关键路径严格由各边持续时间的代数和决定,与边数无关。 |
+---------------------------------------------------------------------------------------+
| 陷阱二:误以为“缩短任意关键活动均能压缩工期” |
| - 错误认知:只要挑一个关键活动缩短工期,总工期就会跟着减少。 |
| - 学术纠正:存在多条关键路径时,单独压缩一条路径上的活动无效;过度压缩会引发关键路径转移。 |
+---------------------------------------------------------------------------------------+
| 陷阱三:误将“两端均为关键事件的边”判定为关键活动 |
| - 错误认知:若 ve(u) == vl(u) 且 ve(v) == vl(v),则边 <u, v> 必为关键活动。 |
| - 学术纠正:只有当 ve(u) + weight == vl(v) 时才成立。若权值小于差值,该边仍有时间余量。 |
+---------------------------------------------------------------------------------------+
| 陷阱四:计算活动最迟开始时间 l(i) 时错用起点参数 |
| - 错误认知:误写为 l(i) = vl(起点) - weight。 |
| - 学术纠正:最迟开始时间是由终点事件倒推的,即 l(i) = vl(终点) - weight。 |
+---------------------------------------------------------------------------------------+
五、 考点速记清单¶
- 核心概念对应:
- AOE 网:顶点表示事件(瞬时状态),边表示活动(持续过程),边权表示耗时。
- 关键路径:从源点到汇点具有最大路径长度的路径,决定了完成工程的最短工期。
- 核心公式表:
- 事件最早发生时间:\(ve(k) = \max_{j} \{ ve(j) + \text{weight}(j \to k) \}\)$ \text{(拓扑正推,源点} $\(ve = 0\))
- 事件最迟发生时间:\(vl(j) = \min_{k} \{ vl(k) - \text{weight}(j \to k) \}\)$ \text{(逆拓扑反推,汇点} $\(vl = ve\))
- 活动最早开始时间:$$ \text{e(i) = ve(\text{起点})} $$
- 活动最迟开始时间:$$ \text{l(i) = vl(\text{终点}) - \text{持续时间}} $$
- 活动总时差(时间余量):$$ \text{TF(i) = l(i) - e(i) = vl(\text{终点}) - ve(\text{起点}) - \text{持续时间}} $$
- 关键活动充要条件:\(TF(i) = 0 \iff l(i) = e(i)\)
- 性质速查口诀:
- 加必延,减不一定缩:增加任何关键活动耗时必延误工期;缩短关键活动仅在单路径或多路径协同缩短时方可缩短工期。
- 点关键不保边关键:关键路径上的点必定是关键事件;两个关键事件之间的边不一定是关键活动。
- 压缩有极限:关键活动压缩到某临界值后,次长路径变为新关键路径,继续单方面压缩无效。