The Monkey climbed up the hill as quick as she could. Sun was shining high in the sky and she was late, as always, at The Tea Time. The tea room was at the top of the hill, hidden by thick trees. Few more steps and The Monkey opened the glass door of the entrance, which bounced noisily against the wall. The Elephant lazily turned his head towards the door to look at the cause of such bustle and smiled looking at The Monkey.

Elephant: Finally! You are here.
Monkey: Hi Elephant, sorry for the delay. I had to chase a couple of squirrels who stole my nuts. They found my reservoir for special occasions and emptied it in just one night. I found the squirrels but not the nuts.
E: They must be very smart squirrels to steal to a monkey.
M: I only know that they are vicious creatures! What do I do now?
E: Just go in the forest and collect again the nuts.
M: Not so simple.
E: What do you mean?
M: They emptied my full nuts storage and soon my family is coming to visit me. Monkeys' families are very big and they eat a lot of nuts to have enough energy to jump through the trees. In my reservoir, I had cashew, hazelnuts, walnuts, almonds, peanuts, pistachios, macadamia nuts, and many more, all necessary for a healthy monkey's diet. It took me a lot of time to collect all these nuts and I don't have enough time to recollect all of them.
E: I see, I might help you but now relax and eat the chocolate éclair that has been waiting for you.
M: Oh wow, a whole éclair! You have not eaten all of them.
E: Sure not, we decided to come here for the éclairs, and here we are.
M: Gnam! It is the best éclair in the world!
E: I agree with you. I had 38 of them while waiting for you.
M: 38!!! Really?
E: Incredible, isn't it? Only 38.... sometimes we have to do sacrifices: I'm on diet.
M: Well, I am very happy with mine. You said you are gonna help me. How do you think to do? Every time we go collect nuts together, I have seen more than half disappearing before reaching home. What will you do this time? Will you do the inverse magic, by making appearing the double of them?
E: Nothing similar. I won't come to help you to collect nuts but I can tell of you how to minimize the collecting time so you will have enough nuts before your family arrives. And indeed, it involves some "inverse magic".
M: I don't know why, but I'm not surprised that your help is just words? What would you tell me? To collect faster? To collect day and night?
E: Not at all. Collect using duality.
M: What's that?
E: It is a fascinating mathematical theory.
M: It does not sound useful.
E: It will. But first I need some extra information. What do you exactly need for a healthy monkey's diet?
M: I told you: many nuts!
E: I mean, which nutrients are needed to monkeys?
M: I don't know. I am just an eating nuts monkey.
E: No problem. Let's look what the Academic Of Monkey Nutrition says about it on Elephaninet. Here it is a table for the daily monkey nutritional needs.
E: We can see in the table that on average, an adult monkey needs no more than 7mg of salt and at least of 3g of fat and 6g of sugar to have enough energy to tease elephants.
M: First, I disagree with the fact that we tease! We love to play, that's all. And second, this table is not about nuts.
E: No, but we can transform this table into nuts. Which nuts do you want to collect?
M: Near to my home tree there is are two plants fill of sweetnuts and fattynuts. I don't have time to look for other nuts, I will just stick with those.
E: I have found on Elephaninet the nutritional information about sweetnuts and fattynuts.
E: I only need two more pieces of final information and I can elaborate the answer for you. How many nuts do you collect in one hour?
M: Mmmm. Ok, in one hour I can collect 30 fattynuts but only 10 of sweetnuts!
E: Final question. How many monkeys there are in your family and for how long do they stay with you.
M: These are two questions, not one. Anyway, including me, we are 10 and they will visit me for the weekend, so 2 days.
E: Ok. Great! Now we can start to talk about Linear Programming.
M: Linear Programming? You were not saying that it was about Duality? Have you already changed your mind?
E: Not at all. Duality is a principle that we can apply to Linear Programming. You will see soon, but first, we need to talk about Linear Programming. In Linear Programming, we want to find the solution of a minimization or maximization problem that can be described by some linear functions. Too difficult? I'll explain you better: your objective, actually, our objective, is to minimize the time to collect all the nuts. You told me that it takes 3 times more to collect sweetnuts than fattynuts. We can write this two information in this way: $$\min \textrm{ collecting time} = \frac{\textrm{1 hours}}{\textrm{10}} \textrm{sweetnuts} + \frac{\textrm{1 hours}}{\textrm{30}} \textrm{fattynuts}$$ Knowing that it is much faster to collect fattynuts, if we would not have any other information, we will just collect only fattynuts. But how many of them? From the monkey nutritional table, we know what each monkey needs each day no more than 7mg of salt. We know that 10 sweetnuts have 8mg in total, and 10 fattynuts 9mg. We can write it down like: $$\frac{\textrm{8 mg}}{\textrm{10}} \textrm{sweetnuts} + \frac{\textrm{9 mg}}{\textrm{10}} \textrm{fattynuts} \leq \textrm{7 mg x } \textrm{10 monkeys x } \textrm{2 days}$$ Shortly, we can write it: $$\textrm{8 sweetnuts} + \textrm{9 fattynuts} \leq (7 \textrm{ x } 10 \textrm{ x } 10 \textrm{ x } 2)$$ $$\textrm{8 sweetnuts} + \textrm{9 fattynuts} \leq 1400$$ We can represent this information, a constraint, in a space in which the variables are the nuts, the decision variables. They are called this way because we will take at the end a decision about how many nuts we need to collect. The green region is the forbidden region defined by the salt amount constraint. Any number of nuts in the white space, the feasible region, corresponds to the nuts we need.

M: I knew you wanted to propose a lazy idea! Look, the point that corresponds to 0 sweetnuts and 0 fattynuts is in the feasible region. Collect no nuts: this is an elephant solution. Your system does not work: monkeys won't be happy with no nuts.

E: Wait, I haven't finished yet with my solution. We have to add two more constraints. The first is that each monkey needs at least 3g of fat per day, and 10 sweetnuts have 2g of fat, while 10 fattynuts 15g. Fattynuts are really fat. We can write it like that, keeping into account that we have to feed 10 monkeys per 2 days: $$\textrm{2 sweetnuts} + \textrm{15 fattynuts} \geq 600$$ See? Now the feasible region has shrunk and the lazy solution has disappeared.

Let's also add the last condition: each monkey needs 6g of sugar per day. Sweetnuts have 20g of sugar per 10 nuts and fattynuts only 3g. For a total of 10 monkeys for 2 days: $$\textrm{20 sweetnuts} + \textrm{3 fattynuts} \geq 1200$$ Now, if you see, the feasible region is very small and the solution, or better, the optimal solution is hidden there.

All points in the white space are solutions to your problem, but only one, the optimal solution, minimizes the objective function, aka the time to collect the nuts. Where do you think it is?
M: In the middle of the white region!
E: Not exactly. If the optimal solution exists, it is on the edges.
M: What do you mean "if the optimal solution exists"? Is it another elephant way for not working?
E: In this case, the optimal solution exists and it's unique, but sometimes with constraints, it is not always guaranteed that we can find it. You know, when you have impossible constraints like sleeping at least 8 hours and go to work early. It is impossible: one condition excludes the other one. Sometimes, we can have multiple optimal solutions, for examples when I have to decide how many éclairs to eat and how many milkshakes to drink: one doesn't exclude the other!
M: I'm not convinced at all by your examples.
E: They are very good and mathematical correct examples!
M: If you insist...but where is this optimal point?
E: We have to solve iteratively the system of equations we have written so far until we find a combination of nuts to which corresponds the smallest collecting time possible. I have written a code doing that on my computer so while you were eating your éclair, I run it and got the optimal result for you.
M: Can I see it?
E: Yes, you can click here to see it.
M: Wow, and how many nuts we have to collect?
E: You have to collect 55 sweetnuts and 33 fattynuts. Look, as I told you before, the optimal solution is on the edge of the feasible region.

M: Me? You told you would help me!
E: I helped you by finding how to minimize the collecting time. That for 55 sweetnuts and 33 fattynuts corresponds to a bit less than 20 hours. Better if you start now.
M: I feel duped. And the duality? You have just spoken about Linear Programming.
E: You're right. Duality is a property of Linear Problems. Each constraint linear problem, like the one we have just solved, has a dual problem. If you can solve the dual problem, you have also solved the initial problem or primal problem. And vice versa. Sometimes, it's easier to convert the primal problem into its dual and solve that instead of solving directly the primal problem. What is interesting it's that, sometimes, dual problems have a real-word interpretation: they are not just a mathematical expedient but they are real.
M: How do I find the dual problem of the nuts?
E: Very easy. Minimization becomes maximization. The decision variables become the constraints and vice versa. The two kinds of nuts are the decision variables of the nuts problem, while the nutrients (salt, fat and sugar) are the constraints. In the dual problem, the situation is inverted. We want to maximise something while taking decisions on salt, fat and sugar.
M: I don't understand.
E: I'll give you the interpretation of the dual problem to make you understand better. Let's assume, for example, that someone, an elephant, decides to open a shop and sell to monkeys salt, oil, and sugar. The elephant, who's very smart, wants to maximize the revenue. For doing that, he needs to choose the price for each item, keeping in mind that monkeys will buy from him, only if salt, oil (fat) and sugar are cheaper or equal costs to the nuts they find in nature. How much is paid a monkey for one hour or nuts collection?
M: Enough to buy 3 éclairs!
E: So, if we know that in one hour a monkey can collect 10 fattynuts, we can say that the price of 10 fattynuts is 3 éclairs. Similarly, we can do for the sweetnuts. At this point, the elephant can decide the price of salt, oil and sugar by imposing that their total cost has to be less or equal to the cost of the same amount within the two nuts and by maximizing the total éclairs revenue.
M: It's interesting that you're telling me that now: this morning a lot of my monkey friends have bought a lot of food from a new shop, paying in éclairs!
E: Yes. The total revenue of the day was 39 éclairs. The optimal solution.