Simplex method: Third iteration has same pivot row as earlier

Question

I have the following minimization problem:

$F(x)=-5x_1-4x_2$

Subject to:

$4x_1+x_2<20$

$3x_1+2x_2<18$

$x_2<6$

And of course $x_1,x_2>0$.

x1 x2 s1 s2 s3 F 
4  1  1  0  0  0  20
3  2  0  1  0  0  18
0  1  0  0  1  0  6
5  4  0  0  0  1  0

$5$ is the maximum value here, so I will use this as a pivot column. Taking the ratios I find that $\frac{20}{4} = 5$ is the lowest ratio. So this will be my pivot column. Now I reduce the rows (and then I find a new maximum and reduce again) to end up after two of these such operations with:

x1 x2 s1    s2    s3 F
1  0  2/5   -1/5  0  0 22/5
0  1  -3/5  4/5   0  0 12/5
0  0  3/5   -4/5  1  0 18/5
0  0  33/20 -11/5 0  1 -158/5

I still have a non negative value in the bottom row. But when I do the ratio test again, I find that

$$\frac{\frac{12}{5}}{-\frac{3}{5}}=-4$$

is my lowest value (lower than 11 & 6). But this would mean that I would have to row reduce the second row again, and that just doesn't work (I would lose the 1 at [2,2]).

Am I not supposed to take negative values for the ratio test into account, and therefore use the lowest positive value 6?

Doing this would mean reducing with [3,3], which makes a whole lot more sense to me.

Answer 1

I just found (GNU also found it, thank you) that only non-negative ratios matter. So the row with the 6 ratio should be the pivot row.

Answer 2

To find the pivot element you first have to choose the column with the highest coefficient (absolute value) of the objective function. Therefore the column of the pivot element is the first one: $max\{4,5\}=5$. Then you have to choose the row with the lowest non negative ratio of the RHS and the prospect pivot element in the same row.

For the first column we have the following ratios:

$\frac{b_1}{a_{11}}=\frac{20}{4}=5$

$\frac{b_2}{a_{21}}=\frac{18}{3}=6$

$\frac{b_3}{a_{31}}=\frac{6}{0}= \texttt{not defined}$

Thus the pivot element for the first iteration is $a_{11}=4$.