An Explicit Solution of a Special Class of Linear Programming Problems

Abstract

The linear programs considered here are of the form: where A is of full row rank, and ( LP ) is feasible with bounded optimal solutions. The main result is an explicit representation of the general optimal solution of ( LP ) in terms of a generalized inverse of A . This explicit solution of ( LP )—explicit in the sense that A −1 b is an explicit solution of Ax = b —has obvious theoretical (and possibly computational) advantages over the well-known iterative methods of linear programming. The results are illustrated by a simple example, and extensions to general linear programs are discussed.