An Explicit Solution of a Special Class of Linear Programming Problems

The linear programs considered here are of the form: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$$\mbox{maximize}\ (c, x)\quad \mbox{subject to }a\leq Ax \leq b,$$\end{document} 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.