I'm solving a LP using simplex method. Its the second time i've faced this situation.
This is the model:
$Max\space\space\space -3x_1+2x_2-x_3+x_4$
$s.t.$
$2x_1-3x_2-x_3+x_4+s_1=0$
$-x_1+2x_2+2x_3-3x_4+s_2=1$
$-x_1+x_2-4x_3+x_4+s_3=8$
$∀i∈\{1,2,3,4\} \space\space\space x_i≥0$
$∀i∈\{1,2,3\} \space\space\space s_i≥0$
I was solving the problem this way:
(In this table, i continued to use row elementary operations. )
The pivot row was the one reffering to $x_2$ (The third row). But when i subtracted the second multiple of that row, from the second row, the RHS of the second row became $-1$. But this means that the value of $s_1$ is $-1$. But $s_1$ had to be equal or greater than $0$. I don't know what is wrong. One idea i came with was to multiply the whole row into $-1$. But, in that way, the new problem will be that the coefficient of $s_1$ becomes $-1$, and that is not a good thing when $s_1$ is in the basis. I'm confused…
What am i doing wrong?
Note: I solved the problem with LINGO and it turns out that this LP has unbounded solution. I'm not sure if that's useful but anyway i wanted to put it here.
Best Answer
Suppose $a_{ij^*} \ \forall\ i$ are the elements of the chosen pivot column. And $b_{i} \ \forall\ i$ are the corresponding values of the RHS.The simplex algorithm says that you have calculate the minimum of the fractions. But $b_{i}$ has to be greater $\color{blue}{\textrm{ or equal}}$ than $0$ - not strictly positive. The short notation is
$\min\bigg\{\frac{b_i}{a_{ij^*}}|a_{ij^*}>0,b_i\geq 0\bigg\}$
In your case the calculation is
$\min\bigg\{\frac{0}{2},\frac{1}{2},\frac{8}{1}\bigg\}=\frac{0}{2}$
Therefore your first pivot element is $(s_1/x_2)$