Non-degeneracy in LP problem

Please send your query

Your Name (required)

Your Email (required)

Phone

Your Query

Non-degeneracy in LP problem

In solving linear programming problem, while improving the basic solution, it may so transpire that there is no scope to generate an optimal solution. This is known as ‘degeneracy’ in linear programming. This occurs when there is a tie in the minimum ratio column. 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 3: Consider the following LPP:
Maximize    Z = 2x1+ x2
Subject to constraints,
4x1 + 3x2
12
4x1+ x2
8
4x1 – x2
8
Solution:
Converting the inequality constraints by introducing the slack variables,
Maximize      Z = 2x1+ x2
Subject to constraints,
4x1 + 3x2
+ S3
= 12
4x1 + x2 + S4
= 8
4x1
– x2
+ S5
= 8
Equating x1, x2
= 0, we get
S3
= 12
S4
= 8
S5
= 8
                                                                         Table 3.8: Illustrating Degeneracy
Iteration
Basic
Solution
X1
X2
S3
S4
S5
Minimum
Equation
Number
Variables
Value
Ratio
0
S3
12
4
3
1
0
0
3
S4
8
4
1
0
1
0
2
S5
8
4
-1
0
0
1
2
-Z
0
-2
-1
0
0
0
For S4;
4/2 = 2
Tie
For S5;
4/2 = 2
After entering all the values in the first iteration table, the key column is –2, variable corresponding is x 1. 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 x 2, 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 S 4. Now, S4 is the leaving variable and x1 is an entering variable of the next iteration table. The problem is solved.