关键路径方法有两个起源：PERT方法（程序评估和审查技术），由美国海军于1957年开发，用于控制组成太空项目的各种活动的执行时间，由于需要在可用的时间间隔内完成每个任务。它最初由Polaris项目时间控件使用，目前在整个太空程序中使用。 CPM方法（关键路径法）是当前方法的第二种起源，也是由美国杜邦公司和雷明顿兰德公司的运营研究中心于1957年在美国开发的，通过适当计划项目的组成活动，寻求对运营成本的控制和优化。
两种方法都提供了必要的管理要素，以
控制执行时间和运营成本来形成当前的关键路径方法，以寻求在最短的时间内以最低的成本执行整个项目。
- 应用领域
由于该方法具有很大的灵活性和对任何大型或小型项目的适应性，因此它的作用范围非常广泛。为了获得最佳结果，应将其应用于具有以下特征的项目：
- 该项目在某些部分或全部方面是唯一的，非重复的；必须在最短时间内执行所有或部分项目，且不得在关键时间内进行任何变更。在可用时间内尽可能低的操作。
在应用范围内，该方法已用于各种活动的计划和控制，例如水坝建设，道路开通，铺路，房屋和建筑物的建造，船舶的修理，市场研究，沉降运动，区域经济研究，审计，大学职业规划，手术室时间分配，工厂扩建，收款路线计划，销售计划，人口普查等。
- 利用PERT-CPM进行项目计划和控制
大型项目的良好管理需要仔细计划，计划和协调许多相互关联的活动。在1950年代初期，开发了基于使用网络和联网技术的正式程序来协助完成这些任务。最出色的程序包括PERT（程序评估和审查技术）和CPM（关键路径方法）。尽管PERT类型的系统最初用于评估研究和开发项目的进度，但它们也用于监视其他特殊类型的项目的进度。例子包括施工程序，计算机程序，准备提案和预算，在计划维护和安装计算机系统时，这种技术甚至已应用于电影制作，政治活动和复杂的外科手术中。
类似于PERT的系统的目标是帮助计划和控制，因此它不需要太多直接的优化。有时，主要目的是确定满足特定交货日期的可能性。它还指出了那些更有可能成为瓶颈的活动，并指出了这一点，因此应尽最大努力避免延误。第三个目标是评估计划变更的效果。例如，可以将资源分配可能发生的变化的评估从不太紧要的活动评估为具有瓶颈的活动。另一个重要的应用是评估偏离进度的影响。
所有PERT类型的系统都使用项目网络以图形方式可视化其元素之间的相互关系。项目计划的这种表示方式显示了所有原始关系，涉及活动执行的顺序。在图1中，这些特性显示了用于房屋建造的初始项目网络。该网络表明，应在铺设基础之前进行开挖，然后在铺设墙壁之前先完成基础。墙装好后，可以并行执行三个活动。通过跟踪网络，您可以看到后续任务的顺序。
用PERT术语来说，网络的每个弧线代表一个活动，即项目所需的任务之一，每个节点代表一个事件，通常在到达所有活动的最后一刻就定义一个事件。箭头指示每个事件应发生的顺序。而且，事件必须在到达该节点的活动开始之前进行。箭头指示每个事件应发生的顺序。此外，事件必须在该节点发出的活动开始之前进行。 （实际上，项目的连续阶段通常可以重叠，因此网络可以代表项目计划的理想近似值。）
指向所有活动的节点是对应于其构思完成的事件，或者，如果项目已经开始，则表示完成计划。在后一种情况下，网络中没有到达弧的每个节点表示继续进行中的活动或开始随时可以开始的新活动的事件。
每个拱门都扮演着双重角色，即代表一个活动，并帮助代表不同活动之间的起源关系。有时即使没有实际活动可表示，也需要一条弧线来定义出处关系。在这种情况下，引入了一个虚拟活动，该活动需要零时间，其中表示该虚拟活动的弧线显示为表示该出处关系的虚线箭头。例如，考虑在图1中表示虚拟活动的弧5®8。该弧的唯一目的是指示必须在开始外部施工之前完成管道铺设。
建立这种类型的网络的通用规则是两个节点不能通过多个弧直接连接。当您同时进行两个或多个活动时，虚拟活动也可以用来避免违反此规则。这在图1中以拱形11®进行了说明。该拱形的唯一目的是指示地板安装应在安装内部装饰之前完成，而从节点9到节点12没有两个拱形。
一旦开发了项目网络，下一步就是估计每个活动所需的时间。图1中房屋建筑示例的这些估算值如图2所示，其中最暗的数字（以工作日为单位）出现在弧线旁边。这些时间用于计算每个事件的两个基本量，即最近的时间和最远的时间。
事件的最接近时间是（紧随其后的）活动尽快开始的（估计）时间。
最接近的时间是通过从网络开始经过正向传递而获得的，从初始事件开始并按时间向前进行，直到最终事件为止，对于每个事件，都将计算每个事件发生的时间。第一，如果每个立即进行的事件都最早发生，并且每个干预活动都消耗了其估计的时间。项目的启动必须标有时间0。此过程如表1所示。对于图1和2所考虑的示例，获得的最接近时间记录在图2中，其中第一个记录在表2中。每个节点给出的两个数字。
事件的最早时间是指事件发生的最后（估计）时间，而不会延迟项目的完成时间。
表1.以房屋建造为例计算最近的时间。
| 事件 | 即时事件
以前 |
时间时间
更多+的 下一个活动 |
天气
=最大加 下一个 |
| 之一 | ___ | ___ | 0 |
| 二 | 之一 | 0 + 2 | 二 |
| 3 | 二 | 2 + 4 | 6 |
| 4 | 3 | 6 + 10 | 16 |
| 5 | 4 | 16 + 4 | 二十 |
| 6 | 4 | 16 + 6 | 22 |
| 7 | 4 | 16 + 7 | 25 |
| 5 | 20 + 5 | ||
| 8 | 5 | 20 + 0 | 29 |
| 6 | 22 + 7 | ||
| 9 | 7 | 25 + 8 | 33 |
| 10 | 8 | 29 + 9 | 38 |
| 十一 | 9 | 33 + 4 | 37 |
| 12 | 9 | 33 + 5 | 38 |
| 十一 | 37 + 0 | ||
| 13 | 10 | 38 + 2 | 44 |
在这种情况下，可以通过回传网络从事件的最远时间开始，从最后的事件开始，然后在时间上倒退到最初的事件。对于每个事件，他计算了事件发生的最终时间，这样，如果所涉及的每个活动恰好消耗了其估计的时间，则随后的事件将在其最远的时间发生。表2说明了此过程，其中44天是房屋建设项目完成的最近时间，也是最远的时间。完成房屋建设项目的最遥远时间。在图2中还找到了获得的最远距离，作为为每个节点指定的第二个数字。
假设活动（i，j）是项目网络中从事件i到事件j的活动。
事件的松弛时间是其最早时间与最近时间之间的差。
活动（i，j）的懈怠是和之间的差。
因此，如果假定其他所有内容都按时运行，则事件的延迟表示在不延迟项目完成的情况下可以承受多少延迟而没有延迟项目的完成，而活动的延迟则表示延迟时间相同。该活动的终止。表3显示了房屋建设项目的这些许可的计算。
项目的关键路径是活动零松弛的路径。（所有闲置零的活动和事件都必须在关键路径上，但不能在其他路径上。）
表2.建造房屋示例的最长时间计算
|
事件 |
即时事件
以前 |
时间时间
更多- 遥远的活动 |
天气
=最小加 下一个 |
| 13 | __ | ___ | 44 |
| 12 | 13 | 44-6 | 38 |
| 十一 | 12 | 38-0 | 38 |
| 10 | 13 | 44-2 | 42 |
| 9 | 12 | 38-5 | 33 |
| 十一 | 38-4 | ||
| 8 | 10 | 42-9 | 33 |
| 7 | 9 | 33-8 | 25 |
| 6 | 8 | 33-7 | 26 |
| 5 | 8 | 33-0 | 二十 |
| 7 | 25-5 | ||
| 4 | 7 | 25-7 | 16 |
| 6 | 26-6 | ||
| 5 | 20-4 | ||
| 3 | 4 | 16-10 | 6 |
| 二 | 3 | 6-4 | 二 |
| 之一 | 二 | 2-2 | 0 |
表3.房屋建筑示例的电气间隙计算。
| 事件 | 清仓 | 行使 | 清仓 | |||
| 之一
二 3 4 5 6 7 8 9 10 十一 12 13 |
0-0 = 0
2-2 = 0 6-6 = 0 16-16 = 0 20-20 = 0 26-22 = 4 25-25 = 0 33-29 = 4 33-33 = 0 42-38 = 4 38-37 = 1 38-38 = 0 44-44 = 0 |
（1,2）
（2.3） （3,4） （4.5） （4.6） （4.7） （5.7） （6.8） （7.9） （8.10） （9.11） （9.12） （10.13） （12.13） |
2-（0 + 2）= 0
6-（2 + 4）= 0 16-（6 + 10）= 0 20-（16 + 4）= 0 26-（16 + 6）= 4 25-（16 + 7）= 2 25-（20 + 5）= 0 33-（22 + 7）= 4 33-（25 + 8）= 0 42-（29 + 9）= 4 38-（33 + 4）= 1 38-（33 + 5）= 0 44-（38 + 2）= 4 44-（38 + 6）= 0 |
如果在表3中验证了松弛度为零的活动，则可以看到房屋的构造示例具有一条关键路径：1®2®3®4®5®6®7®9®12®13，如图2所示，带有较深的箭头。关键活动的这种顺序必须严格按时进行，以免延误项目完成。其他项目可能有一条以上的关键路径。例如，请注意，如果将活动的估计时间（4,6）从6更改为19，将会在图2中发生什么。
有趣的是，在表3中观察到，尽管关键路径上的所有事件（包括4和7）必须具有零余量，但活动（4、7）却并非如此，因为活动的估计时间少于活动（4，5）和（5，7）的估计时间总和。因此，后面这些活动处于关键路径上，而活动（4，7）不在关键路径上。
有关最近和最远时间，许可和关键路径的信息对于项目经理而言是无价的。除其他事项外，它使您可以调查可能的计划改进的效果，以确定应在哪里进行特别的工作以保持并评估延迟的影响。
PERT
图PERT 图是未测网络的原始图，其中包含从事件i开始到事件j结束的箭头所表示的活动数据。
在箭头的上部，显示了标识号，通常是事件编号（ij）。活动的标准持续时间（t）出现在底部的矩形内。在事件的上半部分，记录了进度编号，在左下角记录了该项目的最后一个读数，在右下角记录了该项目的第一个读数。
该图的优点是可以通知每个活动的最早和最晚开始日期和结束日期，而不必诉诸松弛矩阵。
让我们看看如何通过PERT图表显示工厂扩展。
- 活动网络
活动显示事件，顺序，相互关系和关键路径的图形表示称为网络。该方法不仅被称为关键路径，而且从项目开始到完成都被算作一系列活动，这些活动的执行时间没有灵活性，因此，该系列中任何活动遭受的任何拖延都会导致整个项目的延误。
从另一个角度来看，关键路径是指示项目总持续时间的一系列活动。每个活动都由一个箭头表示，该箭头从一个事件开始，到另一个事件结束。
一个事件称为活动开始或终止的时刻。它是在最早或最晚开始或终止之间的可变时间内确定的。
这些事件也可以通过节点的名称来了解。
事件事件
j
初始事件称为i，最终事件称为j。活动的结束事件将是下一个活动的开始事件。
箭头不是矢量，标量，也不表示任何度量。箭头的形状无关紧要，因为将根据网络显示的需要和方便性来绘制箭头。它们可以是水平，垂直，上升，下降，弯曲，笔直，折断等。
如果需要表明某项活动与另一项活动具有相互关系或延续性，则将在两者之间画一条虚线，称为联赛，其持续时间为零。
联盟有时可以代表等待时间，以便能够开始下一个活动
多个活动可以在一个事件中结束或从同一事件开始。
（a）不正确，（b）正确。
建立网络时，应避免以下情况：
- 从同一事件开始并到达同一事件的两个活动。这会造成时间和连续性的混乱。起始事件或结束事件必须在两个事件中打开并与联赛链接。
- 从另一个活动的中间部分拆分一个活动。每个活动都必须始终始于一个事件，然后结束于另一个事件。发生这种情况时，基础活动或初始活动将基于百分比划分为事件，而次级活动则是从中得出的。
（a）不正确；（b）正确。
- 在完成网络时，不要使事件松动。它们都必须与初始事件或最终事件相关。
（a）不正确；（b）正确
- PERT三种估算方法。
到现在为止，已经隐含地假定可以以合理的准确性来获得每个项目活动所需时间的估算。实际上，这些时间将是很多不确定性。实际上，它是具有一定概率分布的随机变量。PERT的原始版本通过使用三种不同类型的活动时间估算来考虑这种不确定性，以便获得有关其概率分布的基本信息。所有活动时间的此信息用于估计在预定日期完成项目的可能性。
PERT对每个活动使用的三个估计是最可能的估计，乐观估计和悲观估计。最可能的估算值（用m表示）试图成为一项活动所花费时间的最现实的估算值。用统计术语来说，它是对活动时间的概率分布的模式（最高点）的估计。如果一切顺利，乐观的估计（用a表示）将是不可能的但可能的时间。它实质上是对概率分布下限的估计。最后，如果一切都出错了，悲观的估计（用b表示）被认为是不太可能但可能的时间。用统计的话它本质上是对概率分布上限的估计。图3显示了这三个估计相对于概率分布的理想位置。
经过的时间
图3.在三个PERT估计中，活动时间的概率分布模型：m =可能估计，a =乐观估计，b =悲观估计。
进行了两个假设，将m，a和b转换为活动所需时间的期望值（t e）和方差（s 2）的估计值。一种假设是，标准偏差（方差的平方根）s等于合理可能的时间要求范围的六分之一；这是，
是期望的方差估计。进行此假设的基本原理是，许多概率分布的尾部（如正态分布）被视为与均值有大约3个标准差，因此，例如，构建尾部，例如通常用于统计质量控制的控制图，以使控制极限之间的偏差估计为六个标准偏差。
获得期望值（t e），也有必要对概率分布的形状进行假设，该分布假定为（至少近似为）β分布。这种分布形式具有图3所示的形式，对于此目的而言是合理的。
使用图3所示的模型，活动时间的预期值大约为
请注意，间隔（a + b）/ 2的中间位于a和b之间，因此t e是模式的加权算术平均值，并且是间隔的一半，模式的权重为三分之二。尽管β分布的假设是任意的，但其目的是以看起来合理的方式确定期望值am，a和b。
在为每个活动计算期望值和估计方差之后，还需要三个附加假设（或近似值）来计算按时完成项目的概率。一是活动时间在统计上是独立的。第二点是，关键路线（就预期时间而言）总是比任何其他路线都需要更长的总时间。这意味着期望值和方差很容易找到该正常随机变量（项目时间）小于计划完成时间的概率。
- 在时间和成本之间进行权衡的CPM方法
CPM和PERT的原始版本在两个重要方面有所不同。首先，CPM假设活动时间是确定性的（也就是说，可以可靠地预测活动时间而没有明显的不确定性），因此它不需要刚才描述的三个估计。其次，CPM并没有将时间放在头等大事，而是将时间和成本同等重要，并通过为每个活动构建时间-成本曲线来突出显示时间和成本，如图所示。图4.此曲线表示为活动预算的直接成本与其持续时间之间的关系。
图4.活动的时间成本曲线（i，j）。
通常，该图基于两点：法线和密集或中断。正常点是指以正常方式进行活动时的成本和所需的时间，而不会产生额外的成本（加班费，专用设备或材料以节省时间等），以加快活动的进行。相反，折断点提供了以密集或折断方式进行活动时所需的时间和成本，也就是说，不考虑成本就完全加速了活动，以便尽可能减少其持续时间。能够。作为近似，然后假定时间和成本之间的所有中间折衷是可能的，并且它们位于连接这两点的线段上。 （请注意图4中的暗线段）。所以，项目人员唯一需要获得的估计是这两个项目的成本和时间。
CPM的基本目标是确定在每个活动中必须使用的时间和成本之间的权衡，才能满足以最小成本计划的项目完成时间。确定
时间和成本的最佳组合的一种方法是应用线性规划。为了发现这一点，有必要引入新的表示法，其部分总结在图4中。令
D ij =活动的正常时间（i，j）
CD ij =活动的正常（直接）成本（i，j ）
d ij =活动（i，j）的休息时间
Cd ij =（活动）（i，j）的休息时间
问题的决策变量是x ij，其中
x ij =活动的持续时间（i，j）
然后每个活动都有一个决策变量x ij，但是没有对应活动的i和j的值都没有。
为了将活动的直接成本（i，j）表示为X jj的（线性）函数，请表示通过活动（i，j）的法线和断点的直线的斜率
还将K ij定义为与该直线的直接成本轴的交点，如图2所示。 4，因此，
在活动的直接成本（I，J）= K IJ + S IJ X IJ，
因此
项目的总直接成本=
总和分布在所有活动（i，j）中。现在该问题可以用数学方式表述和表述。
问题：给定项目的T（最大）完成时间，请选择x jj以最大程度地减少项目的总直接成本。
线性规划公式。为了在问题的线性规划中考虑项目的完成时间，每个事件都需要一个变量。这个附加变量是
事件k的yk =最近（未知）时间，它是X ij的确定性函数。
每个yk是一个辅助变量，即引入变量的模型，因为它在公式化过程中很方便并且不代表决策。单纯形法将辅助变量与普通决策变量（x ij）相同。
要查看如何将yk引入公式中，请考虑图1中的事件7。根据定义，它的最接近时间为：
y 7 = max {y 4 + x 47，y 5 + x 57 }，
换句话说y 7是满足以下两个限制的最小数量：
y 4 + x 47 < y 7
y 5 + x 45 < y 7，
因此，这两个约束可以直接合并到线性规划公式中（将y 7传递到左侧以获得适当的形式之后）。更进一步，我们将在后面看到为什么用简单方法为完整模型获得的最优解将自动使y 7的值成为满足这些限制的最小数量，因此不再需要将y 7的定义纳入模型的限制。
在对所有事件使用这些限制的过程中，每个变量x ij将恰好出现在这种类型的限制中，
可以用适当的方式表示为
为了继续准备编写完整的线性编程模型，将其标记为
事件1 =项目开始
事件n =项目结束，
因此
= 0
=完成时间。。
还要注意，它是一个固定常数，可以从目标函数中消除，因此，使项目的总直接成本最小化等于最大化。因此，线性规划问题在于找到
最大化
拿着它：
对于所有活动（i，j）
从计算的角度来看，可以通过将所有替换为
整个模型，因此第一组功能约束（）被非负约束取代
为其余变量引入非负性限制也很方便：
尽管在设置y 1 = 0 时这些变量已经被强制为非负值，这是由于
限制和
此模型的最佳解决方案的一个有趣的特性是（在正常情况下）网络中的每个路径都是一条需要时间T的关键路径。原因是这种解决方案在满足约束条件的同时避免了额外费用导致缩短任何轨迹的时间。
这种表述的关键是通过约束将模型引入模型的方式，以便为各个事件提供最接近的时间（给定当前基本可行解中的值）。由于必须按顺序获得最接近的时间，所有这些仅是最终要获得正确值（对于的当前值）所必需的，从而加强了限制。但是，要获得正确的值，则每个（甚至）的值必须是满足所有限制的最小数量。现在将简要说明为什么（在正常情况下）此属性对于最佳解决方案有效。
考虑变量的解决方案，使得网络的每条路径都是关键的，并且需要一个时间T.的限制。但是，如果有些变大，则会产生连锁反应，其中有些必须变大才能仍然满足约束等，直到最终必须变大。并且违反了限制。避免出现这种情况的唯一方法是使某些活动（在事件i之后）的持续时间缩短一些，从而增加成本。从而，最佳解决方案将防止它们大于满足约束所需的大小。
如此处所述，该问题假定已为项目完成设置了特定的交付日期T（可能是合同规定的）。一些项目实际上没有截止日期，在这种情况下，不清楚在线性规划公式中为T赋什么值。在这种情况下，对T的决定（实际上是最优解决方案中的项目持续时间）实际上取决于哪个是总成本与项目总时间之间的最佳折衷。
做出此决定所需的基本信息是，当先前公式中的T值发生变化时，最小总直接成本将如何变化，如图5所示。当使用参数线性规划获得在整个时间间隔内，最优解是T的函数。有更多更有效的过程来获取此信息，这些问题可以利用问题的特殊结构。
当项目工期的重要影响（除了直接成本）基本上是无形的时，图5为经理的T值（及其对应的最佳解决方案）决策提供了有用的依据。现在，当这些其他的影响基本上是财务上的（间接成本）时，将图5的总直接成本曲线与最小总间接成本（监管，设施，利息，合同罚金）对t的曲线结合起来是适当的，如图6所示。这些曲线的总和将为不同的T值提供项目的最小总成本的曲线.T的最优值将是最小化此总成本曲线的曲线。
- 在PERT和CPM之间选择
在PERT三估计方法和CPM时间成本权衡方法之间进行选择主要取决于项目类型和管理目标。 PERT在处理活动时间以及有效控制项目进度很重要的不确定性时尤其适用。例如，大多数研发项目都属于此类。另一方面，当可以很好地预测活动时间时，CPM非常合适。
（可能基于经验）以及何时可以轻松调整这些时间（例如，如果更改旅长大小），以及何时计划项目时间和成本之间的适当组合很重要。后一种类型由许多建设和维护项目代表。
当前，当前版本的PERT和CPM之间的差异未如所描述的那样明显。PERT的许多版本允许对每个活动使用单个估计（最有可能），从而省略了概率调查。称为PERT / Cost的版本也以类似于CPM的方式考虑时间和成本的组合。
- PERT和CPM之间的差异
PERT和CPM之间的区别在于时间估算的方式。E1 PERT假定执行每个活动的时间是由概率分布描述的随机变量。另一方面，CPM推断活动的时间是确定的，并且可以通过更改使用的资源级别来更改。
PERT假设某项活动的时间分布是beta分布。任何活动的分布都由三个估算值定义：
- 最可能的时间估计，m，最乐观的时间估计，a；最悲观的时间估计； b。
下图显示了分布的形状。最可能的时间是在正常条件下完成活动所需的时间。乐观和悲观的时间可以衡量活动固有的不确定性，包括设备故障，劳动力可用性，材料延迟和其他因素。
通过定义的分布，可以使用逼近公式分别计算Z活性的活性时间的平均值（预期）和标准偏差。
项目的预期完成时间是关键路径上所有活动的预期时间之和。同样，假设活动的时间分布是独立的（实际上，这是一个非常有问题的假设），则项目差异是关键路径上活动的差异之和。这些属性将在后面进行演示。
在CPM中，仅需要时间估算。所有计算都是在已知正常运行时间的前提下进行的。随着项目的进展，这些估计值将用于监视和监视进度。如果项目中发生任何延迟，则将通过更改资源分配来使项目按计划恢复原状。
- 参考书目
- 弗雷德里克·希利尔（Frederick S.Hillier），杰拉尔德·J·利伯曼（Gerald J. 运筹学简介，第五版，编辑。墨西哥McGraw Hill，1993年。http：//www.gestiopolis.com
