1
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    @MikeSpivey: could you previem my follow-up clarification q?2012-04-13
0

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.

  • 0
    ...is there something wrong with this?2012-02-26