# Thread: Linear Programming - Simplex Method

1. ## 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!

2. 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).

3. 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.

4. I think the $s_k$ are slack variables (the things you add to the inequalities to get equalities).

5. 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?

6. 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.