关键路径（要径法）

关键路径

要径法

关键路径法(CriticalPathMethod，CPM)，又称为要径法，是计划项目活动中用到的一种算术方法。

关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间(例如在关键路径上没有浮动时间)。但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。

定义

历史

推导过程

应用

影响及意义

介绍

关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间(例如在关键路径上没有浮动时间)。但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。

一个项目可以有多个、并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。

最初，关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。

关键路径方法是由杜邦公司发明的。

探寻

AOE网

用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE(ActivityOnEdgeNetwork)网。在建筑学中也

称为关键路线。AOE网常用于估算工程完成时间。例如:图1是一个网。其中有9个事件v1，v2，…v9;11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v1表示整个工程开始，v9表示整个工程结束。V5表示，活动a2和a3已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6个时间单位可以完成。

AOE网性质

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。

只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。

可以采取如下步骤求得关键活动:

A、从开始顶点v1出发，令ve(1)=0，按拓扑有序序列求其余各顶点的可能最早发生时间。Ve(k)=max{ve(j)+dut(<j,k>)}(1.1)j∈T其中T是以顶点vk为尾的所有弧的头顶点的集合(2≤k≤n)。

如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。

B、从完成顶点vn出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间:

vl(j)=min{vl(k)-dut(<j,k>)}k∈S其中S是以顶点vj是头的所有弧的尾顶点集合(1≤j≤n-1)。

C、求每一项活动ai(1≤i≤m)的最早开始时间e(i)=ve(j);最晚开始时间:

l(i)=vl(k)-dut(<j,k>)若某条弧满足e(i)=l(i)，则它是关键活动。

对于图1所示的AOE网，按以上步骤的计算结果见表1，可得到a1,a4,a7,a8,a10,a11是关键活动。

关键路径

这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如图7.21的AOE网中有二条关键路径，(v1,v2,v5,v7,v9)和(v1,v2,v5,v8,v9)它们的路径长度都是24。如图2所示:

研究的问题

(1)完成整个工程至少需要多少时间;

(2)哪些活动是影响工程的关键。

1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。

关键路径术语

(1)关键路径:从源点到汇点的路径长度最长的路径叫关键路径。

(2)活动开始的最早时间e(i)

(3)活动开始的最晚时间l(i)定义e(i)=l(i)的活动叫关键活动。

(4)事件开始的最早时间ve(i)

(5)事件开始的最晚时间vl(i)

设活动ai由弧<j,k>;(即从顶点j到k)表示，其持续时间记为dut(<j,k>;)，则

e(i)=ve(j)

l(i)=vl(k)-dut(<j,k>)(6_6_1)

求ve(i)和vl(j)分两步:

从ve(1)=0开始向前递推

ve(j)=Max{ve(i)+dut(<i,j>)}(6_6_2)

<i,j>T,2<=j<=n

其中，T是所有以j为弧头的弧的集合。

从vl(n)=ve(n)开始向后递推

vl(i)=Min{vl(j)-dut(<i,j>)}(6_6_3)

<i,j>S,1<=i<=n-1

其中，S是所有以i为弧尾的弧的集合。

两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。

4、求关键路径的算法

(1)输入e条弧<j,k>;，建立AOE网的存储结构。

(2)从源点v1出发，令ve(1)=0，求ve(j)2<=j<=n。

(3)从汇点vn出发，令vl(n)=ve(n)，求vl(i)1<=i<=n-1。

(4)根据各顶点的ve和vl值，求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。

StatusToplogicalSort(ALGraphG,stack&T){

FindInDegree(G,indegree);

InitStack(S);count=0;ve[0..G.vexnum-1]=0;

while(!StackEmpty(S))

{Pop(S,j);Push(T,j);++count;

for(p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p>adjvex;

if(--indegree[k]==0)Push(S,k);

if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);

}

}

if(count<G.vexnum)returnERROR;

elsereturnOK;

}

statusCriticalPath(ALGraphG){

if(!ToplogicalOrder(G,T))returnERROR;

vl[0..G.vexnum-1]=ve[G.vexnum-1];

while(!StackEmpty(T))

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p->adjvex;dut=*(p->info);

if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;

}

for(j=0;j<G.vexnum;++j)

for(p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p>adjvex;dut=*(p->info);

ee=ve[j];el=vl[k];

tag=(ee==el)?'*':'';

printf(j,kdut,ee,el,tag);

}

}

算法分析

C++完整代码

#include<iostream>

#include<cstdio>

#include<string.h>

usingnamespacestd;

intn,m,w[1001][1001],prev[1001],queue[1001],Time[1001],l=0,r=0,Pos[1001],path[1001];

voidinit()

{

inti,a,b,c;

scanf("%d%d",&n,&m);

for(i=1;i<=m;i++)

{

scanf("%d%d%d",&a,&b,&c);

w[a][b]=c;

prev[b]++;

}

}

inlinevoidNewq(intv)

{

r++;

queue[r]=v;

}

inlinevoidDel(intv)

{

inti;

for(i=1;i<=n;i++)

if(w[v][i])

{

prev[i]--;

if(!prev[i])

Newq(i);

}

}

voidtopo()

{

for(inti=1;i<=n;i++)

if(!prev[i])

Newq(i);

while(r<n)

{

l++;

Del(queue[l]);

}

}

voidcrucialpath()

{

inti,j;

memset(Time,0,sizeof(Time));

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if((w[j][queue[i]])&&(Time[j]+w[j][queue[i]]>Time[queue[i]]))

{

Time[queue[i]]=Time[j]+w[j][queue[i]];

Pos[queue[i]]=j;

}

}

voidprint()

{

printf("%d",Time[n]);

inti=n,k=0;

while(i!=1)

{

k++;

path[k]=i;

}

for(i=k;i>1;i--)

printf("%d",path[i]);

printf("%d",path[1]);

}

intmain()

{

init();

topo();

crucialpath();

print();

return0;

}

参考资料

1.关键路径法·中国知网