The simplex method and unrestricted variables |
| |
Authors: | M J Best R J Caron |
| |
Institution: | (1) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada |
| |
Abstract: | Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189 and by a postgraduate fellowship. |
| |
Keywords: | Linear programming simplex method unrestricted variables simplex multipliers LU-factorization |
本文献已被 SpringerLink 等数据库收录! |