A production plan may have been optimized using estimated unit profits. If an estimate changes, must the plan be computed again? The feasible set has not moved, but the direction in which we measure improvement has. Reduced costs let us test the existing basis before running another optimization. This unit develops a general basis test.
A certificate for changing costs
Definition 22.1.1
(Basis and reduced costs for a changed objective)
Consider the finite linear program subject to , , where has full row rank. A basis is an invertible square matrix formed by columns of ; let contain the remaining columns, partition and accordingly, and set . The basis is primal feasible if . For a cost vector , its multiplier and reduced costs are
Throughout, the basis is primal feasible.
Theorem 22.1.2
(Exact basis test for a cost change)
The basic solution is optimal for the changed objective whenever . Conversely, if this basis admits a dual-feasible multiplier satisfying equality on its basic columns, then . Thus these inequalities give exactly the cost vectors for which this basis is both primal and dual feasible. The test includes zero reduced costs and degenerate bases.
Proof
(Substitute the basic variables into the objective)
Every feasible satisfies . Substitution gives
If , the last term is nonnegative for every feasible , because , so the basic solution attains a global minimum. Equivalently, and provide a matching dual bound. For the converse, equality on forces the multiplier to be ; dual feasibility on then gives exactly the displayed inequalities.
Proof X-ray
What the substitution identity does and does not decide
Assumptions and where they enter: invertibility of lets every feasible point be written through its nonbasic coordinates; makes the basic point feasible, so it is a candidate at all; turns into a nonnegative remainder.
Key move: the identity holds for every feasible , so a sign check on finitely many coefficients controls the whole feasible set.
The converse is narrower than it looks: it uses equality on all basic columns to pin the multiplier down uniquely, so it is a statement about this basis as a certificate, not about the basic point. The degenerate counterexample below shows the difference.
How it closes: only enters , while does not depend on . A cost change therefore never threatens primal feasibility, which is why one family of inequalities in is the whole test.
The theorem's converse concerns the basis certificate: a degenerate basic point can remain optimal even after this particular basis loses dual feasibility, since another basis can represent the same point.
Counterexample mode
A failed basis test at an optimal degenerate point
A plausible claim is that a negative reduced cost proves the basic point suboptimal. Minimize subject to , . The only feasible point is , so it is optimal. Choose basic: , , , and the reduced cost of is . The basis fails the test although its point is optimal; the basis gives and reduced cost for , certifying the same point. The correct statement: a failed test shows only that this basis is not a dual certificate.
One parameter and simultaneous changes
For , first solve , then compute . Each coordinate is affine in ; intersect all inequalities . A nonbasic cost change alters its own reduced cost directly. A basic cost change also changes and can affect every nonbasic reduced cost. If only changes, remains fixed, so primal feasibility needs no new calculation. On the certified interval the optimal value is ; outside it the test alone does not identify the new optimum.
Common mistake
(Treating a basic cost change as local)
Changing the cost of a basic variable does not touch that variable’s own reduced cost, which stays zero; it moves the multiplier , and through every nonbasic reduced cost. In the example below, changing the profit of the basic variable to changes both slack coefficients, to and . Concluding that every is harmless because is basic is wrong: at the second coefficient is and the basis is no longer optimal.
A reported range for each coefficient with all others fixed cannot generally be used simultaneously. For a safe combined change, evaluate all the new reduced costs together. A sufficient shortcut is the following rule.
Proposition 22.1.3
(The 100% rule)
Suppose the basis is certified for and for each of the cost vectors , meaning that all their reduced costs are nonnegative. If and , the basis is also certified for .
Proof
(A convex combination of certified cost vectors)
Write , a convex combination. The map is linear, so the reduced costs of the combination are the same convex combination of nonnegative vectors, hence nonnegative.
In practice is the largest certified one-at-a-time change in the stated direction, and is the fraction of it that is used. The rule is sufficient, not necessary, and requires the stated directions and ranges.
Common mistake
(Adding one-at-a-time ranges)
Each reported range assumes every other coefficient is fixed. Two changes that are separately inside their ranges can together leave the region: the practice question below on changing both coefficients has and , each certified alone, but together the basis fails. Either test the combined reduced costs or check that the fractions used sum to at most one.
Worked example: a changing profit
Worked example 22.1.4
(A range, its endpoint, and what follows)
Maximize with , , and . Introduce slacks :
Choose basic. Then and , hence
Both slack coefficients are nonpositive exactly when , so the basic plan is optimal there, with value . The maximization dual prices are : they satisfy the column inequalities and are nonnegative precisely in that range. At the second slack has zero reduced cost, and every for is optimal. For , the objective is , attained at ; the value is . The kink at shows why extending the old affine value formula beyond its certified range fails.
Combined changes in the same model
The practice question below on changing both coefficients gives the exact region for changing both profits to : the basis of stays optimal exactly when and . The one-at-a-time ranges are and . The next two examples compare the 100% rule with that exact region.
Concept lensGeometric
The certified costs form a cone
Write the profits as . The exact region becomes , which says with : the objective lies in the cone spanned by the normals of the two constraints tight at . In the minimization form of the theorem, the certified cost vectors are exactly , a convex cone. The 100% rule is a consequence of this convexity.
Worked example 22.1.5
(The 100% rule certifies a combined change)
Take . The decrease in the first profit uses of its range down to ; the increase in the second uses of its range up to . The fractions sum to , so the rule certifies the basis.
Check against the exact region: and . The value is . Directly, gives , the vertex gives , and gives , so is indeed best among the vertices.
Worked example 22.1.6
(A certified change that the 100% rule cannot see)
Take . The change lies outside the one-at-a-time range , so the 100% rule does not apply at all. The exact region still certifies it: and .
Check: the dictionary coefficients are and , both nonpositive. The value is . Directly, gives and gives . Raising the first profit enlarged the room for the second; one-at-a-time ranges cannot record such interaction, which is why the rule is sufficient but not necessary.
Practice with solutions
Quick check
(With the same constraints, maximize . Find the range where has the same basis certificate.)
Substitute and .
Solution · Answer
Substitution yields . Both slack coefficients must be nonpositive, giving . The value in this range is .
Quick check
(Start from and change both coefficients to . Derive the exact region for the same basis. Check .)
Both changes enter the same dictionary.
Solution · Answer
The dictionary is . The region is and . The proposed point violates the second condition: individually each change is within its one-at-a-time range, but together they are not certified. Indeed has value , exceeding at .
Quick check
(In the minimization theorem, what can be concluded from a negative reduced cost at a degenerate basis?)
Recall what the converse of the theorem is about.
Solution · Answer
This basis fails the dual test; it does not by itself prove that the basic point is suboptimal. The zero-only feasible set in the counterexample demonstrates why. A feasible improving direction or a different certificate is needed.