1

Minimize: $\mid{x-y}\mid + 2z$

Subject to:

  • $0 \leq x \leq 3$,
  • $0\leq y \leq 4$,
  • $0 \leq z$,
  • $-x+y \geq 4$,
  • $x+y+z \leq 2$.

The following is what I did, I am looking to see if this is correct, or if there is an easier way to go about it the conversion of the LP above to standard form.

So, I know that I have to get rid of the absolute value signs. Thus, I will split this LP into two LPs, one with the constraints being that $x \leq y$ and one being that $y \leq x$.

Then I have to switch the minimization objective function to a maximization objective function, so I multiply the objective function by $(-1)$, which does this. I also have to get the $-x+y \geq 4$, sign switched to a "$\leq$" sign, so I multiply that equation by $(-1)$, Leaving me with the following:

If $x-y$ is positive:

Maximize $y-x-2z$

Subject to:

  • $x-y \leq -4$
  • $x+y+z \leq 2$
  • $0 \leq x \leq 3$
  • $0 \leq y \leq 3$
  • $0 \leq z$
  • $x \geq y$

And if $x-y$ is negative:

Maximize $y-x-2z$

Subject to:

  • $x-y \leq -4$
  • $x+y+z \leq 2$
  • $0 \leq x \leq 3$
  • $0 \leq y \leq 4$
  • $0 \leq z$
  • $x \leq y$
Pascal
  • 457
  • 1
    Looks mostly good. But in both cases you've written $x-y$ is positive, and you've got the same function to maximise. Also in the original question you've written $z leq z$, which was probably a typo! – B. Mehta Jun 02 '17 at 18:50

1 Answers1

2

The following two problems $$ P_1=\min |x-y|+2z,\quad (x,y,z)\in S $$ and $$ P_2=\min t+2z,\quad |x-y|\le t,\ (x,y,z)\in S $$ are equivalent, since clearly $P_1\le P_2$ and we can always take $t=|x-y|$ in $P_2$ to make them equal. Now $|x-y|\le t$ can be rewritten as $-t\le x-y\le t$, which makes the constraint linear.

A.Γ.
  • 29,518