∇ProvenDecisions
Ctrl K

How to know your linear program's answer is really the best (a product-mix example in Python)

Articles · 2026-11-20

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

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):

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

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: