Linear Programming Simplex Method: How to pick leaving variable
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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 $fracb_ia_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=-frac659-frac89x_1-s_1+frac139s_2+frac49x_0$
$x_3=frac659+frac89+s_1-frac139s_2-frac49x_0$
$x_2=frac49-frac29x_1+0s_1+frac19s_2+frac19x_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 $fracb_ia_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
linear-programming
asked Sep 10 at 18:54
Rachel Kirkland
314
add a comment |Â
up vote
0
down vote
favorite
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 $fracb_ia_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=-frac659-frac89x_1-s_1+frac139s_2+frac49x_0$
$x_3=frac659+frac89+s_1-frac139s_2-frac49x_0$
$x_2=frac49-frac29x_1+0s_1+frac19s_2+frac19x_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 $fracb_ia_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
linear-programming
asked Sep 10 at 18:54
Rachel Kirkland
314
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.
– callculus
Sep 11 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 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_3geq 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.
– callculus
Sep 11 at 16:17
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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 $fracb_ia_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=-frac659-frac89x_1-s_1+frac139s_2+frac49x_0$
$x_3=frac659+frac89+s_1-frac139s_2-frac49x_0$
$x_2=frac49-frac29x_1+0s_1+frac19s_2+frac19x_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 $fracb_ia_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
linear-programming
asked Sep 10 at 18:54
Rachel Kirkland
314
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 $fracb_ia_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=-frac659-frac89x_1-s_1+frac139s_2+frac49x_0$
$x_3=frac659+frac89+s_1-frac139s_2-frac49x_0$
$x_2=frac49-frac29x_1+0s_1+frac19s_2+frac19x_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 $fracb_ia_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
linear-programming
linear-programming
asked Sep 10 at 18:54
Rachel Kirkland
314
asked Sep 10 at 18:54
Rachel Kirkland
314
asked Sep 10 at 18:54
Rachel Kirkland
314
asked Sep 10 at 18:54
Rachel Kirkland
314
asked Sep 10 at 18:54
Rachel Kirkland
314
314
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.
– callculus
Sep 11 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 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_3geq 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.
– callculus
Sep 11 at 16:17
add a comment |Â
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.
– callculus
Sep 11 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 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_3geq 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.
– callculus
Sep 11 at 16:17
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.
– callculus
Sep 11 at 14:14
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.
– callculus
Sep 11 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 at 15:18
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 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_3geq 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.
– callculus
Sep 11 at 16:17
First of all you multiply the first constraints by (-1) to get a positive number on the RHS: $-2x_1+5x_2-x_3geq 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.
– callculus
Sep 11 at 16:17
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2912229%2flinear-programming-simplex-method-how-to-pick-leaving-variable%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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.
– callculus
Sep 11 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 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_3geq 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.
– callculus
Sep 11 at 16:17