# Dual LP from Primal LP, how?

$$\min x +y + z$$

so that

$$x + y =2$$

and

$$y + z = 3$$

where, $x,y,z >0$. How to create the dual?

[Something like this?]

$$\max 2s + 3t$$

so that

$$...+... =1$$

and

$$...+...=1$$

-

The underlying idea of duality is very simple: there are no non-trivial linear consequences of linear inequalities and identities. The trivial consequence is just a linear combination of the given conditions with some coefficients, which are the unknowns for the dual problem.

So, you have 5 conditions: $x\ge0$, $y\ge 0$, $z\ge 0$, $x+y=2$ and $y+z=3$. You want to use them to estimate $x+y+z$ from below. You can add them up with coefficients $a,b,c,d,e$ to get $ax+by+cz+d(x+y)+e(y+z)\ge 2d+3e$ where $a,b,c$ must be $\ge 0$ not to revert the signs of the inequalities but $d,e$ can be arbitrary because the identities survive multiplication by any constants. Now, if you want to draw the conclusion about $x+y+z$ from here, you should have exactly it on the left, so we must have $a+d=1$, $b+d+e=1$, $c+e=1$. This, together with the already mentioned $a,b,c\ge 0$ gives you $6$ restrictions. Now, you want to get as large lower bound as possible and you get $2d+3e$, so the objective is $2d+3e\to\max$. That's all there is to it.

-
+1: This not only gives you the dual, but it also explains where the dual comes from. (Side comment: There's more than one way to form the dual. In fedja's formulation here, the $a,b,c$ variables are what would be the slack variables in the other standard formulation.) – Mike Spivey Jan 12 '12 at 16:45
Can you clarify "not to revert the signs of the inequalities but d,e can be arbitrary because the identities survive multiplication by any constants."? I dropped here. – hhh Apr 13 '12 at 21:00
@MikeSpivey: could you previem my follow-up clarification q? – hhh Apr 13 '12 at 21:20

Primal $$\min c'\bar{x}$$ $$A\bar{x} \leq \bar{b}$$ $$\bar{x}\geq0$$

Dual

$$\max \bar{b}' \bar{y}$$ $$A^{T} \bar{y} \leq \bar{c}$$ $$\bar{y}\geq0$$

Now work out the things.

-
...is there something wrong with this? – hhh Feb 26 '12 at 23:34