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

• 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

Since all ?j ? 0, optimal basic feasible solution is obtained Therefore the solution is Max Z = 18, x1 = 0, x2 = 2
Note – Since a tie in minimum ratio (degeneracy), we find minimum of s1 /xk for these rows for which the tie exists.





Example 2

Max Z = 2x1 + x2 Subject to
4x1 + 3x2 ? 12
4x1 + x2 ? 8
4x1 - x2 ? 8
and x1 ? 0, x2 ? 0

Solution

Standard LPP
Max Z = 2x1 + x2 + 0s1 + 0s2 + 0s3 Subject to
4x1 + 3x2 + s1 = 12
4x1 + x2 + s2 = 8
4x1 - x2 + s3 = 8
x1 , x2 , s1, s2, s3 ? 0