DEGENERACY IN LP PROBLEMS - Quantitative Techniques for management

Degeneracy in Linear Programming problem

The linear programming is the problem of degeneracy-the breaking down of the simplex calculation method under certain circumstances. Degeneracy in applying the simplex method for solving a linear programming problem is said to occur when the usual rules for the choice of a pivot row or column (depending on whether the primal or the dual simplex method is being discussed) become ambiguous.

In other words, two or more values in the minimum ratio column are the same. To resolve degeneracy, the following method is used. Divide the key column values (of the tied rows) by the corresponding values of columns on the right side. This makes the values unequal and the row with minimum ratio is the key row.

Example : Consider the following LPP,

Maximize Z = 2x1+ x2

Subject to constraints,
4x1 + 3x2≤ 12 ...................(i)
4x1+x2≤ 8 ...................(ii)
4x1– x2≤ 8 ...................(iii)

Solution: Converting the inequality constraints by introducing the slack variables,

Maximize Z=2x1+ x2

Subject to constraints,
4x1+ 3x2+ s3 = 12 ...................(iv)
4x1+ x2 + s4 = 8 ...................(v)
4x1– x2+ s5 = 8 ...................(vi)
Equating x1, x2 = 0, we get
s3 = 12
s4 = 8
s5 = 8

Illustrating Degeneracy

Illustrating Degeneracy

After entering all the values in the first iteration table, the key column is -2, variable corresponding is x1. To identify the key row there is tie between row s4 and row s5 with same values of 2, which means degeneracy in solution. To break or to resolve this, consider the column right side and divide the values of the key column values. We shall consider column x2, the values corresponding to the tie values 1, –1.

Divide the key column values with these values, i.e., 1/4, –1/4 which is 0.25 and – 0.25. Now in selecting the key row, always the minimum positive value is chosen i.e., row s4. Now, s4 is the leaving variable and x1 is an entering variable of the next iteration table. The problem is solved. Using computer and the solution is given in the following figure.

LPP Solved Using Computer with TORA (Output Screen)

LPP Solved Using Computer with TORA (Output Screen)

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd Protection Status

Quantitative Techniques for management Topics