1
$\begingroup$

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:
The first table
The second table
The third table (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.

$\endgroup$
0
$\begingroup$

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.