$a)$ Express the following optimization problem as a Linear Programming Problem (LPP):
$$\text{maximize }3x+3y-30$$$$\text{subject to }|x-2|+|y|\le5$$
Hint: you will need to express the inequality in another way so there is no absolute signs. For example the inequality $|x|\le3$ is equivalent to the pair of inequilities $x\le3\wedge x\ge-3$
$b)$ Explain why the following optimization problem is not a LPP: $$\text{maximize }3x+3y-30$$$$\text{subject to }|x-2|-|y|\le5$$
$a)$ Consider $$|x-2|+|y|\le5$$
$$\Leftrightarrow x-2+|y|\le5\wedge 2-x+|y|\le5$$
$$\Leftrightarrow |y|\le7-x\wedge |y|\le3+x$$
$$\Leftrightarrow (y\le-x+7\wedge y\ge x-7)\wedge(y\le x+3\wedge y\ge-x-3)$$
Basically we have,
$$\text{Maximize }3x+3y-30$$
Subject to,
$$y+x\le7$$$$x-y\le 7$$$$-x+y\le 3$$$$-x-y\le3$$
Which is in the form of General Linear Programming Problem (GLPP)
$b)$
Definition(GLPP)
The general linear programming problem can be stated as follows:
Find values of $x_1,x_2,\dots,x_n$ that will maximize or minimize,
$$z=c_1x_1+c_2x_2+\dots+c_nx_n\tag*{(1)}$$
subject to the restrictions,
$$\left.\begin{array}{r}a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n\le(\ge)(=)b_1\\a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n\le(\ge)(=)b_2\\\vdots\text{$\qquad\qquad\qquad$} \\a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n\le(\ge)(=)b_m\end{array}\right\}\tag*{(2)}$$
where in each inequality in $(2)$ one, and only one, of the symbols, $\le,\ge,= $ occurs.
(from “Elementary Linear Programming With Application" by Bernard Kolman $\cdot$ Robert E. Beck)
I think there are two reasons that make it not a general linear programming problem:
- It has costant on left side of inequality which isn't in the form of GLPP.
- It has absolute value apears in the inequality, that also not allowed in GLPP.
Does this answer part $b)?$
I only found the definition for GLPP from the book, is it the same as LPP $?$
Thanks for your help.