关键路径.doc

关键路径一、相关概念 1、 PT图: 结点表示工序, 若工序 i 完成后工序 j 才能启动, 则图中有一条有向边(i,j) ,其长度表示工序 i 所需时间。 2、 PERT 图:有向边表示工序,其长度表示权值,若 e(i) 完成后 e(j) 才能开始, 则 e(i) 的终点是 e(j) 的起点。 3 、对于同一工序而言: PERT 图的边与结点数更少; PERT 图的边数约等于 PT 图的结点数; PT 图的使用更灵活,能适应某些额外约束。 4 、设 G 不存在有向回路,则可将 G 的结点重新编号为 v1',v2',...,vn' ,使得对于任意的边(vi',vj') ,有 i<j 。二、实际意义工序流程:工序中的各步骤最早可以启动时间以及允许最晚启动时间。三、算法及步骤基于 PT 图,时间复杂度为 O(M) 。 step1 :对结点重新编号(假设已完成)。 step2 :工序 1' 的最早启动时间 earliest(1')=0 。 step3 :对 j'从 2'到 N', earliest(j')=max{earliest(i')+C(i',j')} ,其中 i'是 j' 的直接前趋。 step4 :工序 N' 的最晚启动时间 latest(N')=earliest(N') 。 step5 :对 j'从(N-1)' 到 1', latest(j')=min{latest(i')-C(j',i')} ,其中 i'是 j' 的直接后继。需调用《图论的 MATLAB 程序》系列中的函数: (1) 正向表[A1,B1,Z1]=ForwardTable(C) ; (2) 逆向表[A2,B2,Z2]=ReverseTable(C) 。附录附录 A 算法流程图附录 B 算法的 MATLAB 实现附录 C 应用实例参考资料[1] 甘应爱, 田丰等. 运筹学( 第三版) [M]. 北京: 清华大学出版社, 200 5年6 月第三版: 286-290 [2] 戴一奇, 胡冠章, 陈卫. 图论与代数结构[M]. 北京: 清华大学出版社, 1995 年8 月第 1版: 28-32 附录 A 算法流程图附录 B 算法的 MATLAB 实现 function [earliest,latest,delay,road]=KeyPath(C) %========================================================================== %相关概念: %1、 PT 图:结点表示工序,若工序 i完成后工序 j才能启动,则图中有一条有向边(i,j) , %其长度表示工序 i所需时间。%2、 PERT 图:有向边表示工序,其长度表示权值,若 e(i) 完成后 e(j) 才能开始,则 e(i) %的终点是 e(j) 的起点。%3、对于同一工序而言: PERT 图的边与结点数更少; PERT 图的边数约等于 PT 图的结点数; %PT 图的使用更灵活,能适应某些额外约束。%4、设 G不存在有向回路,则可将 G的结点重新编号为 v1',v2',...,vn' ,使得对于任意%的边(vi',vj') ,有 i<j 。%==============================================================