# Maximize the LP in a standard LP and minimize it in a canonical form.

Maximize the following LP in a standard LP and minimize it in a canonical form. $$\text{min}\;\;\; z=-2x_1+x_2+5x_3$$ $$\text{s.t.}\;\;\; x_1+x_2-3x_3 \le 6$$ $$2x_1+3x_2-5x_3=7$$ $$-2x_1+x_2+5x_3 \ge -3$$ $$x_1 \le 0,x_3 \ge 0$$

I think the linear programming can be maximized in a standard LP like this: $$-\text{max}\;\;\; z=-2y-x_2-5x_3$$ $$\text{s.t.}\;\;\; -y+x_2-3x_3 +x_4= 6$$ $$-2y+3x_2-5x_3=7$$ $$2y+x_2+5x_3 -x_5= -3$$ $$y,x_3,x_4,x_5 \ge 0$$

And its minimization in a canonical form is:

$$\text{min}\;\;\; z=2y+x_2+5x_3$$ $$\text{s.t.}\;\;\; y-x_2+3x_3 \ge -6$$ $$-2y+3x_2-5x_3 \ge 7$$ $$2y-3x_2+5x_3 \ge -7$$ $$2y+x_2+5x_3 \ge -3$$ $$y,x_3 \ge 0$$

I would like to know how much of my work is correct.

Almost there.

According to the convention presented in Michel Goeman's note, we require all the variables to be nonnegative, hence we have to do a transformation to handle $$x_2=x_2^+-x_2^-$$ where $$x_2^+, x_2^- \ge 0$$.

• @ Siong Thye Goh, Can you explain my errors? Why do we require to rewrite $x_2$ as $x_{2}^{+}-x_{2}^{-}$ while $x_2$ is a free variable and hence ranges over $\mathbb R$, If you meant to rewrite $x_1$ (which is non-positive) as $x_{1}^{+}-x_{1}^{-}$ then why can't I just transform it to $-y$ with $y \ge 0$? Dec 10, 2021 at 8:44
• are we using the same definition? I think all variables have to be nonnegative right? hence we have to get rid of the free variables. Dec 10, 2021 at 8:54
• So for the first one we have $$-\text{max}\;\;\; z=-2y-x_{2}^{+}+x_{2}^{-}-5x_3$$ $$\text{s.t.}\;\;\; -y+x_{2}^{+}-x_{2}^{-}-3x_3 +x_4= 6$$ $$-2y+3x_{2}^{+}-3x_{2}^{-}-5x_3=7$$ $$2y+x_{2}^{+}-x_{2}^{-}+5x_3 -x_5= -3$$ $$x_{2}^{+},x_{2}^{-},y,x_3,x_4,x_5 \ge 0$$ And for the second one: $$\text{min}\;\;\; z=2y+x_{2}^{+}-x_{2}^{-}+5x_3$$ $$\text{s.t.}\;\;\; y-x_{2}^{+}+x_{2}^{-}+3x_3 \ge -6$$ $$-2y+3x_{2}^{+}-3x_{2}^{-}-5x_3 \ge 7$$ $$2y-3x_{2}^{+}+3x_{2}^{-}+5x_3 \ge -7$$ $$2y+x_{2}^{+}-x_{2}^{-}+5x_3 \ge -3$$ $$x_{2}^{+},x_{2}^{-},y,x_3 \ge 0$$ Dec 10, 2021 at 9:12
• yup, that is correct. btw, for canonical form, can you check your note if your convention is $\le$ or $\ge$. Dec 10, 2021 at 9:18
• Do you mean the convention for the variables? Dec 10, 2021 at 16:21