Sensitivity analysis

Why it matters

The numbers in a model are estimates. Profit per table depends on next month's prices; available hours depend on who calls in sick. A manager rarely asks only "what is the optimal plan?". The next questions are "what if we had one more hour of painting?", "how wrong can the price be before the plan changes?" and "what would it take to make this product worth producing?". Sensitivity analysis answers them, and every LP solver reports the numbers you need for free.

The workshop again

maximize   70x + 50y            (x tables, y chairs)
subject to 4x + 3y <= 240       (carpentry hours)
           2x +  y <= 100       (painting hours)
           x, y >= 0
optimum: x = 30, y = 40, profit 4,100

Both constraints are binding (tight) at the optimum: all 240 carpentry hours and all 100 painting hours are used. A constraint with spare capacity is non-binding, and its slack is the unused amount.

Shadow prices

The shadow price (also called the dual value) of a constraint is how much the optimal objective changes per extra unit of its right-hand side, all else equal.

For the workshop, suppose carpentry rises to 241 hours. Re-solving the two binding equations 4x + 3y = 241 and 2x + y = 100 gives x = 29.5, y = 41 and profit 70 * 29.5 + 50 * 41 = 4,115. One extra carpentry hour is worth 15. The same calculation for painting gives 5 per hour.

These two numbers are the solution of the dual LP:

minimize   240u + 100v
subject to 4u + 2v >= 70        (a table's resources must be "worth" at least its profit)
           3u +  v >= 50        (same for a chair)
           u, v >= 0
solution: u = 15, v = 5, value 240*15 + 100*5 = 4,100

The dual's optimal value equals the primal's (strong duality). The dual variables price each resource so that the products you make exactly "pay" for their resources.

How to use a shadow price:

• Buy more of a resource only if it costs less than its shadow price. Overtime carpentry at 12 per hour adds 3 per hour of profit; at 20 per hour it loses money.
• A non-binding constraint has a shadow price of 0. Extra capacity you are not using is worth nothing.
• Shadow prices are valid only within a range of the right-hand side. For carpentry, the same two constraints stay binding while carpentry hours are between 200 and 300; for painting, between 80 and 120. Outside the range the plan's structure changes and the shadow price changes with it.

Reduced costs

A variable at zero in the optimal plan has a reduced cost: how much its objective coefficient must improve before it is worth making.

In the furniture shop from module 1 (desks, tables, chairs; optimum 2 desks, 0 tables, 8 chairs, profit 280), the shadow prices are 0 for lumber (not binding), 10 for finishing and 10 for carpentry. A table uses 6 lumber, 2 finishing and 1.5 carpentry hours, so its resources are "worth" 0*6 + 10*2 + 10*1.5 = 35. It earns only 30, so its reduced cost is 5: raise the table profit above 35 and tables enter the plan. A variable that is already in the plan has a reduced cost of 0.

Ranges of optimality

How much can one objective coefficient change before the optimal plan (the corner) changes? The workshop's corner (30, 40) stays optimal while the profit ratio of table to chair stays between the slopes of the two binding constraints, 4/3 and 2:

• With chair profit fixed at 50, table profit can range from about 66.67 to 100.
• With table profit fixed at 70, chair profit can range from 35 to 52.5.

Inside the range, the plan stays the same but the total profit changes. Outside, the solver jumps to a different corner.

Reading solver output

• scipy (method="highs"): res.ineqlin.marginals are the duals of the <= rows and res.ineqlin.residual the slacks. Because linprog minimizes, flip the sign when you negated a maximization.
• PuLP: after solving, prob.constraints["carpentry"].pi is the shadow price and .slack the slack; x.dj is a variable's reduced cost.
• Excel Solver prints a Sensitivity Report with "Shadow Price", "Reduced Cost" and "Allowable Increase/Decrease" columns.

Important limits

• All of this is one change at a time. Several simultaneous changes need re-solving (or a scenario run).
• It applies to LPs. Integer programs have no clean shadow prices; analysts re-solve scenarios instead.
• With degenerate solutions (more binding constraints than needed to fix the corner), shadow prices can differ depending on the direction of the change.

Quick recap

• Binding constraints have zero slack; non-binding ones have shadow price 0.
• Shadow price = change in the optimum per extra unit of a resource, valid within a range.
• Reduced cost = how much a zero variable's coefficient must improve to enter the plan.
• Ranges of optimality say how far a coefficient can move before the plan changes.
• Sensitivity holds one change at a time, and only for LPs.

Check yourself

Answer the questions in the Do tab.