When the smallest subscript rule doesn’t find a feasible solution in LP

integer programminglinear programmingoperations research

I've got a Linear Programming problem which is related to Bland's rule a.k.a. the smallest subscript rule.

The problem is as follows:

max $Z = 10x_1 + 12x_2 + 12x_3$

$\quad s.t$

$\quad x_1 + 2x_2 + 2x_3 + x_4 = 20$

$\quad 2x_1 + x_2 + 2x_3 + x_5 = 20$

$\quad 2x_1 + 2x_2 + x_3 + x_6 = 20$

$\quad x_1, …, x_6 \geq 0$

Here is my solution.

enter image description here

So, the objective function is composed of non-basis variables $x_3, x_4, x_5$ and their coefficients are all negative. Thus the simplex method is finished up, however, $x_6 = \frac{-20}{3} < 0$ so that this solution is not feasible.

Here is the question! My instructor taught that the smallest subscript rule will always get out of degenerate problem. Then should I say that even if this rule helps to get out of degeneracy, it do not guarantee the optimal solution.

Thanks a lot!

Edited:

enter image description here

I do the simplex method again (maybe in a correct way). I've got a feasible solution at (4, 4, 4) and the optimal value is 136. Then I can see that RHS are same at 2nd iteration(10, 10, 0) and 3rd iteration(10, 10, 0) and also max value as well (100). Thus, degeneracy can be observed but because of the smallest subscript rule, we can get out of degeneracy problem. Am I right?!

Best Answer

You did not perform the Simplex method correctly. Starting from a basic feasible solution, you should never get to an infeasible one. Bland's rule only ever tells you which of several legal pivots to perform: it does not ever permit illegal pivots.

Related Question