1
$\begingroup$

We are trying to find the dual of the following linear program.

$$ \max_x \ 2x_1 \ + x_2 \ \ \ \ -- (1) $$

such that,

$$ x_1 + x_2 \leq 2 \ \ \ \ -- (2)\\ -x_1 - x_2 \leq -4 \ \ \ \ -- (3)\\ x_1 \geq 0 \\ x_2 \geq 0$$

I get the following answer.

$$ \min_\theta \ 4\theta_1 + 2\theta_2 $$

subject to,
$$ -\theta_1 - \theta_2\geq -2 $$

$$ \theta_1 + \theta_2\geq 1 \\ \theta_1 \geq 0 \\ \theta_2 \geq 0$$

Is this correct?

I'm confused because of $(3)$

$\endgroup$
0
$\begingroup$

Following the method described here:

http://www.cs.columbia.edu/coms6998-3/lpprimer.pdf

I get the following answer.

$$ \min_\theta \ 2\theta_1 - 4\theta_2 $$

subject to,
$$ \theta_1 - \theta_2\geq 2 $$

$$ \theta_1 - \theta_2\geq 1 \\ \theta_1 \geq 0 \\ \theta_2 \geq 0$$

$\endgroup$
1
$\begingroup$

Yep. bluesh34's solution is correct.

You needn't worry about $(3)$ (I'm assuming you're worried about all the terms being negative) since it's more important to have all the inequalities as $\leq$ in the primal problem.

The way I look at it visually is like this: Take your Primal LP and line up the variables: $$ \begin{array}{c c c c c} z= & 2x_1 & +2x_2 \\ & x_1 & + x_2 & \leq & 2 & (\theta_1)\\ & -x_1 & -x_2 & \leq & -4 & (\theta_2) \end{array} $$

Then by forming the dual, you assign your dual variables to the constraints in your primal. Every line in your dual problem can be simply determined by reading each column vertically - the right-most column is your objective function, and the rest are constraints. Following that, you should get bluesh34's solution.

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