Lesson 2: Shadow Prices and Reduced Costs

1 Modelling context

An LP solution tells the decision-maker what to do. The dual tells them what the constraints are costing. These two pieces of information answer different questions, and both are usually needed. A production manager who knows the optimal production plan also wants to know which resource constraints are actually limiting the plan, and what it would be worth to relax each.

This lesson develops the interpretation of the dual variables as shadow prices: the marginal value of relaxing a constraint. It also introduces the reduced costs of the primal variables, which have the parallel interpretation as opportunity costs. Together these are the primary decision-support output of an LP solution.

What is a shadow price?

A shadow price is the change in the optimal objective value per unit increase in the right-hand side of a constraint. If a constraint says "labour ≤ 100 hours" and its shadow price is $12 per hour, then having one additional hour of labour would increase the optimal profit by $12.

2 Learning objectives

By the end of this lesson you will be able to

Define the shadow price of a constraint.
Compute shadow prices from the dual solution or from the solver's sensitivity report.
Interpret shadow prices in decision-relevant terms.
Define the reduced cost of a variable and interpret it as an opportunity cost.
Identify which constraints are binding and which variables are basic in an optimal solution.
Use shadow prices to support a resource-acquisition decision.

3 Prerequisite review

Binding constraint: A constraint whose LHS equals its RHS at the optimum. Its slack is zero.
Slack: The difference b_i − (A x)_i at the optimal solution. Positive slack means the constraint is not binding.
Basic variable: A variable that is positive at the optimum. At a vertex of the feasible region, the number of positive variables equals the number of binding constraints (generically).
Dual variable: A variable of the dual LP. Its optimal value is the shadow price of the corresponding primal constraint.

4 Mathematical formulation

Shadow prices from the dual

Consider the standard-form primal-dual pair from Lesson 1:

Primal:  max  cᵀ x       Dual:  min  bᵀ y
         s.t. A x ≤ b            s.t. Aᵀ y ≥ c
              x ≥ 0                   y ≥ 0

The optimal dual variable y*_i is the shadow price of the i-th primal constraint. To see why, consider a small change δ in the right-hand side b_i. Let z*(b) be the optimal primal objective as a function of b. Then

y*_i = ∂ z* / ∂ b_i

That is, the shadow price is the rate at which the optimal objective changes as the constraint bound changes. This is exact when the change is small enough that the optimal basis does not change. Beyond that threshold, the shadow price itself changes, which is the subject of Lesson 3.

Sign of the shadow price

For a standard-form maximization problem with ≤ constraints and nonnegative right-hand sides:

y*_i > 0: relaxing the constraint (increasing b_i) increases the objective. The constraint is binding and limiting.
y*_i = 0: relaxing the constraint has no effect. The constraint is not binding.

Shadow prices are nonnegative for maximization problems. For minimization problems, the conventions may differ; check the sign convention of the software you are using.

Reduced costs

The reduced cost of a primal variable x_j is the amount by which the objective coefficient c_j would have to change before x_j enters the optimal solution. Equivalently, it is the rate at which the objective would change if x_j were forced to increase by one unit from zero.

At optimality:

If x_j > 0, its reduced cost is zero.
If x_j = 0, its reduced cost is typically positive for a maximization problem, indicating that the variable is "unattractive" at the current coefficient.

The reduced cost has the interpretation of an opportunity cost: it is what the objective would lose by forcing the variable into the solution at level 1, and therefore what the variable's objective coefficient would have to be to make it worth including.

Relationship to complementary slackness

Complementary slackness links shadow prices and reduced costs to the optimal solution:

Non-binding constraint → zero shadow price.
Positive shadow price → binding constraint.
Positive primal variable → zero reduced cost.
Positive reduced cost → zero primal variable.

These relationships are exact and can be used to check the solver's output.

Figure 6.6. The optimal objective value as a function of a constraint's right-hand side. The curve is piecewise-linear and concave. The slope of each segment is the shadow price of the constraint within the corresponding sensitivity range.

5 Worked example

Shadow prices and reduced costs for the production planning LP

Return to the LP from Lesson 1:

maximize   40 x_A + 30 x_B
subject to 2 x_A + x_B ≤ 100    (labour)
           x_A + 3 x_B ≤ 90     (material)
           x_A ≤ 40             (demand A)
           x_B ≤ 30             (demand B)
           x_A, x_B ≥ 0

Step 1 — Primal optimum.

From Unit 6.1: x_A = 40, x_B = 16.67, z* ≈ 2100.

Step 2 — Dual optimum (from Lesson 1).

(y_L, y_M, y_A, y_B) = (0, 10, 30, 0)

Step 3 — Shadow prices.

y_L = 0: the labour constraint has a shadow price of zero. Additional labour hours would not increase profit.
y_M = 10: each additional kilogram of material would increase profit by $10.
y_A = 30: each additional unit of demand for product A would increase profit by $30.
y_B = 0: the demand constraint for B has zero shadow price. Additional demand would not increase profit.

Step 4 — Reduced costs.

Both x_A and x_B are positive at the optimum, so both have reduced cost zero. This is a general property: variables that are in the optimal basis have zero reduced cost.

Step 5 — Decision implications.

If a supplier offers additional material at less than $10 per kilogram, purchasing it would improve profit.
If a customer is willing to pay for one more unit of demand for product A at a profit contribution of at least $30, relaxing the demand cap is worthwhile.
Additional labour has no value at the current plan. Hiring more workers would not improve profit unless something else changes.

Step 6 — Caveats.

These interpretations are valid only within the sensitivity ranges of the constraints. If we purchase substantially more material, the shadow price may change (Lesson 3). The single-unit interpretation is the correct one: each of the shadow prices describes the marginal value of one unit, within a range that must be checked.

6 Verification check

Checks to perform

Check complementary slackness. Every non-binding constraint should have a zero shadow price. Every positive shadow price should correspond to a binding constraint.
Check the sign convention. Confirm that the solver's sign convention for shadow prices matches the course convention. Different software packages differ.
Verify by direct experiment. Increase the RHS of a binding constraint by one unit, re-solve, and check that the objective changes by approximately the shadow price.
Check the reduced costs. Positive variables should have reduced cost zero. Zero variables should have reduced cost consistent with their objective coefficient and the current basis.
Test on a small instance by enumeration. For LPs with two variables, compute the optimum at each vertex and the shadow price of each constraint directly.
Check the units. The shadow price has units of "objective per unit of constraint." For a profit objective and a material constraint in kilograms, the shadow price is dollars per kilogram.

7 Interpretation

The shadow prices and reduced costs are the decision-relevant output of an LP solution. They convert the abstract solver output into actionable information about what a constraint is worth.

Three interpretive points:

Shadow prices are marginal, not average. The shadow price tells you what the next unit of a resource is worth, not the average value of all units consumed. This is why the interpretation applies to small changes.
Reduced costs identify opportunities for new products. A variable with positive reduced cost would become attractive if its objective coefficient increased by more than the reduced cost. This is useful for product-line planning.
Not all constraints are worth relaxing. A non-binding constraint has shadow price zero. Investing in relaxing it would not improve the objective.

Reporting shadow prices

A complete report of an LP solution includes the shadow price of each constraint, with its units and interpretation. For a decision-maker, this is often more actionable than the primal solution itself.

8 Uncertainty and limitations

Shadow prices carry the same uncertainties as the underlying LP, plus one of their own: they are only valid within a specific range.

Limitations of shadow prices
Limitation	Effect
Coefficient uncertainty	Shadow prices depend on the objective and constraint coefficients; if those are wrong, so are the shadow prices
Validity range	Beyond the sensitivity range, the shadow price changes
Discrete resources	If the resource is only available in discrete increments, the shadow price approximates but does not exactly describe the value
Nonlinear effects	Real production functions may have economies of scale; the linear shadow price ignores these

Check the sensitivity range

A shadow price of $10 for material is only valid within the sensitivity range for that constraint's RHS. If a supplier offers a large quantity, the price may fall once the optimum changes. Lesson 3 develops the sensitivity ranges.

9 Common implementation errors

Watch for these

Misinterpreting the sign. Different software packages use different sign conventions for shadow prices. Verify against the definition: for a maximization problem, a binding ≤ constraint should have a nonnegative shadow price.
Applying shadow prices outside the sensitivity range. The price applies only for small changes within the range. For large changes, re-solve.
Confusing shadow price with the total value of a resource. The shadow price is a marginal rate, not the total value. It describes what the next unit is worth, not what all units are worth together.
Missing units. The shadow price has units of "objective per unit of constraint." A report without units is incomplete.
Assuming shadow prices are always positive. For a maximization problem with ≤ constraints, yes. For other forms, the sign depends on the direction of the inequality.
Reporting reduced costs for variables that are in the basis. Basic variables have zero reduced cost; reporting a nonzero value for them is an error.

10 Independent modelling task

Your turn

Use the LP from Lesson 1's task. Solve it and obtain the solver's sensitivity report.
Record the shadow price of each constraint. State the units and the interpretation in terms of the decision problem.
Record the reduced cost of each variable. Interpret each in terms of an opportunity cost.
Verify shadow prices by direct experiment: for a binding constraint, increase its RHS by one unit, re-solve, and check that the objective changes by approximately the shadow price.
Verify complementary slackness: list every constraint and check that non-binding constraints have shadow price zero.
Write a one-paragraph recommendation: which resource, if available at a given price, is worth acquiring, and which is not?

This exercise forms part of Laboratory 12 and the shadow-price component of Assignment 5.

11 Reflection prompt

Reflect before continuing

A decision-maker is offered a large additional quantity of a resource with a positive shadow price. Is the shadow price a valid basis for deciding whether to accept?

Two or three sentences. Consider the difference between a small increase within the sensitivity range and a large increase that changes the optimal basis.

12 Lesson summary

Key takeaways

Shadow prices are the optimal dual variables. They measure the marginal value of relaxing a constraint.
Binding constraints have positive shadow prices; non-binding constraints have zero. This is complementary slackness.
Reduced costs are the opportunity costs of variables. A variable with positive reduced cost would become attractive if its objective coefficient increased by more than the reduced cost.
Shadow prices have units. Objective per unit of constraint.
Shadow prices are valid only within sensitivity ranges. Beyond those ranges, re-solve.

Coming next

Lesson 3 develops the sensitivity ranges themselves: how much can each coefficient or bound change before the shadow prices change.

§ Self-quiz, practice, and homework

Practice exercises

For the production planning LP, compute the shadow price of material. What is the maximum a manager should pay for an additional kilogram?
If the profit on product A increases from $40 to $75, is the shadow price of demand A still $30? Explain.
For a variable that is zero at the optimum with reduced cost $5, by how much must the objective coefficient increase before the variable enters the solution?
Explain in two sentences why basic variables have zero reduced cost.

Homework problems

Shadow price analysis. Take an LP of your choice. Solve it in a spreadsheet, obtain the sensitivity report, and interpret the shadow price of each constraint. State the units, the interpretation, and a decision implication for each. 500 words.
Reduced cost analysis. For the same LP, list the reduced cost of each variable. If a variable has positive reduced cost, compute the threshold objective coefficient at which it would enter the basis. Discuss the decision implications.
Direct verification. For a binding constraint, increase its RHS by 1, 5, 10, 50, and 100 units. Re-solve each time and record the change in the objective. Plot the changes against the size of the perturbation. Identify the point at which the shadow price is no longer valid.

Mini project

Produce a shadow price report for an LP model of your choice. Include the primal solution, the shadow price of each constraint (with units), the reduced cost of each variable, and a paragraph on the decision implications. Recommend which constraints are worth relaxing and at what cost. Submit the spreadsheet and the report. This is part of Laboratory 12 and Assignment 5.