网络计划流程图运用MATLAB确定关键线路的方法

运用Floyd算法及MATLAB编程确定网络计划图关键线路的方法古雨鑫（西南科技大学 四川 绵阳 ）摘要：关键线路的确定对工程有着重要的意义，同时也是目前常用的一种工程项目进度控制的计划方法，本文通过运用Floyd算法，以及MATLAB编程对矩阵的处理能力，本文给出了两种确定关键线路的方法，可以简单方便的确定网络图中的关键线路。关键词：MATLAB，网络流程图，Floyd算法，关键线路1 基本理论1.1基本概念工程中一项工作从开始到完成需要的时间和资源，在网络图中一般用箭线表示，箭尾表示工作的开始，而箭头表示工作的结束，工作的代号（或名称）一般写在箭线的上方，工作的所需要消耗的时间（资源）一般写在箭线的下方，除此以外，还有不消耗资源和时间的虚工作（一般用虚线表示，只与工作有逻辑关系），紧接着前一项的工作称为紧前工作，紧接着后一项的工作称为紧后工作。节点指紧前工作和紧后工作的交点，并附有数码（工程中箭头的数码必须大于箭尾的数码）。关键线路指的是工程中从起始节点到最后节点的所要经过的最长线路。1.2 确定关键线路的意义 现代工程的特点是规模巨大，对时间，资源，资源都有严格的要求，而关键线路更是直接决定工程的总工期，对工程的控制起到了重要的作用，找出关键线路在工程中有着重要的实际意义，对工程的控制有着决定的影响。2 确定工程项目的MATLAB算法方法2.1采用Floyd算法对关键线路的确定 Floyd算法的基本思想是递推产生一个矩阵序列 其中矩阵 的第 行第 列元素表示是从顶点 到顶点 的路径上所经过的顶点序号不大于k的最短路径长度。 计算时用的迭代公式 K是迭代次数，。 最后，当k=n时，就是个顶点之间的最短路径。最后将最短路径的信息储存在path矩阵中。2.1.1将关键线路转换为最短线路的方法及MATLAB对算法的程序实现在此我们需要将最短线路转换成关键线路进行计算，步骤如下： 设网络图B，将网络图的结构不变，使 （其中 为转换后的新矩阵，为B的各边权的最大值），这样就将最短路径的计算转换成关键路径的计算。证明如下：设 中从起点到终点的链为 ，中的节点的标号为 ，链的总长度为 ： 其中 为G中的长度， 根据以上步骤和信息，编写MATLAB程序，可以实现网络图中任意两个节点关键线路的确定和工期的天数，基本步骤如下（附程序） 输入： a为根据网络图绘制的邻接矩阵 输出： Path为包含关键线路信息的矩阵MATLAB代码如下b=0;for i=1:n for j=1:n if a(i,j)=inf b=max(b,a(i,j); %求矩阵所有边的最大权 end endendfor i=1:n for j=1:n if a(i,j)=inf D(i,j)=(j-i)*b-a(i,j); %将关键路径转换成最短路径 end endend path=zeros(n);D(DD(i,k)+D(k,j) %算法中矩阵的迭代计算过程 D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end endendpath 这里以一副网络图为例：通过程序计算出的path矩阵我们可以通过path矩阵看出最短路线为线路为1-2-4-5-8-9-10。根据上述的转换原则，就有关键线路为1-2-4-5-8-9-10。2.3利用MATLAB对矩阵处理的能力找关键线路 MATLAB的强项主要是对矩阵的处理能力，这里看到用Floyd的算法计算关键线路时，要先将最短路径转换成关键路径，这里通过MATLAB编程直接计算关键线路的方法。这里我们通过编写程序记录最早开始时间和最迟开始时间，关键线路就是最早开始时间与最迟开始时间相等的线路。（附程序）输入：startnode：起始节点endnode：终止节点povertime：工作的持续时间输出：ET：最早开始时间FT:自由时间route：关键线路worktime：总工期LT：最迟开始时间程序如下：a=sparse(startnode,endnode,povertime);n=length(a);ET=zeros(1,n);LT=zeros(1,n)+inf;for j=2:n omg=0; for i=1:j-1 if a(i,j)0 omg=omg,a(i,j)+ET(i); end endET(j)=max(omg); %记录每个工作的最早开始时间 endLT(n)=ET(length(ET);for i=n-1:-1:1 b=inf; for j=n:-1:i+1 if a(i,j)0 b=b ,LT(j)-a(i,j); end end LT(i)=min(b); %记录每个工作的最迟开始时间endroute=0;for i=1:n if ET(i)=LT(i) %关键线路上的最早开始时间等于最迟开始时间 route=route i; endendfor i=1:n FT(i)=LT(i)-ET(i);endroute=route(2:length(route);worktime=ET(n); %总工期ETLTrouteFTworktime这里以上述的网络图为例：输入：startnode =1 2 2 2 3 4 5 6 7 8 9;endnode =2 3 4 6 5 5 8 7 9 9 10;povertime = 3 2 6 5 3 2 4 7 4 5 7 ;通过程序计算得出：ET =0 3 5 9 11 8 15 15 20 27route =1 2 4 5 8 9 10FT = 0 0 3 0 0 1 1 0 0 0worktime =27LT =0 3 8 9 11 9 16 15 20 27我们可以看出关键线路为1-2-4-5-8-9-10,同时我们还得出了程序对应的每个节点的的最早开始时间为0-3-5-9-11-8-15-15-20-17，对应每个节点的最迟开始时间为0-3-8-9-11-9-16-15-20-27，对应每个节点的自由时间为0-0-3-0-0-1-1-0-0-0，总工期为27天。结论总结：两种寻找关键线路的方法都可以简单准确的找出关键线路，对于大规模较为复杂的网络图，两种方法都有一定的优势，而第二种方法避免了Floyd的算法的将最短线路转换成关键线路的步骤，同时第二种方法更直接的得出关键线路的路线，Floyd的算法计算出的path矩阵还需要从矩阵找出关键线路。参考文献1司守奎，孙兆亮.数学建模算法与应用（第二版），国防工业出版社，2015.4。2李珠，苏有文.土木工程施工