Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Simplex Method - Programming Problem

  1. Apr 4, 2010 #1
    Simplex Method --- Programming Problem

    1. The problem statement, all variables and given/known data

    Here's the question -
    Conside the linear programming problem:

    maximise P = -3x + y,

    subject to 3x + 2y =< 24,
    4x + 9y =< 36,
    -2x + y =< 1,
    and x >= 0, y >= 0.

    Represent the problem as an initial Simplex tableau and use the Simplex algorithm to solve the problem. Interpret your final tableau.


    2. Relevant equations



    3. The attempt at a solution

    My problem is I'm usure how to tackle this with 3 subjects (ignoring the one with X and Y must be greater or equal to 0). I have completed questions in class with 2 subjects but my teacher nor my text book mention anything about 3 of them.

    I attempted it a couple of times with just putting it in a follow the steps as I would with 2 subjects but it doesn't seem to work perfectly. Is this the correct way?

    I would post my attempts but it'll get a bit complicated over the computer.

    Thank you in advance :)
     
  2. jcsd
  3. Apr 4, 2010 #2

    Mark44

    Staff: Mentor

    Re: Simplex Method --- Programming Problem

    The three inequalities are called constraints, not subjects. The idea is to maximize the objective function, subject to those constraints.

    To get this ready to put into a simplex tableau, you need to add one slack variable for each of the three inequalities that involve both x and y. This turns each inequality into an equation.

    For example, the first inequality becomes 3x + 2y + r = 24.
     
  4. Apr 4, 2010 #3
    Re: Simplex Method --- Programming Problem

    Thank you for the reply but I understand that much. I'm unsure if there is a different idea for 3 constraints (I forgot the word earlier).
     
  5. Apr 4, 2010 #4
    Re: Simplex Method --- Programming Problem

    I think I have worked it now - thank you all. :)
     
  6. Apr 4, 2010 #5

    Mark44

    Staff: Mentor

    Re: Simplex Method --- Programming Problem

    No, it's the same no matter how many constraints you have - one row in the tableau for each constraint equation (i.e., the equation you get after adding a slack variable to the constraint inequality).

    Once you get an answer, you can check by graphing the feasible region and confirming that the point you found maximizes the objective function.
     
  7. Apr 4, 2010 #6
    Re: Simplex Method --- Programming Problem

    Thank you for clearing that up Mark :)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook