ON THE DUAL PAIR OF LP-PROBLEMS IN CANONICAL FORM WITH NONNEGATIVE INVERSE MATRIX

Abstract

The dual pair of LP-problems

\[
\min\{z=c^Tx\mid Ax\geq b,\ x\geq 0\}, \qquad
\max\{w=b^Ty\mid A^Ty\leq c,\ y\geq 0\}
\]

where \(A\) is an \(n\times n\) matrix with inverse \(A^{-1}\geq 0\), is solvable iff \(c^TA^{-1}\geq 0\). Otherwise, the primal objective function \(z\) is unbounded on the feasible region. Some special cases of the matrix \(A\) are discussed.