Special Cases in Simplex Method2 min read


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
CB BV X1 X2 S1 S2 RHS Mini-Ratio
S1 1 4 1 12 3
S2 3 5 1 15 3
Zj
Cj-Zj 2 3

Here, we choose the row with Basic variable S1.

Case II

Cj 5 1
CB BV X1 X2 S1 S2 RHS Mini-Ratio
S1 1 4 1 9 9
1 X2 3 5 1 27 9
Zj 3 5 1 15
Cj-Zj 2 -4

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
CB BV X1 X2 S1 S2 RHS Mini-Ratio
S1 1 4 1 16 4
3 X2 3 5 1 15 3
Zj 9 15 3 45
Cj-Zj -7 -12 -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.

READ  Interpretation of Dual

Example

Maximization Problem

Cj 2 3  
CB BV X1 X2 S1 S2 RHS Mini-Ratio
S1 1 -4 1 16 -4
3 X2 3 -5 1 15 -3
Zj 9 -15 3 45  
Cj-Zj -7 18 -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 -M  
CB BV X1 X2 S1 S2 A RHS Mini-Ratio
S1 1 4 1 16 4
M A 3 5 1 1 15 3
Zj 9M 15M 3M 15M  
Cj-Zj 2-9M 3-18M -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.


Leave a Reply

avatar
  Subscribe  
Notify of
Close Menu