| Degeneracy in linear programming has been examined for its implications to algorithmic properties. A new pivoting technique devised to prevent cycling in the primal simplex method is the TNP-Rule of Gal and Geue. This rule is fully developed here, and is shown to preclude the possibility of cycling. The generalization presented here allows for implicit equalities as a source of degeneracy and for circumstances in which degeneracy is not restricted to a single extreme point of the feasible region. This development leads to the notion of a basis that "resolves" degeneracy and to the result that pivoting can be restricted to bases that directly specify a point of the relative interior of the feasible region. Also, a theorem is generalized and its proof corrected. The theorem here asserts that there exists a basis at a given extreme point with as many "transition columns" as there are dimensions of the feasible region if, and only if, all degeneracy at the point is caused by implicit equalities and weak redundancy.; The concept of "transition graphs" whose nodes are bases and whose edges are pivots is explored, and it is shown that a variety of special graphs is connected graphs, including those induced by the set of optimal bases and by the set of bases "compatible" with a given perturbation of the program rim. The TNP-Rule is modified in a natural way to aid in sensitivity analysis. By restricting pivoting to the set of bases that are compatible with a given perturbation of the rim, rate and range questions, such as concern dual prices and cost and right-hand-side ranging, can be resolved.; Degeneracy also raises questions of stability and the uniqueness and boundedness of solution sets. These are addressed, providing algebraic and pivot tableau conditions. A generalization of degeneracy is presented wherein degeneracy of feasible or solution sets is defined; a relation between the degeneracy of primal solution regions and the nonuniqueness of the dual solution is established. |
