The simplex method and unrestricted variables (Q790709)

Suppose that the simplex method is applied to a linear programming problem having m equality constraints and r unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count by rm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basic inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of an LU-factorization of the basis matrix.