Linear programming with absolute value objective function

[csc2iffy]

Homework Statement

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.

Homework Equations

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.

 

[Ray Vickson]

Homework Statement

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.

Homework Equations

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.

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]

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'?

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]

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

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