At optimality a positive price forces its constraint tight and a positive activity forces its dual constraint tight. Run those implications backwards and a claimed plan determines a candidate set of prices by a small linear system; testing those prices for feasibility certifies the claim or refutes it, with no algorithm run at all. The converse does not hold, and where it fails is where degeneracy first bites.
Core ideas
The conditions themselves are two lines. The idea is that they can be read as a system to solve rather than a property to observe.
Weak duality's two links are sums of non-negative terms. If the ends are equal then every term in both sums is zero, which means yᵢ and row i's slack are never both positive, and xⱼ and dual column j's gap are never both positive. Complementary slackness is that statement and nothing more.
Given a claimed plan you know which rows have slack — those prices are zero — and which activities are positive — those dual constraints are equalities. That is m linear equations in m unknowns, usually, and solving it is arithmetic rather than search.
If the prices come out feasible for the dual, then the claim and the prices are a feasible pair with equal values, so both are optimal. If any sign or any dual constraint fails, the claim is refuted and the failing constraint is the reason. No pivot is performed either way.
The material
Where the conditions come from, how to run them backwards, and the two ways the system can fail to settle the question the way you expect.
A primal-feasible x and a dual-feasible y satisfy complementary slackness when, for every row i, either yᵢ = 0 or row i holds with equality; and for every column j, either xⱼ = 0 or dual constraint j holds with equality.
The two halves have names worth keeping apart. A row with slack must be priced at zero; an activity that is used must be exactly worth its ingredients.
A feasible pair (x, y) is optimal for both programmes if and only if it satisfies complementary slackness.
Weak duality gave cᵀx ≤ yᵀAx ≤ bᵀy. Write the two gaps out: the right one is bᵀy − yᵀAx = yᵀ(b − Ax), a sum of products of a price and its row's slack, and the left one is yᵀAx − cᵀx = (Aᵀy − c)ᵀx, a sum of products of a dual gap and its activity. Feasibility makes every factor in both sums non-negative.
So cᵀx = bᵀy exactly when both sums are zero, which for non-negative terms means every individual product is zero — which is complementary slackness. And by weak duality, cᵀx = bᵀy at a feasible pair is precisely optimality of both.
□
That is the theorem. The use is what makes it worth a lesson: somebody hands you a plan and says it is optimal, and you would like to find out without running the algorithm. The conditions tell you which prices are forced to be zero and which dual constraints are forced to be equalities, and that is usually enough equations to determine y outright.
The system above has three equations — one from the slack row, two from the positive activities — and three unknowns, and it produces the same y the final tableau holds, reached without a single pivot. The lab prints each equation with the sentence that produced it, so that the system is visibly derived rather than assembled.
The three-activity preset is the same exercise with one activity not made. Claim (2, 6, 0): the contract row has 2 spare, so its price is 0; the two positive activities give 2y1 + y2 + y3 = 8 and y1 + y2 = 5; solving gives y = (3, 2, 0), and bᵀy = 46 = cᵀx. The unused third activity contributes no equation at all, and its dual constraint is left to be checked as an inequality: y1 + 2y2 = 7 ≥ 3, which holds with 4 to spare.
Claim x = (4, 3) for the workshop. It is feasible: 4 ≤ 4, 6 ≤ 12, 18 ≤ 18. Glazing now has 6 spare, so y2 = 0; both activities are positive, so y1 + 3y3 = 3 and 2y2 + 2y3 = 5. The second gives y3 = 5/2, and then y1 = 3 − 15/2 = −9/2.
The cutting row is a ≤ row in a maximisation, so its price may not be negative. The claim is refuted, and the reason is a specific one that can be stated: no set of prices consistent with this plan is dual feasible, so this plan cannot be optimal.
Now the trap. At that refuted claim, cᵀx = 27 and bᵀy = 27 as well — the two numbers agree. Equal values prove optimality only for a feasible pair, and y = (−9/2, 0, 5/2) is not feasible, so the agreement establishes nothing. The lab prints both numbers side by side on this preset for exactly that reason: the coincidence is what makes the feasibility test look skippable, and it is not.
It is tempting to read the conditions in both directions and conclude that a tight row must carry a positive price. That is false, and it fails precisely at a degenerate optimum. The conditions say that a positive price forces tightness; they say nothing at all about a tight row, and at a corner where more rows are tight than there are variables they cannot.
max x + y subject to x ≤ 2 (kiln), y ≤ 2 (wheel) and x + y ≤ 4 (firing). The optimum is (2, 2) with z* = 4, and all three rows are tight there. No row has slack, so the conditions give only two equations — y1 + y3 = 1 and y2 + y3 = 1 — for three unknowns.
The lab solves that underdetermined system, reports y = (1, 1, 0), and says in as many words that y3 was never pinned down: the conditions left it free and a choice was made. So here is a row that is tight and priced at exactly nothing, and a second set of prices (0, 0, 1) that is equally optimal. Degeneracy in the primal is multiple optima in the dual, and this is the smallest instance of it.
The system can also be contradictory, which is a refutation of a different shape. Claim (1, 1) on the same programme: every row has slack, so all three prices are forced to zero, and both activities are positive, so y1 + y3 = 1 — 0 = 1. There are no prices to test at all, and the lab reports the verdict as such rather than inventing one. An infeasible claim, by contrast, is refused before any of this begins.
Interactive
the slackness conditions solved for a price vector, and that vector tested
Method
Feasibility, then the conditions, then the system, then the test. Stop at the first step that fails, and say why.
One substitution per row and the sign restrictions. An infeasible claim is refuted here, and going on to solve for prices would be answering a question nobody asked.
A row with slack forces its price to zero. A strictly positive activity forces its dual constraint to hold with equality. Tight rows and unused activities contribute nothing — that is the asymmetry the converse gets wrong.
Usually it determines y. When it does not — fewer equations than prices, which is what a degenerate corner produces — say so, and record that any choice you then make is a choice rather than a consequence.
Certified means: feasible pair, equal values, both points optimal. Refuted means: name the constraint or the sign that failed. Do not let cᵀx = bᵀy stand in for the feasibility test; those two numbers can agree at a refuted claim.
Both claims are feasible and both produce a full set of prices. The difference is one sign, and the second half is written out because the numbers there conspire to look like a proof.
Claim B is the one to remember. Its two values agree to the last fraction, and the pair is still not optimal, because equal values prove optimality only when both points are feasible. Reading 27 = 27 as a certificate is the error the feasibility test exists to prevent, and the true optimum is 36.
For a faded rehearsal, claim (2, 2) on the degenerate programme max x + y subject to x ≤ 2, y ≤ 2, x + y ≤ 4. The supplied observation is that no row has slack, so the conditions give you two equations and not three. Write them, say what is left undetermined, choose a value, and check that your choice is dual feasible. Then find a second, different set of optimal prices for the same plan.
Then claim (1, 1) on that same programme and watch the conditions contradict each other: every row slack forces every price to zero, and a positive activity then asks for 0 = 1. There is nothing to test, and the honest verdict is that no prices can accompany the claim.
You should be able to check a claim for feasibility, write exactly one condition per slack row and per positive activity, solve for y, test every sign and every dual constraint, and state the verdict — including the two verdicts that are neither a clean certificate nor a clean refutation: an undetermined price at a degenerate corner, and a contradictory system with no prices at all.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.