Why is the following not a a linear programming problem?

Question

$$\begin{array}{ll} \text{maximize} & 3x + 3y − 30\\ \text{subject to} & |x−2|−|y| \leq 5\end{array}$$

This is totally a LLP to me, just not in its standard form. I really don't know why it is not? What I am missing? Thanks!

Answer 1

The optimisation problem in the question is NOT an LPP because an LPP has convex feasible region. We can easily check that $$S = \{(x,y)\in\Bbb{R}^2 \mid |x-2|-|y| \le 5\}$$ is not convex as $(10,\pm3) \in S$, but $(10,0) \notin S$.

This problem can be converted into an LPP by the usual trick in (2).

1. make the substitution $u = x-2$
2. split each decision variables into its positive and negative components.

\begin{alignat}{2} y^+ &:= \frac{|y|+y}{2} &\qquad y^- &:= \frac{|y|-y}{2} \\ u^+ &:= \frac{|u|+u}{2} & u^- &:= \frac{|u|-u}{2} \\ \therefore y &= y^+ - y^- & |y| &= y^+ + y^- \\ u &= u^+ - u^- & |u| &= u^+ + u^- \end{alignat} Then the objective function and the constraints become $3u^+ - 3u^- + 3y^+ - 3y^- - 24$ and \begin{cases} u^+ + u^- - y^+ - y^- &\le 5 \\ u^+, u^-, y^+, y^- &\ge 0 \\ u^+ u^- = y^+ y^- = 0 \end{cases} respectively.