Primal to Dual Linear Programming

268 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

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