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: Linear programming with absolute value objective function

  1. Mar 5, 2012 #1
    1. The problem statement, all variables and given/known data

    Minimize |2x1-3x2|
    subject to
    x1≥0, x2≥0

    (a) Solve the problem graphically.
    (b) Formulate a linear program that could be used to solve the problem. Use software to solve your LP and show how to reconstruct a solution to the original problem.

    2. Relevant equations

    3. The attempt at a solution

    I started graphing the problem and posted an attachment of what I have. I usually solve these by way of the corner point method (just to check that my graphical method is correct), but once I found my corner points for this problem I found that 2 of them have the same value but are not adjacent CPF solutions
    This is what's confusing me... also, how would I show the graphical method when absolute value is involved? I started to try it, but I would like to know if I'm doing it correctly before going further.

    Attached Files:

  2. jcsd
  3. Mar 5, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I assume the question wants you to give an LP formulation---that is, a formulation that does *not* have any absolute values in it. Formulating such problems is standard, and can be found in any introductory LP or Operations Research book. You can even look on line.

  4. Mar 6, 2012 #3
    Yes that's basically what I'm trying to ask about here. I tried looking in my book but I can't seem to find absolute value objective functions.
    I remember my teacher talking about this but her example isn't about absolute value objective

    let xi = xi+ - xi-
    |xi| = xi+ + xi-

    But I'm still confused as to how to solve this...
  5. Mar 6, 2012 #4
    Alright, here is my graphical analysis:

    optimal value = 0, occurs at (0,0) and (3,2)
    is this correct?
    Last edited: Mar 6, 2012
  6. Mar 6, 2012 #5
    This is what I have after doing some research online:

    Let X = 2x1 - 3x2

    Minimize |X|
    subject to
    X ≤ X'
    -X ≤ X'

    Minimize X'
    subject to
    2x1 - 3x2 ≤ X'
    -2x1 + 3x2 ≤ X'

    Question, what is X'?
  7. Mar 6, 2012 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I don't understand your question. The optimal X' will be the minimal value of |2x1 - 3x2|; after all, it is >= both (2x1 - 3x2) and -(2x1 - 3x2), and you minimize it.

  8. Mar 6, 2012 #7
    But I'm trying to solve it using IOR and I can't have a function with absolute values I thought?
  9. Mar 6, 2012 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You don't have any absolute values any more---that was the whole point of introducing the new variable X'.

    Watch me compute |-3| without using absolute values:
    min z
    z >= 3
    z >= -3

    Solution: z = 3.

    Last edited: Mar 6, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook