A solver says "optimal". How do you know it is right, and that no better plan exists? For a linear program there is a short, checkable proof: the dual. Here it is on the smallest useful example.
The problem
A company makes two products, A and B.
| Labour (hours) | Raw material (units) | Profit ($) | |
|---|---|---|---|
| One A | 2 | 1 | 3 |
| One B | 1 | 2 | 2 |
| Available | 100 | 80 |
How many of each should it make to earn the most profit?
Step 1: the model in words, then in math
- Decisions:
a= units of A made,b= units of B made (both 0 or more). - Objective: total profit,
3a + 2bdollars, as large as possible. - Rules: labour used,
2a + b, is at most 100 hours; material used,a + 2b, is at most 80 units.
maximize 3a + 2b # profit ($) subject to 2a + b <= 100 # labour (hours) a + 2b <= 80 # raw material (units) a, b >= 0 # cannot make a negative amount Everything is linear, so this is a linear program (LP): the best answer is at a corner of the region the rules allow, and a solver can find it and prove it.
Step 2: solve it with cvxpy
import cvxpy as cp a = cp.Variable(nonneg=True) # units of product A b = cp.Variable(nonneg=True) # units of product B labour = 2*a + 1*b <= 100 # hours of labour material = 1*a + 2*b <= 80 # units of raw material prob = cp.Problem(cp.Maximize(3*a + 2*b), [labour, material]) prob.solve(solver=cp.HIGHS) print(prob.status, prob.value, a.value, b.value) print(labour.dual_value, material.dual_value) Output (cvxpy 1.9.3, HiGHS):
optimal 160.0 40.0 20.0 1.333333 0.333333 So: make 40 units of A and 20 units of B, for a profit of $160. Both rules are used to the limit: labour 2(40) + 20 = 100 hours, material 40 + 2(20) = 80 units.
Step 3: check it is feasible
Plug the answer back into every rule: 100 ≤ 100 hours ✓, 80 ≤ 80 units ✓, 40 ≥ 0 and 20 ≥ 0 ✓. Feasible means "allowed", not yet "best".
Step 4: prove it is the best, with the dual
The two numbers on the second line are the dual values (also called shadow prices):
- one more labour hour is worth $4/3 ≈ $1.33 of extra profit;
- one more unit of raw material is worth $1/3 ≈ $0.33.
They give a proof in two lines:
- They price every product at least at its profit. Product A uses 2 hours and 1 unit: 2(4/3) + 1(1/3) = 3 ≥ $3 ✓. Product B uses 1 hour and 2 units: 1(4/3) + 2(1/3) = 2 ≥ $2 ✓. So any plan's profit is at most the value of the resources it uses.
- So no plan can beat the value of all the resources: 100 hours × $4/3 + 80 units × $1/3 = $160.
Every feasible plan earns at most $160, and ours earns exactly $160. That is optimal, with no trust in the solver required: anyone can redo the arithmetic. This is weak duality (dual value ≥ any profit) closing with strong duality (they meet, gap 0).
You can check it by hand too: the corners of the allowed region are (0, 0) → $0, (50, 0) → $150, (0, 40) → $80 and (40, 20) → $160.
What the dual tells a manager
The shadow prices are useful on their own: if someone offers an extra labour hour for less than $1.33, take it; raw material is worth only $0.33 a unit at the margin. (These values hold for small changes, until another rule starts to bind.)
The takeaway
For any LP, ask for three things, not one: the status (optimal, infeasible, unbounded), feasibility of every rule, and a dual certificate whose value matches the objective. If the gap is 0, the answer is proven.
This article was written with AI assistance; every number in it comes from the solver run shown above and was checked by hand.
I build ProvenDecisions, a web app that does these steps for you, from typed math, LaTeX, a photo or a spoken problem, and shows the dual check with every answer. This example is solved there: https://proven-decisions.ai/examples/product-mix?ref=devto
