Degeneracy in Linear Programming: A Simple Geometric Interpretation - Nelson, Richard R. (The Review of Economics and Statistics, 1957)
ONE of the more conceptually mysterious aspects of linear programming is the problem of degeneracy the breaking down of the simplex calculation method under certain circumstances. Although a set of rules for dealing with degeneracy is well known, in the absence of an understanding of the nature of the problem the rules must be followed by rote. This note presents a simple geometrical explanation of the problem, the solution, and explains why certain types of programming problems frequently lead to degeneracy. It is hoped that the presentation will be of use both to students and teachers of linear programming. Before presenting the geometry of degeneracy, it is necessary to review briefly the geometry of linear programming and the simplex method of computing optimum linear programs.