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:

Degenerate Optimal Solution LP

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.

standard-Degenerate-Optimal

Which produces the following Simplex Method initial tableau:

initial tableau Degenerate Optimal Solution

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:

simplex Degenerate Optimal Solution

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:

Degenerate Optimal Solution simplex

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:

Degenerate Optimal Solution

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.

 

Rating: 4.6. From 9 votes.
Please wait...

, , , ,

Sin Comentarios aun. Se el primero en comentar!

Leave a Reply