• 论文 • 上一篇    下一篇

大型线性规划问题的动态块主元算法

魏紫銮   

  1. 中国科学院计算中心
  • 出版日期:1981-02-20 发布日期:1981-02-20

魏紫銮. 大型线性规划问题的动态块主元算法[J]. 数值计算与计算机应用, 1981, 2(2): 114-121.

A DYNAMIC BLOCK PIVOTAL METHOD FOR LARGE-SCALE LINEAR PROGRAMMING

  1. Wei Zi-luan Computing Center, Academia Sinica
  • Online:1981-02-20 Published:1981-02-20
对于求解大型的线性规划问题,一个好的有效的算法必需具备三个条件:(1)应当能保证在给定的精度内具有数值可靠性;(2)它所占用的存储量要尽可能的小;(3)它能较快地求得问题的解,节省计算时间.标准的单纯形法显然不具备以上的条件.多年来,人们一直对单纯形(或修正单纯形)法提出各种不同的改进方法,使它能具有以上条件,这些改进的方法主要集中在两个方面,其一是对基矩阵的逆采用各种不同的表示形式,使它在求解过程中保持有较稀疏的结构,以减小存储量.如用初等矩阵的乘积形式表
This paper presents an algorithm of dynamic block pivot for the solution of large-seale linear programming. The algorithm consists of two main stages. In the first stage,we select, by means of general column selection rules, a set of incoming columns andminimize them locally. In the second stage, we bring up a method revise all the simplexmultipliers and reduced costs. It is shown that the modification used in the algorithm depends only on the initialsimplex multipliers and the reduced costs, and on the different rows of the basis inverse,the indices are exactly those of the corresponding columns which entered the basis in-verse ultimately; and it is independent of the intermediate quantities in the local mini-mization process. Furthermore, a pair of updating formulas is provided. The algorithm does not need to update all the simplex multipliers and the reducedcosts in each iteration. It needs only to update them once through a number of iteration.Thus the amount of operations, involved in updating the reduced costs is compaablewith that involved in each iteration.
()

[1] H. M. Markowitz, The elimination form of the inverse and its application to linear programming, Management Sci, Vol. 3(1957) 255-269.
[2] L. J. Lavsen, A modified inverse procedure for product form of inverse-linear programming codes, Commun. ACM, July, 1962.
[3] R. H. Bartels, G. H. Golub, The simplex method linear programming using LU decomposition, Commun. ACM. Vol. 12 (1969) , 266-268, 275-278.
[4] J. J. H. Forrest, J. A. Tomlin, Updated triangular factors of the basis to maintain sparsity in the product form simplex method, Math. Prog. Vol. 2(1972) 262-278.
[5] M. Benichou, J. M. Gauthier, G. Hentges. G. Ribiere, The efficient solution of large-scale linear programming problems-some algorithmic techniques and computational results, Math. prog. Vol. 13 (1977) , 280-322.
[6] P. M. J. Harris, Pivot selection methods of the DEVEX LP Code, Math. Prog. Vol. 5(1973) 1-28.
[7] E. Hellerman, D. Rarich, Reinversion with the preassigned pivot procedure. Math. Prog. Vol. 1 No. 2(1971) , 195-216.
[8] D. Goldfarb, J. K. Reid, A practicable steepest-edge simplex algorithm. Math. Prog. Vol. 12 (1977) , 361-371.
[9] J. de Buchet, How to take into account the low density of matrices to design a mathematical programming package, (in: Ed J. K. Reid large sparse sets of linear equations, Academic press, London, 1971) , 211-217.
[10] Mokhtar S. Bazaraa, C. M. Shetty, Nonlinear programming theory and algorithms, John Wiley & Sons, New York, 1979, 400-401.
No related articles found!
阅读次数
全文


摘要