Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have function $\max \{ |x-1| + 2|y-1| | x,y \in R, x+y \leq 2 \}$. Can this problem be converted to LP? I think it cant because of the abs. value in criterial function, but Im not sure.

If it can, how to convert it? I think that restrictive conditions are already in correct form so I only have to convert criterial function to some form without abs. if its possible.. Thanks for advice!

share|improve this question
1  
Would converting it to 4 LP's work? $\max{x−1+2y−1}$ subject to $x+y≤2, x-1≥0, y-1≥0$, $\max{-x+1+2y−1}$ subject to $x+y≤2, x-1≤0, y-1≥0$, etc.? Then just take whichever is biggest as your solution? –  crf Dec 5 '12 at 10:00
    
So you suggest dividing the equation into four different with corresponding restrictions? I dont know if its LP after that but maybe youre right... –  Smajl Dec 5 '12 at 15:39
add comment

1 Answer

up vote 2 down vote accepted

Yes, it can be converted into LP. Use the following hint

Hint: $|z|$ can be replaced by $z^{+}+z^{-}$ along with the conditions $z^{+}\geq 0, z^{-}\geq 0$.

share|improve this answer
    
but what if $|z|$ is in criterial function and not in restrictions??? –  Smajl Dec 5 '12 at 15:35
    
@Smajl: You replace $|z|$ by $z^++z^-$ in the criterial function as well. –  pritam Dec 6 '12 at 8:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.