Recipe

Find the allowable range for one cost coefficient

Use when: you know an LP's optimal vertex and its other candidate vertices, and need to know how far ONE cost coefficient can move before a different vertex becomes optimal

Goal: the exact interval that coefficient can move through while today's optimal vertex -- and its shadow prices -- stay valid

Taught in Sensitivity to cost changes · a later section extends this recipe with more cases

Quick recipe

Perturb the coefficient
Substitute the shift into the cost at every candidate vertex
Impose that the current vertex stays best
Read the tightest bracket, then add the base value back

1
Take the cost coefficient $c_j$ you're asked about and write it as its current value plus an unknown shift: $c_j+\Delta$ . Every other coefficient, and every constraint, stays exactly as it was.

Example

For Meadowbrook's Feed A cost $c_1=4$ , write it as $4+\Delta$ , holding $c_2=3$ fixed.
- Not yet: a resource (right-hand-side) value, rather than a cost coefficient — covered in Sensitivity to resource changes
Why: isolating one unknown is what makes "how far can THIS number move" an answerable question at all -- everything else has to hold still to ask it.
2
List the feasible region's other vertices (Chapter 7's basic feasible solutions), then write the objective, with $c_j+\Delta$ plugged in, evaluated at the current optimal vertex and at each of those other vertices.

Example

At $(4,3)$ : $(4+\Delta)(4)+3(3)=25+4\Delta$ . At $(10,0)$ : $(4+\Delta)(10)+3(0)=40+10\Delta$ . At $(0,15)$ : $(4+\Delta)(0)+3(15)=45$ .

Why: the allowable range is defined by comparisons between vertices, so every comparison needs both sides written as the same function of $\Delta$ before anything can be compared.
3
Since this is a minimization, require the current vertex's cost to stay at or below every other vertex's cost, one inequality per comparison.

Example

Against $(10,0)$ : $25+4\Delta\le40+10\Delta \Rightarrow -15\le6\Delta \Rightarrow \Delta\ge-2.5$ . Against $(0,15)$ : $25+4\Delta\le45 \Rightarrow \Delta\le5$ .
- the inequality solves to $\Delta\ge(\text{something})$ — that comparison sets the LOWER edge of the range.
- the inequality solves to $\Delta\le(\text{something})$ — that comparison sets the UPPER edge of the range.
⚡ Shortcut

Skip writing out the full inequality: compute each vertex's cost at the current (unperturbed) coefficients, subtract the current vertex's cost from it, and divide by the difference in $x_j$ 's own coordinate between the two vertices. Against $(10,0)$ : $(40-25)/(4-10)=15/(-6)=-2.5$ -- a negative divisor flips the direction, giving $\Delta\ge-2.5$ directly. Against $(0,15)$ : $(45-25)/(4-0)=20/4=5$ , a positive divisor, giving $\Delta\le5$ -- both edges in two divisions, no inequality algebra at all.

Why: a cost-minimizing solution can never trade itself for a more expensive one, so every OTHER vertex's cost has to stay at least as large as the current vertex's, for the range to still be valid.
4
Among every lower-bound inequality, keep the largest (tightest) one; among every upper-bound inequality, keep the smallest (tightest) one. Add the coefficient's original value back to convert the $\Delta$ -range into the actual allowable range.

Example

Tightest lower bound $\Delta\ge-2.5$ , tightest upper bound $\Delta\le5$ . Adding back $c_1=4$ : the allowable range is $c_1\in[4-2.5,\,4+5]=[1.5,\,9]$ .

Why: $\Delta$ was only ever a bookkeeping device for the shift -- the question asked about $c_1$ itself, not how far it moved.

Common mistakes

Perturbing more than one coefficient at once -- the recipe only ever isolates a single unknown; a second moving coefficient needs its own separate analysis.
Assuming the allowable range is symmetric around the base value. It almost never is: Meadowbrook's own range, $[1.5,9]$ , sits $2.5$ below $c_1=4$ but $5$ above it.
Comparing the current vertex against only one other vertex and stopping -- the tightest bound can come from any candidate vertex, so every one of them needs its own comparison.
Reporting the $\Delta$ -range instead of translating it back to the coefficient's own range in the final answer.
Trusting a comparison against only the FINITE candidate vertices when the region is unbounded in the ranged variable's own direction. If that variable could grow without limit, pushing its cost coefficient's sign the wrong way can make the whole LP unbounded instead of merely switching to a different vertex — Section 8 shows a worked instance of exactly this.