Degeneracy in Simplex Method
In some cases, there may be ambiguity in selecting the variable that should be introduced into the basis, i.e., there is a tie between the replacement ratio of two variables.
To resolve degeneracy in simplex method, we select one of them arbitrarily. Let us consider the following linear program problem (LPP).
Example - Degeneracy in Simplex Method
Maximize 3x1 + 9x2
subject to
x1 + 4x2 ≤ 8
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
Solution.
After introducing slack variables, the corresponding equations are:
x1 + 4x2 + x3 = 8
x1 + 2x2 + x4 = 4
x1, x2, x3, x4 ≥
0
Where x3 and x4 are slack variables.
Simplex Method: Table 1
| cj | 3 | 9 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | Solution values b (=XB) |
| 0 | x3 | 1 | 4 | 1 | 0 | 8 |
| 0 | x4 | 1 | 2 | 0 | 1 | 4 |
| zj-cj | -3 | -9 | 0 | 0 |
Minimum positive value (8/4, 4/2) = (2, 2)
There is a tie between the two values. So you are at liberty to break the tie arbitrarily.
In the following material, we will consider both the cases.
Case I
x4 departs & x2 enters.
Table 2
| cj | 3 | 9 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | Solution values b (=XB) |
| 0 | x3 | -1 | 0 | 1 | -2 | 0 |
| 9 | x2 | 1/2 | 1 | 0 | 1/2 | 2 |
| zj-cj | 3/2 | 0 | 0 | 9/2 |
x1 = 0, x2 = 2, z = 18
Case II
x3 departs & x2 enters.
Table
| cj | 3 | 9 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | Solution values b (=XB) |
| 9 | x2 | 1/4 | 1 | 1/4 | 0 | 2 |
| 0 | x4 | 1/2 | 0 | -1/2 | 1 | 0 |
| zj-cj | -3/4 | 0 | 9/4 | 0 |
x4 departs & x1 enters.
Table 3
| cj | 3 | 9 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | Solution values b (=XB) |
| 9 | x2 | 0 | 1 | 1/2 | -1/2 | 2 |
| 3 | x1 | 1 | 0 | -1 | 2 | 0 |
| zj-cj | 0 | 0 | 3/2 | 3/2 |
x1 = 0, x2 = 2, z = 18
The above example shows how to resolve degeneracy in linear programming (LP).
