DUALITY: A REAL-LIFE STORY.

BY ASHISH GOEL.

Read Chapter 1 of http://www.stanford.edu/~ashishg/msande111/notes/supplement.pdf for this to make sense.

Narrator: Louie Thief and Tony Soprano are negotiating.

Tony: Nice setup you got here, Louie. You broke into the warehouse, there is gold here and diamond and silver, and you have a knapsack to carry this. Tell you what. I will buy this whole operation off of you.

Louie: Sounds good boss. The gold is worth 5, the diamond is 20, the silver is 3. I will give you a 10% discount, seeing you are a family man and all. So just pay me $26.

Tony: Get real, Louie. We got no way to carry this whole inventory out of here. Won't fit in your knapsack. Tell you what, I will give you a price for the gold, silver, diamond separately, and if you can show me why that price is not fair, I will raise my bid. But don't talk to me about no Linear Programs, Louie, like you did last time because that stuff gives me a headache and I get trigger-happy when I get a headache and you don't want me getting trigger-happy because I got a loaded gun in my pocket. And look where all the LPs got those finance guys on Wall Street.

Narrator: Ok, so now Louie can't show the LP solution to Tony and ask for $22.5. He has to find other ways of explaining why an offer is not good.

Louie (after thinking for a few seconds): I love negotiating. Fire away, Chief. But don't forget to also quote me a price per pound for my knapsack. And I have taken MS&E 111 so I name my quantities. So give me y₁, y_2, y₃, y₄ as the price for the gold, diamond, silver, and for each pound of my knapsack capacity.

Tony: Don't talk to me about no y's, Louie. I will give you $2 for the gold, $10 for the diamond, $1 for the silver, and $2 for each pound of your knapsack.

Louie: Get real, Boss. I can use the diamonds and three pounds of my knapsack capacity to carry all the diamonds. I will make $20 and you are only offering me y₂ + 3y₄ = $16. Make another offer, Boss.

Narrator: So what Louie is really saying is that for her to accept an offer, y₂ + 3y₄ must be at least 20. Wow, a linear constraint.

Tony: Well, I may not know LPs. but I know for sure that my goal is to minimize y₁ + y₂ + y₃ + 4y₄ . Jeez, you got me talking y's now Louie. You trying to ruin my reputation, eh, Louie?

Narrator: Ok, so now Tony has a linear objective function! The plot thickens. Now we will go around the class and people will play the part of Tony and Louie, making offers. And we will see whether we can get more constraints from Louie like the one that we already wrote down. Make some lowball offers, folks!