Duality and Shadow Prices
The dual LP prices the primal model's constraints. It supplies bounds and local sensitivity information, but a shadow price is not a market price, causal effect, or universal value.
Prerequisites
Complete linear-programming model patterns.
Learning goals
- Write the dual of the allocation maximization LP.
- Verify weak and strong duality numerically.
- Convert SciPy minimization marginals to the maximization interpretation.
- State shadow-price units and the conditions under which they apply.
From resources to a dual bound
For the primal subject to and , the dual is
Here has benefit points per staff-hour and benefit points per room-hour:
Any dual-feasible prices every batch highly enough, so bounds every primal-feasible benefit from above. At the bound is 200, equal to the primal value: strong duality holds.
SciPy solves the negated minimization objective. Its inequality marginal is the derivative of the minimized objective with respect to the right-hand side, so the reported values are negative here. Negating them yields the local shadow price of capacity for the original maximization.
Worked example
import numpy as np
from scipy.optimize import linprog
benefit = np.array([8.0, 6.0])
A = np.array([[2.0, 1.0], [1.0, 2.0]])
b = np.array([40.0, 50.0])
primal = linprog(-benefit, A_ub=A, b_ub=b,
bounds=[(0.0, None)] * 2, method="highs")
dual = linprog(b, A_ub=-A.T, b_ub=-benefit,
bounds=[(0.0, None)] * 2, method="highs")
if primal.status != 0 or dual.status != 0:
raise RuntimeError("expected optimal primal and dual")
shadow = -primal.ineqlin.marginals
print(f"primal_points={-primal.fun:.3f} dual_points={dual.fun:.3f} duality_gap={dual.fun + primal.fun:.3e}")
print(f"shadow_price_staff_points_per_hour={shadow[0]:.6f}")
print(f"shadow_price_room_points_per_hour={shadow[1]:.6f} sign_converted_from_minimization=True")
Expected output:
primal_points=200.000 dual_points=200.000 duality_gap=0.000e+00
shadow_price_staff_points_per_hour=3.333333
shadow_price_room_points_per_hour=1.333333 sign_converted_from_minimization=True
One extra staff-hour increases the optimal modeled benefit by about points only while the active set remains unchanged. It says nothing directly about the acquisition cost of labor or realized learner outcomes.
Limitations and common mistakes
- Always document the primal form and solver sign convention before interpreting marginals.
- A zero shadow price can arise from slack or degeneracy; it does not prove a resource has no real value.
- Dual solutions may be nonunique even when the primal objective is unique.
- Shadow prices are local to coefficient values, bounds, and the current right-hand side.
- Strong duality certifies the encoded convex program, not data accuracy, causality, fairness, or real-world validity.
Practice
Use the two shadow prices to predict the modeled value of one additional hour of each resource. Re-solve both perturbations, compare the change, and name the units in every calculation.
Next steps
Find where that local interpretation stops working in sensitivity and scenario analysis.
Primary sources
Checked 2026-10-18: Boyd and Vandenberghe, Convex Optimization, chapter 5 and updated duality slides; SciPy 1.18.1, linprog marginal convention; Stanford EE364A, duality notes.