Balinski-Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and shows that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski-Tucker (B-T) Simplex Tableus. Furthermore, we give a strong polynomial algorithm for constructing such a B-T Simplex Tableau when a solution in the relative interior of the optimal face is known. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.