# Linear Programming - Simplex Method

Printable View

• Apr 10th 2010, 05:51 AM
Aquafina
Linear Programming - Simplex Method
Hi. I would like to get a FULLY WORKED solution of the following problem.

Maximize p = -x - y subject to
-x + 2y <= 4
3x + y <= 9
x >= 0
y >= 0

Initial starting point:
x=0
y=0

PS: I obtained the following solution from a website.

Tableau #1
x y s1 s2 s3 s4 p
-1 2 1 0 0 0 0 4
3 1 0 1 0 0 0 9
1 0 0 0 -1 0 0 0
0 1 0 0 0 -1 0 0
1 1 0 0 0 0 1 0

Tableau #2
x y s1 s2 s3 s4 p
-1 2 1 0 0 0 0 4
3 1 0 1 0 0 0 9
-1 0 0 0 1 0 0 0
0 1 0 0 0 -1 0 0
1 1 0 0 0 0 1 0

Tableau #3
x y s1 s2 s3 s4 p
-1 2 1 0 0 0 0 4
3 1 0 1 0 0 0 9
-1 0 0 0 1 0 0 0
0 -1 0 0 0 1 0 0
1 1 0 0 0 0 1 0

Sorry if this post is in the wrong forum!
• Apr 10th 2010, 07:15 AM
maddas
The solutions must lie in the quadrant $x\ge0$ $y\ge0$. Negate these and add them together to get $p=-x-y \le 0$. Since p is 0 in the region of interest only at (0,0), this inequality tells us 0 is the maximum for p achieved at (0,0).

If you do use the simplex method,it suffices to check just the vertices. I think they are (0,0) (0,2) (2,3) (3,0).
• Apr 10th 2010, 09:18 AM
BabyMilo
Quote:

Originally Posted by Aquafina
Hi. I would like to get a FULLY WORKED solution of the following problem.

Maximize p = -x - y subject to
-x + 2y <= 4
3x + y <= 9
x >= 0
y >= 0

Initial starting point:
x=0
y=0

PS: I obtained the following solution from a website.

Tableau #1
x y s1 s2 s3 s4 p
-1 2 1 0 0 0 0 4
3 1 0 1 0 0 0 9
1 0 0 0 -1 0 0 0
0 1 0 0 0 -1 0 0
1 1 0 0 0 0 1 0

Tableau #2
x y s1 s2 s3 s4 p
-1 2 1 0 0 0 0 4
3 1 0 1 0 0 0 9
-1 0 0 0 1 0 0 0
0 1 0 0 0 -1 0 0
1 1 0 0 0 0 1 0

Tableau #3
x y s1 s2 s3 s4 p
-1 2 1 0 0 0 0 4
3 1 0 1 0 0 0 9
-1 0 0 0 1 0 0 0
0 -1 0 0 0 1 0 0
1 1 0 0 0 0 1 0

Sorry if this post is in the wrong forum!

what do the tableaus mean?

do you mean P=x+y
=> P-x-y=0

I see no reasons why you have 4 slack variables.
as you have 2 variable equations.
• Apr 10th 2010, 09:22 AM
maddas
I think the $s_k$ are slack variables (the things you add to the inequalities to get equalities).
• Apr 10th 2010, 09:58 AM
Aquafina
Quote:

Originally Posted by maddas
I think the $s_k$ are slack variables (the things you add to the inequalities to get equalities).

Thanks for your help. However, would you be able to give me a fully worked solution using the Simplex method?
• Apr 13th 2010, 10:52 AM
maddas
The heart of the simplex method is the observation that the extremum of a linear function on a simplicial complex occurs at one of the vertices. So it is easy to check all the vertices in this case and see that (0,0) is, in fact, the minimum. I'm not sure what you want exactly.