2
$\begingroup$

min $ = 4y_1 +2y_2 - y_3 $

$s.t. y_1 + 2y_2 +2y_3 <= 6$

$s.t. y_1- y_2 + 2y_3 = 8$

$y_1, y_2 >= 0, y_3 $urs

How do I find the dual to this LP? What confuses me is the = sign. Also the urs variable. I'm not sure how to act on these.

$\endgroup$
2
  • $\begingroup$ You can write $y_3=y_4-y_5$ where $y_4,y_5\geqslant 0$. $\endgroup$
    – Math1000
    Commented Jun 3, 2019 at 18:17
  • $\begingroup$ I know. But then how do you use this to find the dual? $\endgroup$
    – user634512
    Commented Jun 3, 2019 at 18:23

1 Answer 1

4
$\begingroup$

With the table below you do not need to transform $y_3$. You have to read the table from right to left, since the primal problem is min-problem. The dual of the LP is

$\texttt{max} \ \ 6u_1+8u_2$

$u_1+u_2\leq 4 \quad (y_1)$

$2u_1-u_2\leq 2 \quad (y_2)$

$2u_1+2u_2=8 \quad (y_3)$

$u_1\leq 0, u_2 \text{ unrestr.}$

enter image description here

$\endgroup$
7
  • $\begingroup$ isn't a max problem supposed to be with <= constraints? Also, why do we put = to the last constraint and not to any other? $\endgroup$
    – user634512
    Commented Jun 3, 2019 at 19:10
  • $\begingroup$ @ThePoorJew "isn't a max problem supposed to be with <= constraints?" Mostly. But there can be other constraints as well. With the same argument you can ask a similar question for the primal. In general I don´t say that there exists a optimal solution (for both). "Also, why do we put = to the last constraint and not to any other?" Because $y_3$ is unrestricted (seventh line of the table). $\endgroup$ Commented Jun 3, 2019 at 19:17
  • $\begingroup$ @ThePoorJew I´ve added the corresponding variables. You can try to convert back the dual to the primal. It should be the same primal as you have in your question. $\endgroup$ Commented Jun 3, 2019 at 19:21
  • $\begingroup$ But, from what I know,if our primal is a nonnormal form LP, I have to multiply the <= constraint with (-1), yielding -y1-2y2-2y3>=-6. And then proceed. Am I wrong? $\endgroup$
    – user634512
    Commented Jun 3, 2019 at 19:25
  • 1
    $\begingroup$ @ThePoorJew Usually you solve an LP with the simplex algorithm. In case of $\geq$-constraints you add an artificial constraint. But if you want to multiply a $\geq$ constraint by (-1) to obtain a "normal" LP, you can do it. It doesn´t affect the dual problem. $\endgroup$ Commented Jun 3, 2019 at 19:44

You must log in to answer this question.