• 论文 •

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

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

### 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

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!