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 non-basic variable row
  • In case of choice between both basic variable, we will choose the basic variable with lower index.
  • In case of choice between both non-basic variables, we will choose the non-basic variable with 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 solution

The multiple optimal solution occurs when the optional solution is obtained but there exists basic solution in our solution. The multiple optional solution occurs 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 exists 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.

Advertisements