Special Cases in Simplex Method

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

Cj2300
CBBVX1X2S1S2RHSMini-Ratio
0S11410123
0S23501153
Zj00000
Cj-Zj2300


Here, we choose the row with Basic variable S1.

Case II

Cj5100
CBBVX1X2S1S2RHSMini-Ratio
0S1141099
1X23501279
Zj350115
Cj-Zj2-400


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

Cj2300
CBBVX1X2S1S2RHSMini-Ratio
0S11410164
3X23501153
Zj9150345
Cj-Zj-7-120-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

Cj2300 
CBBVX1X2S1S2RHSMini-Ratio
0S11-41016-4
3X23-50115-3
Zj9-150345 
Cj-Zj-7180-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

Cj2300-M 
CBBVX1X2S1S2ARHSMini-Ratio
0S114100164
MA35011153
Zj9M15M03M15M 
Cj-Zj2-9M3-18M0-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.

Post a Comment

0 Comments