linear programming with absolute value objective function

csc2iffy

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

Minimize |2x₁-3x₂|
subject to
x₁+x₂≤5
-x₁+x₂≥-1
x₁≥0, x₂≥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
(0,0)=0
(1,0)=1
(3,2)=0
(0,5)=15
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 Thumbnails

 

Ray Vickson

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.

RGV

csc2iffy

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 x_i = x_i⁺ - x_i^-
|x_i| = x_i⁺ + x_i^-

But I'm still confused as to how to solve this...

csc2iffy

Alright, here is my graphical analysis:

optimal value = 0, occurs at (0,0) and (3,2)
is this correct?

csc2iffy

This is what I have after doing some research online:

Let X = 2x₁ - 3x₂

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

---->
Minimize X'
subject to
2x₁ - 3x₂ ≤ X'
-2x₁ + 3x₂ ≤ X'

Question, what is X'?

Ray Vickson

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.

RGV

csc2iffy

But I'm trying to solve it using IOR and I can't have a function with absolute values I thought?

Ray Vickson

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
s.t.
z >= 3
z >= -3

Solution: z = 3.

RGV