A Class of Methods for Linear Programming

A class of methods is presented for solving standard linear programing problems. Like the simplex method, these methods move from one feasible solution to another at each iteration, improving the objective function as they go. Each such feasible solution is also associated with a basis. However, this feasible solution need not be an extreme point and the basic solution corresponding to the associated basis need not be feasible. Nevertheless, an optimal solution, if one exists, is found in a finite number of iterations. The nonbasic variables must be ordered in the methods of our class. Except for this characteristic, the simplex method [2] and the reduced gradient method [4] belong to this class.