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 + 2b dollars, 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:

  1. 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.
  2. 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