Understanding Duality in Linear Programming: A Simple Guide

Linear Programming (LP) is a mathematical technique used to optimize a certain objective, like maximizing profit or minimizing cost, given some constraints. However, every LP problem has a hidden twin—called the dual problem—which provides valuable insights into the original problem.

What is Duality?

For every Linear Programming problem, known as the Primal problem, there is a corresponding Dual problem. These two problems are linked, and solving one gives important information about the other.

Think of it like this:
Imagine a company that makes wooden tables and chairs. The Primal problem might be:
“How many tables and chairs should we produce to maximize profit, given our limited wood and labor?”

The Dual problem, on the other hand, asks:
“What is the fair price we should assign to each unit of wood and labor so that we can determine the true value of these resources?”

Both problems are looking at the same situation, but from different perspectives—one from production, the other from resource valuation.

Primal vs. Dual: A Quick Overview

Here’s a structured comparison:

Feature	Primal Problem	Dual Problem
Objective	Maximize or Minimize	Minimize or Maximize
Variables	Decision variables (e.g., how many tables/chairs to produce)	Shadow prices (e.g., cost of resources)
Constraints	Limits on resources	Constraints on resource pricing

If the Primal is a Maximization problem, the Dual will be a Minimization problem, and vice versa.

Example: A Simple Linear Programming Problem

Let’s say a furniture company makes Tables (T) and Chairs (C) to maximize profit.

• Each Table gives $50 profit
• Each Chair gives $30 profit
• Each item requires wood and labor, but both resources are limited.

Primal Problem (Maximization)

$$\text{Maximize }Z=50T+30C$$

Subject to:

1. Wood constraint: $5T+3C\le 120$ (Wood available: 120 units)
2. Labor constraint: $2T+2C\le 50$ (Labor available: 50 hours)
3. $T,C\ge 0$ (Can’t produce negative items)

Dual Problem (Minimization)

Instead of focusing on the number of tables and chairs, the Dual problem asks:
“What should be the value of each unit of wood and labor to minimize cost?”

Let W = price per unit of wood
Let L = price per unit of labor

$$\text{Minimize }Z=120W+50L$$

Subject to:

1. Profit per Table: $5W+2L\ge 50$ (Cost must justify selling price)
2. Profit per Chair: $3W+2L\ge 30$
3. $W,L\ge 0$

Key Takeaways from Duality

1. The Optimal Values of the Dual = The Shadow Prices

   • If the company solves the dual problem, the values of $W$ and $L$ tell them how much extra wood or labor is worth.

2. Strong Duality Theorem

   • If an optimal solution exists for both Primal and Dual, their objective function values are equal.
   • That is, if the maximum profit in the Primal is $X, then the minimum cost in the Dual is also $X.

3. Economic Interpretation

   • If a constraint is not binding (i.e., we have extra resources), its dual variable will be zero.
   • If a resource is scarce, its dual variable will be positive, meaning it has value.

Why Duality is Important

• Business Decisions: Helps companies decide how much they should be willing to pay for additional resources.
• Sensitivity Analysis: Shows the impact of changing constraints (e.g., what happens if we get more labor?).
• Computational Efficiency: Sometimes solving the Dual is easier than solving the Primal.

Final Thoughts

Duality is like looking at a problem from two sides of the same coin. If you understand one, you can learn a lot about the other. It’s a powerful concept in optimization, used in economics, supply chain management, finance, and engineering.

Next time you see an LP problem, try formulating its Dual—it might just give you the insights you need!

Photo by Christina Morillo: https://www.pexels.com/photo/close-up-photo-of-person-typing-on-laptop-1181675/