# What is a Degenerate Optimal Solution in Linear Programming

When applying the Simplex Method to calculate the minimum coefficient or feasibility condition, if there is a tie for the minimum ratio or minimum coefficient it can be broken arbitrarily. In this instance, at least one basic variable will become zero in the following iteration, confirming that in this instance the new solution is degenerate. The practical implication of this condition indicates that the model has at least one redundant constraint.

## Degenerate Optimal Solution

Let’s consider the following Linear Programming model which we will solve using the Simplex Method and which we will also represent graphically with Geogebra:

We put the above problem in its minimized standard form, adding $x_{3}$ and $x_{4}$, as slack variables for constraints 1 and 2, respectively.

Which produces the following Simplex Method initial tableau:

To facilitate the fast convergence of the algorithm we select $x_{2}$ as the entering variable. Next we calculate the feasibility criteria (smallest coefficient): $Min\begin{Bmatrix}\frac{8}{4};\frac{4}{2}\end{Bmatrix}=2$ (if a tie exists we arbitrarily select variable $x_{3}$ as the variable that leaves the basis. Then we update the tableau:

Now $x_{1}$ enters the basis. The feasibility criteria determines that: $Min\begin{Bmatrix}\frac{2}{1/4};\frac{0}{1/2}\end{Bmatrix}=0$ $x_{4}$  leaves the basis. A new iteration is made:

The degenerate optimal solution is reached for the linear problem. Note that $x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18$. As this is a two-dimensional problem, the solution is overdetermined and one of the constraints is redundant just like the following graph confirms:

In practice knowing that some resources (like those associated with a constraint) are superfluous can be useful during the implementation of a solution. From a theoretical point of view, the degeneration has two implications: it produces the cycling or circling phenomenon (it’s possible that the Simplex Method repeats a series of iterations without ever improving the value of the objective function and the calculations are interminable, as can be observed in the previous example); the second theoretical aspect arises when iterations 1 and 2 are examined. Although they differ in the classification of basic and nonbasic variables, both produce identical values for all variables and for the objective value $x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18$.