Degeneracy In Linear Programming

Degeneracy example cont.:

Now to select the outgoing variable, we have to take limiting ratio in the replacement ratio column. But both the ratios are same i.e. = 2. Hence there exists a tie as an indication of degeneracy in the problem.

To solve degeneracy follow the steps mentioned below:

1. Divide the elements of identity column by column from left to right by the corresponding key column element.

Once the ratios are unequal select the lowest ratio and the row containing that ratio is the key row.

For the first column of the identity (i.e. the S1 column) the ratios are: 1/4, and 0/2. The lowest ratio comes in row of S2. Hence S2 is the outgoing variable. In case ratios are equal go to the second column and try.

Optimal solution is b = 2 and Profit is 2 × 9 = Rs. 18/–