**Degeneracy**

The degeneracy occurs when the mini-ratio comes equal. The degeneracy makes the solution lengthy. When degeneracy occurs, we will choose the row with

- In case of choice between basic and non-basic variable, we will choose the non-basic variable row
- In case of choice between both basic variables, we will choose the basic variable with a lower index.
- In case of choice between both non-basic variables, we will choose the non-basic variable with a lower index.

**Example**

**Maximization Problem**

Suppose X1, X2, S1, S2 are the decision variables where S1 and S2 are our basic variables and x and y are our non-basic variables.

**Case I**

Cj | 2 | 3 | 0 | 0 | |||

CB | BV | X1 | X2 | S1 | S2 | RHS | Mini-Ratio |

0 | S1 | 1 | 4 | 1 | 0 | 12 | 3 |

0 | S2 | 3 | 5 | 0 | 1 | 15 | 3 |

Zj | 0 | 0 | 0 | 0 | 0 | ||

Cj-Zj | 2 | 3 | 0 | 0 |

Here, we choose the row with Basic variable S1.

**Case II**

Cj | 5 | 1 | 0 | 0 | |||

CB | BV | X1 | X2 | S1 | S2 | RHS | Mini-Ratio |

0 | S1 | 1 | 4 | 1 | 0 | 9 | 9 |

1 | X2 | 3 | 5 | 0 | 1 | 27 | 9 |

Zj | 3 | 5 | 0 | 1 | 15 | ||

Cj-Zj | 2 | -4 | 0 | 0 |

Here, we choose the row with non-basic variable X2.

**Multiple optimal solutions**

The multiple optimal solutions occur when the optional solution is obtained but there exists a basic solution in our solution. The multiple optional solutions occur when the objective function is parallel to one of its constraints.

**Example**

**Maximization Problem**

Cj | 2 | 3 | 0 | 0 | |||

CB | BV | X1 | X2 | S1 | S2 | RHS | Mini-Ratio |

0 | S1 | 1 | 4 | 1 | 0 | 16 | 4 |

3 | X2 | 3 | 5 | 0 | 1 | 15 | 3 |

Zj | 9 | 15 | 0 | 3 | 45 | ||

Cj-Zj | -7 | -12 | 0 | -3 |

Cj-Zj is free of positive values so we have obtained the optimal solution. But still, there is basic variable in our system, that is, S1.

**Unbounded**

The unbounded solution occurs when all the mini-ratio comes negative, which is not desirable in simplex, that is, the elements in the pivot column are negative.

**Example**

**Maximization Problem**

Cj | 2 | 3 | 0 | 0 | | ||

CB | BV | X1 | X2 | S1 | S2 | RHS | Mini-Ratio |

0 | S1 | 1 | -4 | 1 | 0 | 16 | -4 |

3 | X2 | 3 | -5 | 0 | 1 | 15 | -3 |

Zj | 9 | -15 | 0 | 3 | 45 | | |

Cj-Zj | -7 | 18 | 0 | -3 | |

The Mini-ratio appears to be negative. So, the solution is unbounded.

**Infeasibility**

The solution is said to be infeasible if the artificial variable remains though we have obtained the optimal solution or there does not exist any scope for further optimization.

**Example**

**Maximization Problem**

Cj | 2 | 3 | 0 | 0 | -M | | ||

CB | BV | X1 | X2 | S1 | S2 | A | RHS | Mini-Ratio |

0 | S1 | 1 | 4 | 1 | 0 | 0 | 16 | 4 |

M | A | 3 | 5 | 0 | 1 | 1 | 15 | 3 |

Zj | 9M | 15M | 0 | 3M | 15M | | ||

Cj-Zj | 2-9M | 3-18M | 0 | -3M | |

Since the Cj-Zj row is free of positive numbers, the optimal solution is obtained but the artificial variable A is still present in our solution.

## 0 Comments