AOE图中关键路径的MATLAB实现

AOE图中关键路径的MATLAB实现 AOE图中关键路径的MATLAB实现,科学技术, 刘 露 约1837字 摘 要:利用AOE图中关键路径的计算,通过MATLAB软件编程求出AOE图的关键路径,提出若要加快工程进度应该给予关注的工作。 关键词:AOE图 关键路径 MATLAB 1 引言 若在带权的有向图中,以顶点示事件,以有向边表示活动,边上的权值表示活动的开销(如活动持续的时间),则此带权有向图称为AOE网(Activity On Edge Network)。AOE网通常可以表示一项工程的工作流程。而AOE图中主关键路径是决定工程项目进度的主要指标,如果要加快工程的总进度,就必须加快位于关键路径上的工作进度。本文运用MATLAB软件编程,根据关键路径的特点和性质找出关键路径。 2 算法描述 运用计算AOE图的时间参数的矩阵表式法,算法如下(基于MATLAB语言): (1)根据工作节点,求解工程的网络矩阵(稀疏矩阵)a; (2); (3)while() (4) (5)while() (6)end 3 算法实现 function cpm(snode,enode,povertime) a=sparse(snode,enode,povertime); n=length(a); earliestST=zeros(1,n); latestET=zeros(1,n)+inf; for i=2:n new1=0; for j=1:i-1 if(a(j,i)>0) new1=[new1,a(j,i)+earliestST(j)]; end end earliestST(i)=max(new1); end latestET(n)=earliestST(length(earliestST)); for i=n-1:-1:1 new2=inf; for j=n:-1:i+1 if(a(i,j)>0) new2=[new2 latestET(j)-a(i,j)]; end end latestET(i)=min(new2); end route=0; for i=1:n if(earliestST(i)==latestET(i)) route=[route i]; end end for i=1:1:n freetime(i)=latestET(i)-earliestST(i); end route=route(2:length(route)); worktime=earliestST(n); earliestST route freetime worktime 说明:其中参数snode,enode,povertime为向量,向量snode为所有工作的开尾节点,向量enode为所有工作的头节点,向量povertime为对应工作所需时间。 4 工程实例 某公司的产前分析网络工程图的工序明细表如表(1),求出AOE网中关键路线及所需最短时间; 4.1根据规则,工序表的网络图如下图(2): 图(2) 工序表的网络图 4.2MATLAB算法实现: Snode=[1 1 1 2 3 3 4 5 5 5 6 6 7]; Enode=[2 3 4 5 4 5 6 6 7 8 7 8 8]; Povertime=[5 10 11 4 4 realmin 15 21 25 35 realmin 20 15]; cpm(Snode,Enode,Povertime) earliestST =0 5101410313551 latestET =0 6101610313651 freetime =0 1 0 2 0 0 1 0 route =1 3 5 6 8 worktime =51 结果显示:关键路径为?????,各个节点的最早开始时间分别为:0、5、10、14、10、31、35、51;各个节点的最迟开始时间分别为:0、6、10、16、10、31、36、51;各个节点的自由活动时间分别为:0 、1、0 、2、0、0、1、0;工作总时间为51;从而每项工作的自由活动时间可由上述参数直接计算出,如:工作A的最早开始时间为0,工作A的最迟开始时间为1,最迟开始时间为1,最迟完成时间为6,最大自由活动时间为1。 5 结论 本文求解关键路径的步骤可以归结为下:?根据所给信息,建立工程的AOE图;?求各项工作头节点向量(Snode)、尾节点向量(Enode)及消耗向量Povertime(虚工作的消耗为realmin)(头结点标号要小于尾节点标号);?调用算法求解。 参考文献: 1.朱弘毅.网络技术[M].上海:复旦大学出版社,1999. 2.刁在筠,刘桂真等.运筹学[M].北京:高等教育出版社,2009. 3.刘振鹏,张小莉等.数据结构[M].北京:中国铁道出版社,2008.