2
$\begingroup$

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

Basicly we have

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\\\color{lightgrey}{\text{by the way, can anyone help me eidt those dots to$\color{darkwhite}{\text{ (about here)}}$ center, thx}\rightarrow}\vdots\\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 isn't a general linear programming problem

First it has costant on left side of inequality which isn't in the form of GLPP

Second it has absolute value apears in the inequality, that also not allowed in GLPP

Does this answers $b)?$

I only found definition for GLPP from the book, is it same as LPP $?$

Thanks for your help.

$\endgroup$
  • $\begingroup$ A GLP(P) is an LP(P). I think a GLP(P) should be distinguished from an LP(P) in standard form. GLP(P) is typically the abbreviation for a generalized LP (which is not an LP). $\endgroup$ – LinAlg Oct 3 '19 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.