1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: A difficult LP problem

  1. Apr 26, 2009 #1
    1. The problem statement, all variables and given/known data

    Solve the LP problem?
    Minimize -x_{1} - 5x_{2} + x_{3}


    x_{1} + 3x_{2} + 3 x_{3} <= 4
    - x_{1} - 2x_{2} + x_{3} >= -5
    3x_{2} - x_{3} <= 3
    x_{1}, x_{2}, x_{3} >= 0

    Please explain how this process works (with all the steps), thanks.

    3. The attempt at a solution

    I read somewhere that in order to consider a minimized problem, one shall maximize: -x_{1} - 5x_{2} + x_{3}
  2. jcsd
  3. Apr 27, 2009 #2


    Staff: Mentor

    No, that's not it at all, although minimizing -x1 -5x2 + x3 is equivalent to maximizing +x1 +5x2 - x3. There is also the concept of the dual problem in linear programming, which is more involved than I have time or inclination to explain right now.

    For your problem, you have only three variables, so why don't you graph your feasible region? Any potential solution will occur at a corner point, so all you have to do is to evaluation your objective function (-x1 -5x2 + x3), and pick the point that gives you the smallest value.
  4. Apr 27, 2009 #3


    User Avatar
    Science Advisor

    The basic concept of LP is that the max or min of a linear function on a convex set occurs at a vertex. Find the vertices of the set (the points where the bounding planes intersect) and evaluate the object function at each one to determine where it is a minimum.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook