Results 1 to 6 of 6

Math Help - Linear Programming - Simplex Method

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    190

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    422
    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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    383
    Quote Originally Posted by Aquafina View Post
    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.
    Last edited by BabyMilo; April 10th 2010 at 10:36 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    422
    I think the s_k are slack variables (the things you add to the inequalities to get equalities).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by maddas View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    422
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Programming - Elimination Method help
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: November 9th 2011, 07:55 AM
  2. Linear Programming: Degeneracy in Simplex Method
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: November 9th 2010, 05:18 PM
  3. Linear Programming, simplex method
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 8th 2010, 07:05 PM
  4. Linear Problem - Solve Using the Simplex Method
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: February 5th 2010, 12:35 AM
  5. Linear Programming - canonical form and simplex methods
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: July 31st 2007, 12:42 AM

Search Tags


/mathhelpforum @mathhelpforum