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.
Asked
Active
Viewed 3,946 times
2
-
You can write $y_3=y_4-y_5$ where $y_4,y_5\geqslant 0$. – Math1000 Jun 03 '19 at 18:17
-
I know. But then how do you use this to find the dual? – Jun 03 '19 at 18:23
1 Answers
4
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.}$
callculus42
- 30,550
-
isn't a max problem supposed to be with <= constraints? Also, why do we put = to the last constraint and not to any other? – Jun 03 '19 at 19:10
-
@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). – callculus42 Jun 03 '19 at 19:17
-
@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. – callculus42 Jun 03 '19 at 19:21
-
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? – Jun 03 '19 at 19:25
-
@ThePoorJew Please notice I have made an edit to change my inequality signs. What do you mean by non-normal LP? Usually you multiply a constraint by (-1) if the RHS is negative. – callculus42 Jun 03 '19 at 19:28
-
A non-normal LP is if it's max and has >= in its constraints, and if its min it has <= in its constraints – Jun 03 '19 at 19:34
-
1@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. – callculus42 Jun 03 '19 at 19:44