Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 38 · Duality and Sensitivity

Shadow Prices and Sensitivity Analysis

Learn shadow prices, reduced costs and sensitivity ranges for objective coefficients and right-hand sides, computed from the optimal basis in Python and verified by re-solving.

An optimal solution answers "what should we do?", but a manager immediately asks "what if the data are wrong?" and "what is more capacity worth?". Sensitivity analysis (also called post-optimality analysis) answers such questions without re-solving from scratch, using information that the final simplex basis already contains. This lesson covers the four classic outputs: shadow prices, reduced costs, right-hand-side ranging and objective-coefficient ranging.

We use the bakery model with optimal basis {x, y, s3} (bread, cakes and flour slack), optimum (20, 60) and profit 2600.

Shadow prices (dual values)

The shadow price of a constraint is the change in the optimal objective value per unit increase of its right-hand side, as long as the optimal basis does not change. It is the dual variable y_i:

d(optimal value) / d(b_i) = y_i

For the bakery: oven 10, labor 20, flour 0. One more oven hour is worth 10 dollars, one more labor hour 20 dollars, and extra flour nothing. Compare shadow prices with market prices: if an extra oven hour can be bought for less than 10 dollars, buy it; if labor costs 25 per hour you should not hire more.

Python Verify shadow prices by re-solving

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reduced costs

The reduced cost of a variable that is not in the optimal plan (value 0) says how much its profit coefficient would have to improve before it becomes attractive. Equivalently, it is the loss in profit per unit if you force one unit of that variable into the plan. Formally, reduced cost_j = a_j . y - c_j for a maximization. Variables in the basis have reduced cost 0.

Suppose the bakery considers a new product, a pie, using 1 oven hour, 2 labor hours and 1 unit of flour, earning 45 dollars. Its resource value is 1*10 + 2*20 + 1*0 = 50, which is more than 45 dollars of profit, so the pie is not worth making: pricing out a new product is just evaluating a . y - c.

Python Price out a new product

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Right-hand-side ranging

Shadow prices hold only over a range of right-hand-side values, the interval where the current basis stays feasible. Outside it, a different set of constraints binds and the price changes (typically drops, because of diminishing returns).

If the optimal basis matrix is B (columns of the final basis in the standard-form A), the basic variables are x_B = B⁻¹ b. Changing b_i to b_i + t gives x_B(t) = B⁻¹ b + t B⁻¹ e_i. The basis stays feasible while every component is >= 0, so we solve t from B⁻¹ b + t B⁻¹ e_i >= 0.

Python Range for each right-hand side

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The oven price of 10 per hour holds for oven availabilities from 80 to 120 hours. Beyond 120 the flour limit (40 bread batches) caps bread production, so extra oven time stops helping. The flour constraint (price 0) matters only if flour drops below 20 units, where it starts to bind.

Objective-coefficient ranging

How much can a profit coefficient change before the optimal plan (not the profit) changes? The plan stays optimal as long as all reduced costs keep their signs. For the bakery, the dual constraints at the current basis give y1 = c_x - 30 and y2 = 60 - c_x (from 2y1 + y2 = c_x and y1 + y2 = 30). Both must stay >= 0, so the plan (20, 60) stays optimal for the bread profit between 30 and 60 dollars. Below 30 the optimum jumps toward cakes; above 60 it jumps toward bread. The profit itself still changes inside the range (it is c_x * 20 + 1800), only the plan stays.

Python Check the profit range by re-solving

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The plan (20, 60) appears for bread profits between 30 and 60. Exactly at 30 and 60 there are alternative optima (ties with the neighbouring plan), because a reduced cost equals zero there, and the solver may report either one.

What solver output looks like

Solvers print a sensitivity report with the same quantities:

Item Meaning
Dual value / shadow price Marginal value of a constraint's right-hand side
Reduced cost Penalty for forcing a non-basic variable into the plan
RHS allowable increase / decrease The ranges computed above
Objective allowable increase / decrease The profit-coefficient ranges

SciPy exposes duals (res.ineqlin.marginals) and reduced costs (res.lower.marginals) but not the ranges; the basis calculations above fill the gap, or you can scan with repeated solves as a sanity check.

Three cautions

  1. Shadow prices are marginal. They are valid for small changes within the range, not for doubling a resource.
  2. Degenerate solutions have several valid dual answers. Ranges and prices can differ between solvers, so interpret them with care.
  3. Sensitivity is not uncertainty. It varies one parameter at a time. For simultaneous changes in many coefficients, use scenario analysis, or robust and stochastic programming (beyond this course).

Always report sensitivity results in business terms: "Each extra labor hour is worth 20 dollars up to 100 total hours; beyond that, nothing", not "the dual variable is 20".

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. The shadow price of labor is 20. If one extra labor hour is available (within the range), the optimal profit

    The shadow price is the marginal change in the optimal value per unit of right-hand side.
  2. 2. A product has resource value (a_j . y) greater than its profit. Should it be produced?

    If the implicit value of the resources exceeds the profit, producing it destroys value.
  3. 3. Why do shadow prices only hold over a range?

    The dual price is the slope of the optimal value function, which is piecewise linear and changes slope when the basis changes.
  4. 4. Objective-coefficient ranging tells you

    Within the range, the same vertex remains optimal even though the profit value changes.

Summary

  • Shadow price = dual value = marginal profit per extra unit of a binding resource.
  • Reduced cost tells how much a non-basic variable's profit must improve to enter the plan; price out new products with a . y - c.
  • RHS ranging uses B⁻¹ b + t B⁻¹ e_i >= 0 to find where a shadow price stays valid.
  • Cost ranging keeps the reduced costs' signs; the plan stays optimal inside the range.
  • Sensitivity is one-at-a-time and marginal; use scenarios for large or simultaneous changes.

Next: Integer Programming Basics