用Octave计算关键路径法（CPM）问题
广告
{{v.name}}
关键路径法（Critical Path Method, CPM）是项目进度管理的核心运筹学方法，核心是通过分析项目中各活动的时间依赖关系，计算关键时间参数、识别关键活动和关键路径，最终确定项目的最短完成工期，并明确哪些活动的延迟会直接导致总工期延长（关键活动），为项目进度管控、资源调配提供依据。
CPM的核心前提是活动持续时间为确定值（若持续时间随机，用计划评审技术PERT），计算围绕正推法（算最早时间）和逆推法（算最迟时间）展开，最终通过总时差判定关键路径，以下从核心概念、手动计算步骤、Octave代码实现、扩展场景全维度讲解，零基础可直接落地。
一、CPM核心基础概念
1. 项目活动分解与表示
将项目拆解为若干独立活动，明确活动的持续时间和先后依赖关系（紧前/紧后活动），常用活动节点图（AON） 表示（节点=活动，箭线=依赖关系，最通用），也可用箭线图（AOA，箭线=活动），本文以AON为例。
2. 5个核心时间参数
所有计算围绕这5个参数展开，是判定关键路径的基础，设活动\(i\)的持续时间为\(t_i\)：
| 参数 | 符号 | 核心含义 | 计算公式 |
|--------------|------|--------------------------------------------------------------------------|------------------------------|
| 最早开始时间 | \(ES\) | 活动最早能开始的时间（需所有紧前活动全部完成）| 紧前活动的\(EF\)最大值 |
| 最早完成时间 | \(EF\) | 活动最早能完成的时间 | \(EF = ES + t\) |
| 最迟完成时间 | \(LF\) | 活动最迟必须完成的时间（不延误项目总工期）| 紧后活动的\(LS\)最小值 |
| 最迟开始时间 | \(LS\) | 活动最迟必须开始的时间 | \(LS = LF - t\) |
| 总时差 | \(TF\) | 活动的最大可延迟时间（延迟不影响项目总工期）| \(TF = LS - ES = LF - EF\) |
3. 关键路径判定规则
- 关键活动：总时差\(TF=0\)的活动（无任何缓冲时间，延迟1天则项目总工期延迟1天）；
- 关键路径：由所有关键活动按依赖关系组成的路径，是项目的最长路径（路径总持续时间=项目最短完成工期）；
- 项目可存在多条关键路径，所有关键路径的总持续时间相同，均需重点管控。
4. 辅助概念
- 紧前活动：某活动开始前必须完成的前置活动；
- 紧后活动：某活动完成后才能开始的后续活动；
- 虚活动：仅表示依赖关系，持续时间为0的活动（用于处理复杂依赖，如多紧前/紧后）。
二、CPM手动计算步骤（核心：正推+逆推）
手动计算是理解CPM的基础，适用于中小型项目（活动数<20），步骤为定义活动清单→正推法算\(ES/EF\)→逆推法算\(LF/LS\)→计算总时差→判定关键路径，结合经典示例一步一步落地。
例子
某项目拆解为6个活动，活动清单、持续时间、紧前活动如下：
| 活动代号 | 持续时间\(t\)（天） | 紧前活动 |
|----------|-------------------|----------|
| A | 3 | 无 |
| B | 2 | A |
| C | 4 | A |
| D | 3 | B |
| E | 2 | C |
| F | 1 | D,E |
步骤1：正推法计算\(ES\)、\(EF\)（从项目起点→终点，顺向计算）
核心规则：
1. 无紧前活动的起始活动，\(ES=0\)（默认项目从第0天开始）；
2. 非起始活动的\(ES = \max(\text{所有紧前活动的}EF)\)（必须等最晚完成的紧前活动结束）；
3. 所有活动的\(EF = ES + 本活动持续时间t\)。
计算过程：
| 活动 | \(t\) | 紧前活动 | \(ES\) | \(EF=ES+t\) |
|------|-----|----------|------------|-----------|
| A | 3 | 无 | 0 | 3 |
| B | 2 | A | 3 | 5 |
| C | 4 | A | 3 | 7 |
| D | 3 | B | 5 | 8 |
| E | 2 | C | 7 | 9 |
| F | 1 | D,E | max(8,9) =9|10 |
关键结论：项目最短完成工期 = 最终活动的\(EF\) = 10天。
步骤2：逆推法计算\(LF\)、\(LS\)（从项目终点→起点，逆向计算）
核心规则：
1. 无紧后活动的结束活动，\(LF=\)项目最短完成工期；
2. 非结束活动的\(LF = \min(\text{所有紧后活动的}LS)\)（必须等最早开始的紧后活动开始）；
3. 所有活动的\(LS = LF - 本活动持续时间t\)。
计算过程：
| 活动 | \(t\) | 紧后活动 | \(LF\) | \(LS=LF-t\) |
|------|-----|----------|------------|-----------|
| F | 1 | 无 | 10 | 9 |
| E | 2 | F | 9 | 7 |
| D | 3 | F | 9 | 6 |
| C | 4 | E | 7 | 3 |
| B | 2 | D | 6 | 4 |
| A | 3 | B,C | min(4,3)=3|0 |
步骤3：计算总时差\(TF\)，判定关键路径
计算每个活动的总时差\(TF = LS - ES\)，若\(TF=0\)则为关键活动，所有关键活动组成关键路径。
计算过程
| 活动 | \(ES\) | \(EF\) | \(LS\) | \(LF\) | \(TF=LS-ES\) | 关键活动 |
|------|------|------|------|------|-------------|----------|
| A | 0 | 3 | 0 | 3 | 0 | 是 |
| B | 3 | 5 | 4 | 6 | 1 | 否 |
| C | 3 | 7 | 3 | 7 | 0 | 是 |
| D | 5 | 8 | 6 | 9 | 1 | 否 |
| E | 7 | 9 | 7 | 9 | 0 | 是 |
| F | 9 | 10 | 9 | 10 | 0 | 是 |
关键路径：A → C → E → F，总持续时间=10天。
步骤4：项目管控结论
1. 关键活动A、C、E、F无缓冲时间，需重点管控，确保按计划完成；
2. 非关键活动B、D各有1天总时差，可延迟1天（或调配资源至关键活动），不影响总工期；
3. 若需缩短项目总工期，只能压缩关键路径上活动的持续时间（压缩非关键活动无意义）。
代码如下：
function result = cpm_calculation(activities, durations, predecessors)
% 关键路径法计算函数
% 输入：
% activities: 活动代号数组，cell类型，如{'A','B','C'}
% durations: 活动持续时间数组，数值型，如[3,2,4]
% predecessors: 紧前活动索引数组，每行对应一个活动的紧前活动索引（索引从1开始，空为[]），如[[],[1],[1],[2],[3],[4,5]]
% 输出：
% result: 结构体，包含所有时间参数、总工期、关键活动、关键路径
n = length(activities);
if length(durations) ~= n || length(predecessors) ~= n
error('输入参数长度不匹配');
end
% 初始化
ES = zeros(1, n);
EF = zeros(1, n);
LS = inf(1, n);
LF = inf(1, n);
Slack = zeros(1, n);
% 构建后继列表
successors = cell(1, n);
for i = 1:n
for j = 1:n
if ismember(i, predecessors{j})
successors{i} = [successors{i}, j];
end
end
end
% 前向计算：最早开始和完成时间
% 先设置起点
start_indices = find(cellfun(@isempty, predecessors));
ES(start_indices) = 0;
EF(start_indices) = durations(start_indices);
changed = true;
while changed
changed = false;
for i = 1:n
if isempty(predecessors{i})
new_ES = 0;
else
pred_EF = EF(predecessors{i});
new_ES = max(pred_EF);
end
if new_ES > ES(i)
ES(i) = new_ES;
EF(i) = ES(i) + durations(i);
changed = true;
end
end
end
% 总工期
total_duration = max(EF);
% 后向计算：最晚开始和完成时间
% 先设置终点
end_indices = find(cellfun(@isempty, successors));
LF(end_indices) = total_duration;
LS(end_indices) = LF(end_indices) - durations(end_indices);
changed = true;
while changed
changed = false;
for i = 1:n
if isempty(successors{i})
new_LF = total_duration;
else
succ_LS = LS(successors{i});
new_LF = min(succ_LS);
end
if new_LF < LF(i)
LF(i) = new_LF;
LS(i) = LF(i) - durations(i);
changed = true;
end
end
end
% 计算松弛时间
Slack = LS - ES;
% 关键活动
critical_activities_indices = find(Slack == 0);
critical_activities = activities(critical_activities_indices);
% 关键路径：从起点到终点，连接关键活动
% 起点：没有紧前的活动
start_indices = find(cellfun(@isempty, predecessors));
% 终点：没有后继的活动
end_indices = find(cellfun(@isempty, successors));
% 找到关键路径：从关键起点开始，沿着关键后继
critical_path = {};
if ~isempty(critical_activities_indices)
% 找到关键起点
critical_starts = intersect(start_indices, critical_activities_indices);
if ~isempty(critical_starts)
current = critical_starts(1);
critical_path = {activities{current}};
visited = [current];
while true
% 找到当前的关键后继
nexts = successors{current};
next_critical = intersect(nexts, critical_activities_indices);
next_critical = setdiff(next_critical, visited);
if isempty(next_critical)
break;
end
current = next_critical(1);
critical_path = [critical_path, activities{current}];
visited = [visited, current];
end
end
end
% 构建结果结构体
result.ES = ES;
result.EF = EF;
result.LS = LS;
result.LF = LF;
result.Slack = Slack;
result.total_duration = total_duration;
result.critical_activities = critical_activities;
result.critical_path = critical_path;
end
结果如下：
# test_cpm.m
activities = {'A', 'B', 'C', 'D', 'E', 'F'};
durations = [3, 2, 4, 3, 2, 1];
predecessors = {[], [1], [1], [2], [3], [4, 5]};
result = cpm_calculation(activities, durations, predecessors);
disp('最早开始时间 (ES):');
disp(result.ES);
disp('最早完成时间 (EF):');
disp(result.EF);
disp('最晚开始时间 (LS):');
disp(result.LS);
disp('最晚完成时间 (LF):');
disp(result.LF);
disp('松弛时间 (Slack):');
disp(result.Slack);
disp('总工期:');
disp(result.total_duration);
disp('关键活动:');
disp(result.critical_activities);
disp('关键路径:');
disp(result.critical_path);
>> test_cpm
最早开始时间 (ES):
0 3 3 5 7 9
最早完成时间 (EF):
3 5 7 8 9 10
最晚开始时间 (LS):
0 4 3 6 7 9
最晚完成时间 (LF):
3 6 7 9 9 10
松弛时间 (Slack):
0 1 0 1 0 0
总工期:
10
关键活动:
{
[1,1] = A
[1,2] = C
[1,3] = E
[1,4] = F
}
关键路径:
{
[1,1] = A
[1,2] = C
[1,3] = E
[1,4] = F
}
