Register to reply

Linear programming with absolute value objective function

Share this thread:
csc2iffy
#1
Mar5-12, 07:59 PM
P: 76
1. The problem statement, all variables and given/known data

Minimize |2x1-3x2|
subject to
x1+x2≤5
-x1+x2≥-1
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
(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
abs val minimization.png  
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
Ray Vickson
#2
Mar5-12, 09:44 PM
Sci Advisor
HW Helper
Thanks
P: 5,086
Quote Quote by csc2iffy View Post
1. The problem statement, all variables and given/known data

Minimize |2x1-3x2|
subject to
x1+x2≤5
-x1+x2≥-1
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
(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
#3
Mar6-12, 03:18 PM
P: 76
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...

csc2iffy
#4
Mar6-12, 05:21 PM
P: 76
Linear programming with absolute value objective function

Alright, here is my graphical analysis:

optimal value = 0, occurs at (0,0) and (3,2)
is this correct?
csc2iffy
#5
Mar6-12, 08:21 PM
P: 76
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'?
Ray Vickson
#6
Mar6-12, 08:27 PM
Sci Advisor
HW Helper
Thanks
P: 5,086
Quote Quote by csc2iffy View Post
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'?
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
#7
Mar6-12, 08:58 PM
P: 76
But I'm trying to solve it using IOR and I can't have a function with absolute values I thought?
Ray Vickson
#8
Mar6-12, 10:07 PM
Sci Advisor
HW Helper
Thanks
P: 5,086
Quote Quote by csc2iffy View Post
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


Register to reply

Related Discussions
Optimization of a matrix with an objective function (for ML) Calculus 0
Writing an absolute value function as a piecewise function Precalculus Mathematics Homework 2
Optimization of objective function that's the product of unitary matrices Linear & Abstract Algebra 0
Linear Algebra (Linear Programming) Feasible solutions and extreme points. Calculus & Beyond Homework 1
Minimizing 5-d discontinuous objective function - alternatives to N-M Simplex Calculus 0