1
$\begingroup$

my question is: Find the dual to the problem: min $2y_1+3y_2+y_3$ s.t. $y_1+2y_2+y_3 \geq 2$, $y_1+y_2-y_3=1$, $y_2 \leq 0, y_3 \geq 0$

I'm really confused about the signs of the inequalities and variables. This is what I've done: max $2x_1+x_2$ s.t. $x_1+x_2=2$, $2x_1+x_2 \leq 3$, $x_1-x_2 \geq 1$, $x_1 \leq 0$, $x_2$ unrestricted in sign

Could someone tell me please whether or not my constraints in the dual are correct or whether they should be swapped? Also if anyone has any good tips for how to understand why the dual works then that'd be great!

Thanks :-)

$\endgroup$
  • 1
    $\begingroup$ A good way is to always write the Largangian and dual function from scratch - then you don't have to remember which inequalities are supposed to go which way etc. $\endgroup$ – Michal Adamaszek May 11 '18 at 15:51
0
$\begingroup$

It will be more pedagogical to know the general principle behind the primal and dual conversion.

The primal LP is

\begin{alignat}{5} \min \quad & z = & 2y_1 & + & 3 y_2 & + & y_3 & && \\ \mbox{s.t.} \quad & & y_1 & + & 2 y_2 & + & y_3 & \geq 2 && \tag{constraint 1} \\ & & y_1 & + & y_2 & - & y_3 & = 1 && \tag{constraint 2} \\ & & \rlap{y_2 \le 0, y_3 \ge 0} \end{alignat}

Using the SOB method, you can easily know in this minimisation problem

  • constraint 2 and $y_1$ are odd
  • $y_2$ is bizarre.
  • others are sensible

In the corresponding dual maximisation problem

  • $x_2$ and dual constraint 1 are odd
  • dual constraint 2 is bizarre.
  • others are sensible

\begin{alignat}{4} \max \quad & z = & 2x_1 & + & x_2 &&& \\ \mbox{s.t.} \quad & & x_1 & + & x_2 & = 2 && \tag{dual constraint 1} \\ & & 2 x_1 & + & x_2 & \ge 3 && \tag{dual constraint 2} \\ & & x_1 & - & x_2 & \le 1 && \tag{dual constraint 3} \\ & & \rlap{x_1 \ge 0} \end{alignat}

Therefore, dual constraints 2 & 3 and the sign of dual variable $x_1$ should be reversed.

$\endgroup$

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.