Optimal simplex tableau characterization of unique and bounded solutions of linear programs

Uniqueness and boundedness of solutions of linear programs are characterized in terms of an optimal simplex tableau. LetM denote the submatrix in an optimal simplex tableau with columns corresponding to degenerate optimal dual basic variables. A primal optimal solution is unique iff there exists a nonvacuous nonnegative linear combination of the rows ofM, corresponding to degenerate optimal primal basic variables, which is positive. The set of primal optimal solutions is bounded iff there exists a nonnegative linear combination of the rows ofM which is positive. WhenM is empty, the primal optimal solution is unique.This research was sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS-79-01066.