论网络图线路条数的计算及其应用.pdf

论网络图线路条数的计算及其应用 Lf7 贾春玉 )《I 在箭线式网络图中，线路是 由一系列首尾相接的工序组成。连接工序是结点。工序是线 路的重要组成部分 。关键线路是 由关键工序即工序总时差为零的工序所组成。在计算工程按 规定工期完工概率时，需计算关键线路的条数与次关键线路的条数．然后把他们接规定工期 完工概率之积近似为工程按规定工期完工概率 。在网络赶工问题 中．当赶工时间 (比工程最 短完工时间提前的时间)超过某工序 (除原关键工序外) 总时差时．则该工序就可能变为关 键工序，通过该 工序的线路也就不能按期完工。通过该工序线路条数就直接影响工程按规定 工期完工的概率，此外．当某道工序延期时，由此而影响通过该工序线路不能按期完成，当 延期超过该工序总时差时．则通过该工序线路条数的计算也直接影响工程完工概率。综上所 述，均需计算关键线路的条数、次关键线路的条数及通过该工序线路条数的计算。 线路条数的计算可以由始点至终点按箭线方向一一列举加以确定．然后计算条数的总和。 此方法虽然可行 ，但单纯计算线路条数 ，以及只需计算经过某遭工序线路条数并加 以确定其 构成时 ，此法在复杂网络图中就显得 力不从心 ，非常笨掘 为此．笔者提出两种计算网络图 线路条数 的方法 。 图 i 为了便于说明问题 ，我们做如下的规定与假设：在如图l所示的箭线式网络图中，用 “@”表示结点 (或称事项)．它表示工序 (或称活动)的开工或完工，它是相邻工序在时间 34 ‘ 上的分界点 x代表结点的编号。用 “——一”代表工序，它表示一个相对独立的活动 (工 序)。线路是指从网络始点开始，顺着箭线方向到网络图终点为止．中间由一系列首尾相连的 结点和箭线所组成的通路 。 假设网络图的编号规规是从左至右，箭头结点编号大于箭尾结点编号．且由连续 正整数 组成 (或称 自然数)。井规定始点编号为 I，终点编号为 n，则该网络图共有 n个结点。 设 Ai，k为从第 i结点至第 k结点线路条数 。 而 A．．．为第 l结点至第 j结点线路条数。 A．、n为第 j结点至终点 n线路条数 。 方法一 设Bi为第 i结点至终点n线路条数。B1．为第 i结点的紧后结点．即工序箭尾是第 i结点， 箭头是第k结点。其中n≥ki。则有：B，=A (为了简洁令B，=A )则第 j结点线路条散 函数为： B．∑Bi． 当第L结点 (L≥i4-i)不是第i结点的紧后结点时 (判断标准为工序 R (i．L)=一 。。)，B_-l— O 计算时，从最后一个结点 (终点)n开始．且令 B一l。经过 n步即可计算出线路条数 。 现举例说 明如下 ： 第 l步 ：B11=I 第2步LB ∑B 一 B l 一 J 第3步；B．。；∑B B】l4-Bl = J4-J = 2 第1步：B。一∑B．． Bl十 B 0 = 1+2 = 3 第5步：B：∑B = BT = I 第6步：B；∑B 一B。4-B” = 3+ I 一 第7步：B一∑B = B = 3 第8步，B：∑B =B自+B口 = 1 3 = 4 第9步：B．：∑B =B。+Bl = 1+ 1= 2 第10步：B，：∑B =B +‘B6+ B = 2+ 4+ 3 = 9 第11步：B：一∑B!lK — B +B +‘B 一 9+ 3+ d