Linear Programming - Simplex Method

• 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
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
I think the $s_k$ are slack variables (the things you add to the inequalities to get equalities).
I think the $s_k$ are slack variables (the things you add to the inequalities to get equalities).