1
$\begingroup$

I'm learning how to convert primal LP problems to dual, but not sure if I'm doing it correclty.

primal: $$ \begin{align} maximize: \ \ \ \quad x_1 + 2x_2\qquad\quad \ \ \\ subject\ to:\ -2x_1 + x_2 + x_3 \qquad & = 2\\ -x_1 + 2x_2\quad + x_4\quad & = 7\\ x_1\qquad\qquad\ \ + x_5 & = 3\\ x_i \ge 0, i = 1, 2, 3, 4, 5 \end{align} $$

My attempt at the dual: $$ \begin{align} minimize: \ \ 2\lambda_1 + 7\lambda_2 + 3\lambda_3\\ subject\ to:\ -2\lambda_1 - \lambda_2 + \lambda_3 & \ge 1\\ \lambda_1 + 2\lambda_2\quad\ \ & \ge 2\\ \lambda_1, \lambda_2\ both\ free,\ & \lambda_3 \ge 0\\ \end{align} $$

$\endgroup$
  • $\begingroup$ You are forgetting a few constraints. Remember that row 0 is $x_1+2x_2+0x_3+0x_4+0x_5$ $\endgroup$ – Elliot G Dec 10 '15 at 8:14
1
$\begingroup$

$$ \begin{align} maximize: \ \ \ \quad x_1 + 2x_2\qquad\quad \ \ \\ subject\ to:\ -2x_1 + x_2 + \color{red}{ x_3} \qquad & = 2 \quad (\color{blue}{\lambda_1})\\ -x_1 + 2x_2\quad + \color{red}{x_4}\quad & = 7\quad (\color{blue}{\lambda_2})\\ x_1\qquad\qquad\ \ + \color{red}{x_5} & = 3\quad (\color{blue}{\lambda_3})\\ x_i \ge 0, i = 1, 2, 3, 4, 5 \end{align} $$

Because of the equality signs all $\lambda_i$ are free. But this is only an intermediate result. The constraints which results from the (red) $\color{red}{ x_i}$ are:

$\lambda_1\geq 0 \quad (\color{red}{ x_3})$

$\lambda_2\geq 0 \quad (\color{red}{ x_4})$

$\lambda_3\geq 0 \quad (\color{red}{ x_5})$

Beside this your dual program is fine.

$\endgroup$
  • $\begingroup$ So all free $\lambda_i$ are negligent by the end when including constraints from $x_3$ through $x_5$? $\endgroup$ – tloveless Dec 10 '15 at 16:49
  • $\begingroup$ Yes, that´s it. $\endgroup$ – callculus Dec 10 '15 at 16:51

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.