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

Question

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.

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:

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?!

Answer 1

Yes, your edited table is correct, see WA answer: $f(4,4,4)=136$ (max).

Here it is stated: "with Bland's selection rule, the simplex algorithm never cycles, so it is guaranteed to terminate in a bounded time." If you choose row $x_6$ (bigger subsript instead of $x_5$ as you did), the algorithm will cycle (between 2nd and 4th tables).

Answer 2

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.