Skip to main content

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 max⁡cTx\max c^Tx subject to Ax≤bAx\le b and x≥0x\ge0, the dual is

min⁡y≥0bTysubject toATy≥c.\min_{y\ge0} b^Ty\quad\text{subject to}\quad A^Ty\ge c.

Here ySy_S has benefit points per staff-hour and yRy_R benefit points per room-hour:

min⁡40yS+50yRs.t. 2yS+yR≥8,  yS+2yR≥6,  y≥0.\min 40y_S+50y_R\quad \text{s.t. }2y_S+y_R\ge8,\;y_S+2y_R\ge6,\;y\ge0.

Any dual-feasible yy prices every batch highly enough, so bTyb^Ty bounds every primal-feasible benefit from above. At y=(10/3,4/3)y=(10/3,4/3) 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 10/310/3 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.