1. Not finding help here? Sign up for a free 30min 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!

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}

    when

    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

    Mark44

    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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook