0

I hope someone can help me. I am trying to get a head start on uni this year by learning some linear programming from a book, but it is getting confusing.

I have read that you pick the leaving variable by minimising the ratio $\{\frac{b_i}{a_{ij}} : a_{ij}>0\}$

However by doing this I seem to be going round in circles (I am presuming it is okay to reverse the leaving and entering variables on the next iteration - I read this on another question here)

So I have to following:

$ z=-\frac{65}{9}-\frac{8}{9}x_1-s_1+\frac{13}{9}s_2+\frac{4}{9}x_0$

$x_3=\frac{65}{9}+\frac{8}{9}+s_1-\frac{13}{9}s_2-\frac{4}{9}x_0$

$x_2=\frac{4}{9}-\frac{2}{9}x_1+0s_1+\frac{1}{9}s_2+\frac{1}{9}x_0 $

Is it wrong that $z$ is just $-x_3$?

I picked $s_2$ to enter and $x_2$ to leave as this is the only basic variable with a positive coefficient of $s_2$. But then on the next iteration I needed to pick $x_2$ to enter and $s_2$ to exit the basis. Have I done this wrong?

As an aside (another question - hope this is okay), if I am solving an auxiliary problem and have negatives, do I choose to the leaving variable is the one that minimises or maximises the ratio $\{\frac{b_i}{a_{ij}} : a_{ij}<0\}$?

I am so confused, I hope someone can help me. I realise it is not that important as I will learn how to do it properly in lectures, but I am really bored and need maths to do to keep me going for the next three weeks!

TIA

Rachel Kirkland
  • 122
  • Is it wrong that $z$ is just $-x_3$? No. It would be helpful if you wrote down the original LP. At the moment I cannot follow your explanations. – callculus42 Sep 11 '18 at 14:14
  • Thank you callculus for your reply. The original problem is as follows:

    maximise $-x_1-3x_2-x_3$ subject to $2x_1-5x_2+x_3 \le -5$, $2x_1-x_2+2x_2 \le 4$, $x_1,x_2,x_3 \ge 0$

     – Rachel Kirkland Sep 11 '18 at 15:18
  • First of all you multiply the first constraints by (-1) to get a positive number on the RHS: $-2x_1+5x_2-x_3\geq 5$ To get an equality we introduce a surplus variable. And since it is a \geq constraint we need additionally a artificial variable. $-2x_1+5x_2-x_3-s_1+a_1=5$ Now you can apply the simplex algorithm. – callculus42 Sep 11 '18 at 16:17

0 Answers0