网络上两类物资联合最大流问题的极流特征

当网络上(诸如交通网络、通讯网络)有多种不同物资或信息同时分别从相应的发点输送到相应的收点,要求每条线路上各类物资或信息的输送量总和不超过线路的容量时,寻求所有物资的最大输送量的问题,就是所谓网络多种物资的最大流问题,这个问题在生产实际和理论上都有着重要的意义,1963年T.C.Hu提出了求两类物资联合最大流的标号方法,但是为了保证有限步达到最大流,要求边的容量是偶数。 本文是文献3]的继续,用图论的语言描述了两类物资最大流问题极流的特征,并对标号方法作了一点修改,使得有限步得到最大流,或者在某一步得到极流后,保证以后的迭代是从极流到极流.这样因极流的个数是有限的,并且最大流总可以在极流上达到,从而保证了有限步内得到所要求的最大流,无须对边的容量作任何限制, 本文所提的算法是使图形特征很强的标号算法和线性规划的极点迭代结合起来,这就使得有可能把这种方法,推广到更大的一类问题中,例如,研究容量的改变对最大流量的影响。