# In Simplex Method, if the leaving variable fails for all candidates of MRT, what's wrong?

I'm facing a problem programming a full tableau solver for some LP problems.

The difficulty is when the test for leaving (line) variable cannot find a single positive value on the pivot column for the Minimum Ratio Test.

When this happens, the program backtracks and tries another entering (column) variable candidate. But there's a dead-end eventually.

For the choice of entering column I've tried two methods:

1. Fast rate of increase of object function
2. Smallest subscript (lowest column index)

My question is, when this happens is the problem impossible to solve or I'm making a big mistake? I've run the same problem on lp_solve and it runs just fine.

Thanks.

-

$$\begin{matrix} \text{Basic Variable}& Z & x_1 & x_2 & x_3 & x_4 & x_5 & \text{Right-Hand Side}\\ \hline Z & 1 & 1/2 & -2 & 0 & 3/2 & 0 & 3 \\ \hline x_3 & 0 & 1/2 & 0 & 1 & 1/2 & 0 & 1 \\ x_5 & 0& -1 & -1 & 0 & -1 & 1 & 0 \\ \end{matrix}$$
In this example, the only choice for leaving variable is $x_2$, and there are no positive values in its pivot column. If we rewrite the tableau in equation form, it becomes $$Z = 3 - 1/2x_1 + 2x_2 - 3/2 x_3,$$ $$x_3 = 1 - 1/2x_1 - 1/2 x_4,$$ $$x_5 = 0 + x_1 + x_2 + x_4.$$
Letting $x_2$ enter the basis means increasing $x_2$. Normally, we increase the entering variable until doing so any more would make one of the current basic variables negative (and thus the current solution infeasible). However, the fact that there are no positive values in $x_2$'s column means that increasing $x_2$ does not cause any of the current basic variables to decrease: the value of $x_3$ remains at $1$, the value of $x_5$ actually increases with $x_2$, and the values of $x_1$ and $x_4$ remain $0$. Thus we can increase $x_2$ indefinitely without any other variable going negative, which means we can increase the objective function indefinitely in this direction without the current solution ever becoming infeasible. This means the problem is unbounded.