degeneracy
•Degeneracy arises when there is a tie in the minimum ratio value that
determines the variable to enter into the next solution (Sharma,
2017).
•While solving the linear programming problem, if the minimum ratio
to identify the outgoing variable from the basic variables is not
unique. This situation prompt the degeneracy problem in LP problem.
Besides, if one or more basic variables have zero value, this a case of
degeneracy.
Degeneracy in linear programming
•This is a basic feasible solution in which some basic variables are zero.
•Example
•M𝑎𝑥 𝑍 = 3𝑋1+ 9𝑋2
Subject to
𝑋1+4𝑋2≤ 8
𝑋1+ 2𝑋2≤ 4
𝑋1, 𝑋2≥ 0
Initial simplex table-basic feasible solution
Contribution per unit
Ci
3
9
0
0
Quantity
Replacement Ratio
Variable
X1
X2
S1
S2
0
S1
1
4
1
0
8
8/4=2
