输送问题的强多项式算法——原设对偶型图上作业法  

A STRONG POLYNOMIAL ALGORITHM FOR THE TRANSSHIPMENT PROBLEM——GRAPHICAL METHOD IN PRIMAL-DUAL TYPE

作　　者：林国宁[1] 林诒勋[2] 

机构地区：[1]厦门大学 [2]郑州大学

出　　处：《高等学校计算数学学报》1989年第3期281-284,共4页Numerical Mathematics A Journal of Chinese Universities

摘　　要：输送问题的图上作业法是我国独创的方法,,曾有过一系列重要的研究工作(如[1],[2])。但计算复杂性问题没有解决。近年来,由于受算法设计观点的启发,我们在文章[3]中,对网络单形法的实现方案作了改进与分析,得到一种拟多项式时间的算法。本文进一步根据原设对偶算法原理,设计出一种对偶型的图上作业法。经算法分析,这是一种强多项式算法,其运算量不超过O(n^6)。这里n是网络顶点数。The graphical method of the transshipment problem arose in 1958[1,2]. In this paper, we present a strong polynomial algorithm which is based on the primal-dual approach, the network flow algorithm and the original graphical method. The time bound of the algorithm is O(n6), where n is the number of vertices in the network.

关 键 词：输送问题 对偶型 图上作业法 

分 类 号：O221.1[理学—运筹学与控制论]