Convert problem to linear programming task

Question

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!

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 05 '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 05 '12 at 15:39

score 2 · Accepted Answer · answered Dec 05 '12 at 10:01

2

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$.

answered Dec 05 '12 at 10:01

pritam

10,157

but what if $|z|$ is in criterial function and not in restrictions??? – Smajl Dec 05 '12 at 15:35
@Smajl: You replace $|z|$ by $z^++z^-$ in the criterial function as well. – pritam Dec 06 '12 at 08:39

Convert problem to linear programming task

1 Answers1