Canonical bases in linear programming (Q908850)

The author introduces an alternative unified development of primal and dual simplex methods for linear programming problems. In the most well- known primal method, the notion of bases for the range of the constraint matrix plays a predominant role both in the algebraic description and in the geometric interpretation of moving along edges connecting adjacent extreme points of the feasible domain. Here, the author rather specifies the notion of bases for the null space of the constraint matrix, and he refers to these as canonical bases. Hence, this leads the author to state both the primal and dual algorithms as feasible direction methods which are very similar. Two practical advantages of the approach are mentioned. First, primal or dual feasibility is not required, and, second, it is easy to switch between primal and dual algorithms. Basic results on canonical bases are first introduced. These bases are computed using Gauss-Jordan elimination. Furthermore, the updating is simplified whenever pivoting between adjacent canonical bases. The paper also includes a geometric interpretation of canonical bases and simplified versions of the algorithms.