An Explicit Solution of a Special Class of Linear Programming Problems

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⁻¹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.