# Linear program dual

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

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

Following the method described here:

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

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.