1
$\begingroup$

The following linear optimization problem is given: $$ \begin{eqnarray} x_1 + 2x_2 -7x_3 \leq 1\\ |3x_1-5x_2-20| \leq 4 \\ x \geq 0 \\ 6x_1+5x_2-3x_3 \rightarrow min \end{eqnarray} $$ And it is my task to convert it into the normal form. The script of my professor says, that an LOP is in normal form if it has the following form: $$ \begin{eqnarray} Ax = b \\ x \geq 0 \\ c^Tx \rightarrow max \end{eqnarray} $$ That is not the problem so far. In this case I think I have to introduce variables for each inequality to let it become an equality. I'll call those variables $z_i$. (In German, these variables are called "Schlupfvariabeln", I did not found out the English word, sorry for that!) $$ \begin{eqnarray} x_1+2x_2-7x_3+z_1 = 1 \\ |3x_1-5x_2-20|+z_2 = 4 \\ x \geq 0 \\ z \geq 0 \\ 6x_1+5x_2-3x_3 \rightarrow min \end{eqnarray} $$

Until here, I think I that the two first rules $Ax=b$ and $x \geq 0$ are okay. Now I have the problem that I don't know how to transform $6x_1+5x_2-3x_3 \rightarrow min$ into a $\rightarrow max$ function. Can I introduce a variable e.g. $z_3$ there as well? Like $$ 6x_1+5x_2-3x_3+z_3 \rightarrow max $$Furthermore I am not sure whether the variable $x_2$ can be places there since there is an absolute value. Can I do it that way?

Finally, I have a third problem. In the book I learn the "algorithm" stops here. Our prof expanded the transformation into the normal form as the following:

He introduced other variables $y$ and replaced all the $x$ with e.g. $x_1 = y_1-y_4$ where $y_4$ can always be the same subtrahend if it is big enough. With my professor's algorithm, the LOP would somehow look like: $$ \begin{eqnarray} (y_1-y_4)+2(y_2-y_4)-7x_3+z_1 = 1\\ |3(y_1-y_4)-5(y_2-y_4)-20|+z_2 = 4 \\ x \geq 0 \\ y \geq 0 \\ z \geq 0 \\ (??) \rightarrow max \end{eqnarray} $$ where $(??) \rightarrow max$ is the solution of my first problem where I did not know how to transform a $\rightarrow min$ into a $\rightarrow max$ function.

So basically, my main questions are:

(1) How to transform the $\dots \rightarrow min$ in something like $\dots \rightarrow max$?

(2) Can I introduce a variable $z_2$ when there was an absolute value

And (3) which of those equations is the normal form? Is it enough to introduce variables to make an inequality an equality or do I really have to do this last step (which I unfortunately do not understand)?

$\endgroup$
  • $\begingroup$ these "Schlupfvariablen" are called slack variables in English. $\endgroup$ – user136457 Jan 7 '15 at 10:55
1
$\begingroup$

Hint:

If $|3x_1-5x_2-20| \leq 4$, Then:

$$-4 \leq 3x_1-5x_2-20 \leq 4$$

Therefore you can add these two constraints instead:

$$3x_1-5x_2-20 \leq 4$$

$$3x_1-5x_2-20 \geq -4$$

Or Equivalently:

$$3x_1-5x_2\leq 24$$

$$-3x_1+5x_2\leq -16$$

If the absolute value is in the objective, then you should introduce auxiliary variables and add similar constraints.

$\endgroup$
  • $\begingroup$ Thanks! Do I have to introduce different $z_i$ variables for each of those two equations? Or do both equations have the same $z_i$ variable? $\endgroup$ – Drudge Mar 22 '14 at 19:25
  • $\begingroup$ Yes, different $z_i$'s $\endgroup$ – Alt Mar 22 '14 at 19:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.