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

运用Floyd算法及MATLAB编程确定网络计划图关键线路的 古雨鑫 （西南科技大学四川绵阳 621000） 摘要：关键线路的确定对工程有着重要的意义，同时也是目前常用的一种工程项目进度控制的计划方法，本文通过运用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 end end for i=1:n for j=1:n if a(i,j)~=inf D(i,j)=(j-i)*b-a(i,j);%将关键路径转换成最短路径 end end end path=zeros(n); D(D<0 )=inf; for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end end end D for k=1:n for j=1:n for i=1:n if D(i,j)>D(i,k)+D(k,j) %算法中矩阵的迭代计算过程 D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end end end path 这里以一副网络图为例： 通过程序计算出的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 end ET(j)=max(omg);%记录每个工作的最早开始时间 end LT(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);%记录每个工作的最迟开始时间 end route=0; for i=1:n if ET(i)==LT(i)%关键线路上的最早开始时间等于最迟开始时间 route=[route i]; end end for i=1:n FT(i)=LT(i)-ET(i); end route=route(2:length(route)); worktime=ET(n);    %总工期 ET LT route FT worktime 这里以上述的网络图为例： 输入： 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    27 route = 1    2    4    5    8    9    10 FT = 0    0    3    0    0    1    1    0    0    0 worktime =27 LT = 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]李珠，苏有文.土木工程（第二版），武汉理工大学出版社，2013.1. [3]杨鹏，罗一新.流程网络图主关键路径确定的 MATLAB 方法[J].与决策，2007，26(3)：61-63. [4]徐永琳，刘露.网络计划技术节点参数和关键路径的MATLAB实现及优化.工业仪表与自动化装置.2013 年第4 期.