0
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ @ 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$? $\endgroup$
    – masaheb
    Dec 10, 2021 at 8:44
  • $\begingroup$ 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. $\endgroup$
    – Siong Thye Goh
    Dec 10, 2021 at 8:54
  • $\begingroup$ 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$$ $\endgroup$
    – masaheb
    Dec 10, 2021 at 9:12
  • $\begingroup$ yup, that is correct. btw, for canonical form, can you check your note if your convention is $\le$ or $\ge$. $\endgroup$
    – Siong Thye Goh
    Dec 10, 2021 at 9:18
  • $\begingroup$ Do you mean the convention for the variables? $\endgroup$
    – masaheb
    Dec 10, 2021 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .