网络图关键线路计算法

出处：按学科分类—经济 湖北人民出版社《企业管理公式辞典》第402页（2545字）

网络图中，完成各道工序需要时间最长的路，称关键线路，它是网络计划中的主要矛盾线，决定着工程的完工期。在网络图上，我们可以通过找到工序总时差为零的工序即关键工序，由关键工序组成的线路得到关键线路。

关键线路的计算方法有三种：

方法一：图算法

在网络图上，计算出每个节点的最早开始时间(TE)及最晚完成时间(TL)，然后比较同一节点的最早开始时间与最晚完成时间，其差为零者即为关键节点，从头至尾与关键节点相连的工序即为关键工序，由此组成关键线路。

步骤：

(1)从左至右计算每一节点的最早开始时间。根据节点编号从小至大，顺序计算，并标在节点上方，用方框圈起来。

计算方法：定始点TE(i)=0

按公式TE(j)=max｛TE(i)+T(ij)｝推算。

(2)计算节点最晚完成时间，待图中全部节点最早开始时间计算完毕后，在图中从右至左，按节点编号从大至小，逆序计算，并标在节点上方，用三角框圈起来。

计算方法：定终点TL(n)=TE(n)

按公式：推算。

(3)计算节点(事项)时差，确定关键节点及关键工序，并用双线在图中标出关键线路。

计算方法：按TE(i)－TL(i)或TE(j)－TL(j)计算，为零者即为关键节点。实际上可采用观察法，节点上方“□”内数字与“Δ”内数字相同的节点，即为关键节点。

例，用图算法求下述网络关键线路及完工周期。

单位：天

关键线路：①→②→③→④→⑤→⑥→⑦→⑨→⑩→⑾

即：D→E→F→G→H→I→K→N

完工周期：38天。

方法二：表算法

设计表格，在表上填写各道工序及其作业时间，按照计算工序参数ES(ij)，EF(ij)，LS(ij)，LF(ij)及ZC(ij)的顺序，根据计算各项时间参数的公式，在表格上逐道工序进行计算。首先计算ES(ij)和EF(ij)，在表中由始点开始，按从上至下的顺序逐个工序进行。然后计算LS(ij)与LF(ij)，在表中由终点开始，由下至上逐个工序进行计算。然后根据上述参数，计算各道工序的总时差zC(ij)，由总时差为零的工序构成关键线路。

例：用表算法解图算法网络例题。

从表上由工序总时差为零的工序(表中标*者)，可得到关键线路：

D→E→F→G→H→I→K→N

完工期38天。

方法三：矩阵算法

矩阵法是将网络图反映的各工序间的关系，用一张矩阵表表示出来，以计算事项的时间参数来寻找关键线路的。

(1)制作矩阵表。作一张与网络图中节点数目相同的方形矩阵表，在横行与竖列上分别从上至下、从左至右按顺序写上事项编号。并以行为箭尾事项，列为箭首事项(矩阵表中i行与j列交叉元素，即表示工序i→j)，顺序把各工序作业时间填入相应格内。并在矩阵表中另加一行，另加一列(行加在矩阵表上方，列加在矩阵表左边)，用于填写计算出的事项最迟完成时间与最早开始时间。

(2)从上至下逐个计算事项最早开始时间。其方法是：首先规定TE(1)=0。计算某行TE时，找到与这一行数相同的列元素，将该列中有数字格中的数字与对应行的TE值相加，择其大者即为所求行对应事项TE值。

(3)TE列全部计算完毕后，然后计算事项最晚完成时间(即TL行数值)，计算顺序从右至左逐个进行。其方法是：规定最末TL(n)=TE(n)，即将表中TE列最下方数字填入TL列最右边格内。计算某列TL时，找到与这一列数相同的行元素，将该行中有数字格中的数字用对应列的TL值减掉，择其小者，即为所求列对应事项的TL值。

(4)从表上读出关键线路，在矩阵表中TE值与TL值相等的节点，即为关键节点，其交叉元素即为关键工序。

另外，从矩阵表上还可直接计算出各工序总时差。其方法是：将矩阵表中有数字格所在列对应的TL值，减去所在行对应的TE值，再减去该元素值，即为该工序总时差，可填在该格用“()”括起。

例：用矩阵算法解图算法例题。

由表中读出关键线路：①→②→③→④→⑤→⑥→⑦→⑨→⑩→⑾

即D→E→F→G→H→I→K→N

完工周期：38天。