It was a crisp morning in Paris, and the bustling sounds of the city filtered into Hydra’s patisserie. As she prepped trays of croissants and pain au chocolat, a sharp knock interrupted her routine. Standing in the doorway was François, the resource broker, with his usual ledger in hand and an expression that promised numbers and negotiations.

François stepped in, the scent of warm butter filling the shop. “Hydra, I see you’ve been busy. But let’s talk business. How are you planning your production this week?”

Hydra wiped her hands on her apron. “It’s always a balancing act. I have orders piling up, but resources are tight—especially flour and butter. And then there’s oven time to consider.”

François nodded knowingly. “Let’s be more strategic. You have limited resources—flour, butter, and oven time. Instead of just making pastries, let’s aim to maximize your profit.”

The Primal Problem: Maximizing Profit

Hydra nodded, pulling out her records. Together, they modeled the problem using the bakery’s real data. Hydra’s bakery specializes in five exquisite pastries: Croissant, Pain au Chocolat, Éclair au Chocolat, Tarte aux Fraises, and Macarons.

Each pastry requires a mix of three limited resources: flour, butter, and oven time. François opened his ledger and presented the constraints:

• Flour: 20 kg available

• Butter: 15 kg available

• Oven time: 20 hours available

The profit for each pastry was:

• Croissant: €4

• Pain au Chocolat: €5

• Éclair au Chocolat: €6

• Tarte aux Fraises: €8

• Macaron: €3

Hydra needed a plan. The question she wanted to answer was: how many of each pastry should she bake to maximize her profit, given her limited resources of butter, flour, and oven time?

Her goal was to maximize her profit within the limits of her resources. Mathematically, this is expressed as:

Primal Model

François leaned over the numbers. “This is your primal model. It tells you how to allocate resources to maximize profit.”

The Dual Model: The Value of Resources

Now that we have the primal model in place, let’s flip the perspective and see how we can interpret the value of the resources. In optimization, this is where the dual model comes in.

Imagine you are trying to buy as many pastries as possible with a limited budget. You could either think about how much profit you can make from each pastry (this is the primal problem) or how much you are willing to pay for each resource (flour, butter, etc.) to make those pastries (this is the dual problem). Both perspectives lead you to the same conclusion, just from different angles.

The primal and dual problems are intricately linked:

1. Constraints in the primal problem (represented by the vector b) become the objective function coefficients in the dual problem.

2. Objective function coefficients in the primal (represented by c) transform into the constraints in the dual.

Source:

In Hydra's case and using her resource allocation primal formulation, the dual formulation becomes:

Dual Model

Interpreting the Dual

The shadow prices y1, y2, and y3 represent the true economic value of the resources—flour, butter, and oven time—respectively.

If the shadow price for flour (y1) is 2€, this means that every additional kilogram of flour would increase Hydra's profit by 2€. Resources with a shadow price of €0, like oven time, indicate they are not being fully utilized in the optimal solution. This means that increasing the amount of oven time wouldn't increase Hydra's profit, so it isn't the bottleneck in her production process.

Weak vs. Strong Duality: Two Sides, Same Coin

François smiled as he explained. "The primal and dual are like two sides of the same coin. The primal problem shows you the best pastries to bake for the highest profit. The dual tells you the value of your resources and why some are more important than others." He gave Hydra an analogy to make duality easier to understand:

• Weak Duality: Think of it like shopping for ingredients with a budget. Weak duality ensures that the total cost of ingredients (the dual) will never be more than the money you make from selling pastries (the primal). In other words, it guarantees that the economic value of the ingredients you buy won’t exceed the profit you can earn from using them. This keeps things balanced and realistic.

• Strong Duality: Now, imagine you’re at the store, and you’ve got the perfect balance between what you need and what you can afford. Strong duality says that when both your bakery’s plan (primal) and the cost of ingredients (dual) are perfectly optimized, the total economic value of the ingredients will exactly match the profit from selling the pastries. It’s like hitting the sweet spot where everything aligns.

Together, weak and strong duality show that the primal and dual are two sides of the same coin: one tells you how to use your resources to make the most profit, and the other shows the true economic value of those resources.

The Optimal Solution

After crunching the numbers, Hydra found her optimal production plan:

• 100 Croissants

• 50 Pain au Chocolat

• No Éclairs, Tarts, or Macarons

This solution maximized profits while fully utilizing flour and butter. Oven time, however, had leftover capacity, confirming its shadow price of €0.

François pointed out: “See how your butter was the bottleneck? That’s where your operation hinges.”

Conclusion: The Power of Duality

Hydra surveyed her trays of pastries, each one not only a product of her baking skill but also a testament to the power of optimization. The primal and dual models had transformed the way she viewed her bakery—from simply crafting delicious treats to strategically managing her resources for maximum profit. Duality in optimization isn’t just about solving equations; it reveals the deeper story of how scarcity and value intertwine, giving new meaning to each kilogram of flour and minute of oven time.

This concludes the Hydra series, where we navigated the complexities of optimization through the lens of a Parisian bakery. By balancing profits, resources, and time, Hydra’s journey showed how optimization can bring precision and insight into everyday decisions. Whether you’re in a bakery or a boardroom, the principles of duality can help you see beyond the numbers and unlock new efficiencies.