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. Let M denote the submatrix in an optimal simplex tableau with columns corresponding to degenerate optimal dual basic variables. A primal optimal solution is unique if and only if there exists a nonvacuous nonnegative linear combination of the rows of M corresponding to degenerate optimal primal basic variables which is positive. The set of primal optimal solutions is bounded if and only if there exists a nonnegative linear combination of the rows of M which is positive. When M is empty the primal optimal solution is unique. (Author)