可行性分析与项目评价教学课件关键路径法(CPM).ppt

关键路径法（CPM）
CPM（Critical Path Method）的基本思想：用网络图表示一个系统或一个工程的计划，分析各个工序或过程在网络中的地位，通过计算找出网络中的关键工序和关键路径。
一个网络中，完成各道工序需时最长的路线，13页，共39页。
节点的最迟时间
节点的最迟时间是指结点 i 最迟必须完成（结束）的时间，否则将影响它的后续作业的按时开工。
规定结束点：tL(n) = 任务的总工期；
或者：tL(n) = tE(n) ；
其它节点：
j1
i
t (i, j1)
j2
t (i ,j2)
t (i, jk)
jk
tL(i)
tL(j)
第14页，共39页。
节点的时差
节点的时差为结点的最迟时间减去最早时间。
对任意节点有：
第15页，共39页。
作业的最早开始时间
作业的最早开始时间表示该作业最早什么时候可以开始，显然必须等到它的先行作业完工之后才能开始。
作业的最早开始时间等于起始节点的最早时间，即：
第16页，共39页。
作业的最早完成时间
最早完成时间等于最早开始时间加上作业时间，即：
第17页，共39页。
作业的最迟完成时间
作业最迟完成时间等于终止节点的最迟时间，否则就会耽误下面的作业。所以有：
第18页，共39页。
作业的最迟开始时间
作业的最迟开始时间等于最迟结束时间减去作业时间，即：
第19页，共39页。
作业的总时差
任一作业(i , j )，如果在 tES (i , j)开始，耗费 t (i , j) ，则它一定能在 tEF (i , j)时完成；但作业(i, j )又有一个 tLF(i , j)，它只要不超过 tLF(i , j)而完工，就不会拖延总工期，所以作业 (i , j)的安排具有一定的回旋余地，我们将此称为作业的总时差：R(i,j)。
由定义我们可知作业的总时差可以由下两式中的任一个计算：
第20页，共39页。
总时差的示意图
i
j
作业 A
k
作业 B
tES tLS A tEF tLF
tES tLS B tEF tLF
R(A)
R(B)
A
B
第21页，共39页。
总时差的含义
当 R (i , j) = 0 时，称此作业 (i , j) 为“关键作业”。
当 R (i , j)  0 时，作业 (i , j) 可作如下两种机动，即其“时差调用”有两种方式：
可以适当推迟其开工时间（只要不超过其最迟开工时间）；
可以适当放慢进度，延长其作业时间，只要延长的时间不超过R(i , j)。
可见，R (i , j) 的大小表明作业 (i , j) 具有的潜力，调用时差就是挖掘该作业具有的潜力，即人力、物力和时间的潜力。
设时差调用量为δ(i , j) ，则调用原则为：δ(i , j)≤ R (i , j) 。
第22页，共39页。
作业的单时差
在调用时差时，只要满足δ (i , j) ≤ R (i , j) ，整个任务的总工期就不会拖延，但对后续作业 (j , k) 来说，会出现以下两种情况：
受到干扰，无法在 tES(j ,k) 开始下面的工序；
不受干扰，可以在tES(j ,k)开始下面的工序。
因此，可定义 r (i , j)为在不影响后续作业的最早开始时间的前提下，本作业 (i , j) 可以自由利用的机动时间范围。即：
第23页，共39页。
单时差和总时差示意图
i
j
作业 A
k
作业 B
tES tLS A tEF tLF
tES tLS B tEF tLF
R(A)
r(A)
第24页，共39页。
关键路线及其含义
关键结点（事项）——网络图中，时差为零的结点（事项）
关键作业 ——网络图中，总时差为零的作业；
关键路线 ——网络图中，从起点到终点，由关键作业连成的通路称为关键路线。关键路线上的工序都是关键工序。
网络分析的根本任务之一就是找出关键路线(CP)，华罗庚先生称它为主要矛盾线；二是找出非关键路线各工序的时差；三是利用“向关键路线要时间，向非关键路线要资源”的指导思想，做出最优或满意的工程计划。
第25页，共39页。
寻找关键路线
定理1：在CP上，全部结点的时差为零，反之不真。
这个定理给出了关键路线的必要条件，但是不充分。这个定理只是提供确定CP