Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 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.

share|improve this answer
1  
+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.

share|improve this answer
    
...is there something wrong with this? –  hhh Feb 26 '12 at 23:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.