Two-stage supply chain: a linear programming example, solved and checked
The two-stage supply chain is a classic linear programming problem. Here it is solved by a real solver (HIGHS) and checked: every constraint, the dual, and the optimality certificate. Change the numbers below and solve your own.
Solve your own version free, no account needed
The problem
A factory makes up to 80 units at $5 each. Units go to warehouses W1 or W2 ($2 and $3 per unit), then to a store that needs 50 units ($4 from W1, $1 from W2). Each warehouse handles at most 40 units. Minimize total cost.
How the model was built
The objective as written from the problem, before the numbers are multiplied out:
- p is the number of units made; f1 and f2 are the units sent from the factory to W1 and W2; s1 and s2 are the units sent from W1 and W2 to the store.
- f1 + f2 = p: everything made goes to a warehouse. s1 = f1 and s2 = f2: each warehouse sends on what it receives. s1 + s2 ≥ 50: the store gets at least its 50 units.
- Cost: $5 a unit to make, then $2 or $3 to a warehouse, then $4 or $1 to the store. Through W1 a unit costs $2 + $4 = $6 to move; through W2, $3 + $1 = $4.
The model
Each line has a plain-language note on the right.
| make this as small as possible | |
| units produced at the factory (units) is at most 80 | |
| limit 2: left side must equal the right side | |
| limit 3: left side must reach at least 50 | |
| limit 4: left side must equal the right side | |
| limit 5: left side must equal the right side | |
| units shipped from factory to warehouse W1 (units) is at most 40 | |
| units shipped from factory to warehouse W2 (units) is at most 40 | |
| units produced at the factory (units) cannot be negative | |
| units shipped from factory to warehouse W1 (units) cannot be negative | |
| units shipped from factory to warehouse W2 (units) cannot be negative | |
| units shipped from W1 to the store (units) cannot be negative | |
| units shipped from W2 to the store (units) cannot be negative |
In matrix form
With its numbers:
What is being decided
There are 5 decision variables.
| Variable | Type | Meaning |
|---|---|---|
| p | real number | units produced at the factory (units) |
| f1 | real number | units shipped from factory to warehouse W1 (units) |
| f2 | real number | units shipped from factory to warehouse W2 (units) |
| s1 | real number | units shipped from W1 to the store (units) |
| s2 | real number | units shipped from W2 to the store (units) |
Goal and limits
Minimize the objective subject to 12 constraints, of which 8 are simple bounds on a single variable.
Problem type
LP, complexity level 2: a linear program. Solved with HIGHS at the Medium solver tier.
The answer at a glance
The optimal value of each decision, as the solver returned it.
Which constraints hold the answer in place
Binding (no slack left): (2) f1 + f2 = p; (3) s1 + s2 >= 50; (4) s1 = f1; (5) s2 = f2; (7) f2 <= 40. Changing a binding constraint changes the answer; a slack one can move a little without effect.
| # | Constraint | Value | Limit | Slack | Binding |
|---|---|---|---|---|---|
| 1 | p <= 80 | 50 | 80 | 30 | |
| 2 | f1 + f2 = p | 50 | 50 | 0 | yes |
| 3 | s1 + s2 >= 50 | 50 | 50 | 0 | yes |
| 4 | s1 = f1 | 10 | 10 | 0 | yes |
| 5 | s2 = f2 | 40 | 40 | 0 | yes |
| 6 | f1 <= 40 | 10 | 40 | 30 | |
| 7 | f2 <= 40 | 40 | 40 | 0 | yes |
| 8 | p >= 0 | 50 | 0 | 50 | |
| 9 | f1 >= 0 | 10 | 0 | 10 | |
| 10 | f2 >= 0 | 40 | 0 | 40 | |
| 11 | s1 >= 0 | 10 | 0 | 10 | |
| 12 | s2 >= 0 | 40 | 0 | 40 |
Why this is optimal
A proof you can check by hand. Multiply each constraint in the table by its weight and add them up: the result is a lower limit on the objective that holds for every plan meeting the constraints. Our answer reaches that limit exactly, so no plan does better. A negative weight turns a limit around (for example ≥ into ≤) before adding. Every step was checked in exact fractions, not rounded decimals.
| # | Constraint | Weight |
|---|---|---|
| 2 | f1 + f2 = p | -5 |
| 3 | s1 + s2 ≥ 50 | 11 |
| 4 | s1 = f1 | -7 |
| 5 | s2 = f2 | -10 |
| 7 | f2 ≤ 40 | -2 |
Algebraic model (low level)
Decision variables, objective and every constraint written out; this is exactly what the solver receives.
Standard form
As a linear program: minimize cᵀx subject to A x ≤ b (the inequality rows) and A_eq x = b_eq (the equations); a maximization is written as minimizing the negative.
Model code (cvxpy)
The same model in cvxpy, ready to run.
import cvxpy as cp
p = cp.Variable(name='p') # units produced at the factory (units)
f1 = cp.Variable(name='f1') # units shipped from factory to warehouse W1 (units)
f2 = cp.Variable(name='f2') # units shipped from factory to warehouse W2 (units)
s1 = cp.Variable(name='s1') # units shipped from W1 to the store (units)
s2 = cp.Variable(name='s2') # units shipped from W2 to the store (units)
objective = cp.Minimize(2*f1 + 3*f2 + 5*p + 4*s1 + s2)
constraints = [
p <= 80,
f1 + f2 == p,
s1 + s2 >= 50,
s1 == f1,
s2 == f2,
f1 <= 40,
f2 <= 40,
p >= 0,
f1 >= 0,
f2 >= 0,
s1 >= 0,
s2 >= 0,
]
problem = cp.Problem(objective, constraints)
problem.solve(solver='HIGHS')
print(problem.status, problem.value)
print('p =', p.value)
print('f1 =', f1.value)
print('f2 =', f2.value)
print('s1 =', s1.value)
print('s2 =', s2.value)The dual problem
Every constraint of the original (primal) problem gets a price, and every primal variable becomes a constraint on those prices. Strong duality: primal and dual optima are equal (470).
| Dual variable | Prices | Value |
|---|---|---|
| y1 | price of constraint 'p <= 80' (objective change per extra unit of its right-hand side) | 0 |
| y2 | price of constraint 'f1 + f2 = p' (objective change per extra unit of its right-hand side) | -5 |
| y3 | price of constraint 's1 + s2 >= 50' (objective change per extra unit of its right-hand side) | 11 |
| y4 | price of constraint 's1 = f1' (objective change per extra unit of its right-hand side) | -7 |
| y5 | price of constraint 's2 = f2' (objective change per extra unit of its right-hand side) | -10 |
| y6 | price of constraint 'f1 <= 40' (objective change per extra unit of its right-hand side) | 0 |
| y7 | price of constraint 'f2 <= 40' (objective change per extra unit of its right-hand side) | -2 |
Solve your own
This is the model as the app reads it. Change any number and solve it in the free box on the front page (no account needed).
minimize 5*p + 2*f1 + 3*f2 + 4*s1 + 1*s2
subject to
p <= 80
f1 + f2 = p
s1 + s2 >= 50
s1 = f1
s2 = f2
f1 <= 40
f2 <= 40
p, f1, f2, s1, s2 >= 0
# p = units produced at the factory (units)
# f1 = units shipped from factory to warehouse W1 (units)
# f2 = units shipped from factory to warehouse W2 (units)
# s1 = units shipped from W1 to the store (units)
# s2 = units shipped from W2 to the store (units)Checked: the app's answer matches the reference answer in our test set, which two solvers (HIGHS, CLARABEL) agree on. Built 2026-11-10.
Related examples
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.