# 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 $\displaystyle x\ge0$ $\displaystyle y\ge0$. Negate these and add them together to get $\displaystyle 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 $\displaystyle s_k$ are slack variables (the things you add to the inequalities to get equalities).

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