Lecture_8_Special cases in Simplex Metho

8.1 Degeneracy
The concept of obtaining a degenerate basic feasible solution in a LPP is known as degeneracy.
The degeneracy in a LPP may arise
Lecture 8
Linear programming :
Special cases in Simplex Metho
? At the initial stage when at least one basic variable is zero in the initial basic feasible
solution.
? At any subsequent iteration when more than one basic variable is eligible to leave the
basic and hence one or more variables becoming zero in the next iteration and the
problem is said to degenerate. There is no assurance that the value of the objective
function will improve, since the new solutions may remain degenerate. As a result, it is
possible to repeat the same sequence of simplex iterations endlessly without improving
the solutions. This concept is known as cycling or circling.
Rules to avoid cycling
? Divide each element in the tied rows by the positive coefficients of the key column in that
row.
? Compare the resulting ratios, column by column, first in the identity and then in the body,
from left to right.
? The row which first contains the smallest algebraic ratio contains the leaving variable.
Example 1
Max Z = 3x1 + 9x2
Subject to
x1 + 4x2 ? 8
x1 + 2x2 ? 4
and x1 ? 0, x2 ? 0
Solution
Standard LPP
Max Z = 3x1 + 9x2 + 0s1 + 0s2
Subject to
x1 + 4x2 + s1 = 8
x1 + 2x2 + s2 = 4
x1 , x2 , s1, s2 ? 0