Linear Programming - Simplex Method

Printable View

April 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!
April 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).
April 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.
April 10th 2010, 09:22 AM
maddas

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