For any primal-feasible plan and any dual-feasible set of prices, the plan's value is at most the middle quantity and the middle quantity is at most the prices' value. Two inequalities, each coming from one sign restriction, and between them they bracket the optimum. A single feasible set of prices is therefore a proof about the primal that cost no solving at all, and when the two ends agree, both points are proved optimal with no further argument.
Core ideas
There is one inequality here and it has two halves. What is new is not the algebra but what a single feasible point of the second programme is now worth.
yᵀAx is the same number read two ways. Grouped as (Aᵀy)ᵀx it is at least cᵀx, because Aᵀy ≥ c and x ≥ 0. Grouped as yᵀ(Ax) it is at most bᵀy, because Ax ≤ b and y ≥ 0. Neither half uses optimality, an algorithm, or any property of the points beyond feasibility.
Any dual-feasible y — guessed, inherited from a previous solve, produced by a heuristic — proves that no feasible plan earns more than bᵀy. That is a claim about every point of a region you have not enumerated, from one point you did not have to solve for, and it is the property everything later on this path lives on.
If a feasible pair has cᵀx = bᵀy, then no plan beats x and no prices beat y, so both are optimal. That is the whole proof: two lines of it, and it needs no pivots. A gap, by contrast, brackets the optimum without locating it.
The material
Where the two inequalities come from, why a guessed set of prices is already a proof, and what happens when you try to beat the bound.
Take any plan that satisfies the primal's constraints and any set of prices that satisfies the dual's. Neither has to be optimal and neither has to have been solved for. Then write down the single number yᵀAx and read it two ways.
If x is feasible for the primal maximisation and y is feasible for its dual, then cᵀx ≤ bᵀy. In particular every dual-feasible y gives an upper bound on the primal optimum, and every primal-feasible x gives a lower bound on the dual optimum.
If cᵀx = bᵀy for such a pair, then x is optimal for the primal and y is optimal for the dual.
Both inequalities of the chain hold by the two sign arguments above, so cᵀx ≤ bᵀy for every feasible pair. Now suppose cᵀx = bᵀy. Any feasible x̂ satisfies cᵀx̂ ≤ bᵀy = cᵀx, so no feasible plan earns more than x does, and x is optimal. Any feasible ŷ satisfies bᵀŷ ≥ cᵀx = bᵀy, so no feasible prices value the resources below y, and y is optimal.
Note what is absent. No algorithm was run, no basis was mentioned, and nothing was assumed about how either point was obtained.
□
The bakery maximises 5x + 4y subject to 6x + 4y ≤ 24, x + 2y ≤ 6 and x + y ≥ 2. Guess the crudest prices that work: y = (1, 0, 0). Check dual feasibility — 6(1) ≥ 5 for the x column and 4(1) ≥ 4 for the y column — and the certificate is valid.
It says no plan earns more than bᵀy = 24. The plan x = (1, 1) earns 9, so the chain reads 9 ≤ 10 ≤ 24. The true optimum is 21, so the guess was not sharp; it was, nonetheless, a proved bound obtained by inspecting one column at a time.
A chain reading 8 ≤ 9 ≤ 42 establishes that the optimum lies between 8 and 42 and says nothing at all about where. On the workshop it is 36, close to the upper end; nothing in the chain could have told you that. What the two links do give you is an account of where the gap went: 1 of it is the amount by which the prices overvalue what this plan actually consumes, and 33 of it is the amount of resource the plan leaves unused at those prices.
This is also why a gap is not evidence against either point. One end of a wide chain can already be optimal — the plan could be perfect and the prices dreadful — and the chain cannot distinguish that case from one where both are poor. Only a closed gap says anything about either point on its own.
The lab invites you to type a plan that earns more than the prices allow, and refuses every attempt by naming which of the two points is not feasible. That refusal is the theorem. Type x = (10, 10) against the workshop's optimal prices and the numbers do read 80 against 36 — and the panel reports that all three rows are broken, so the plan was never a candidate.
Offer y = (0, 0, 1) for the workshop. Then bᵀy = 18, and the optimal plan (2, 6) earns 36, which is more. Weak duality has not failed: the x2 dual constraint asks for 2y2 + 2y3 ≥ 5 and these prices give 2, so y is not dual feasible and was never a certificate.
This is the check to run first and the one most often skipped. A number is a bound because its point is feasible, and feasibility is one substitution per dual constraint.
min 2x + 3y subject to x + y ≥ 4, x ≤ 3, y ≥ 1 has the dual max 4y1 + 3y2 + y3 subject to y1 + y2 ≤ 2, y1 + y3 ≤ 3, with y1, y3 ≥ 0 and y2 ≤ 0. At x = (3, 2) and y = (1, 0, 0) the chain reads 4 ≤ 5 ≤ 12, with the primal value at the top.
Everything has turned over: now the dual value is the lower bound and the primal value the upper one, and a certificate proves that no plan costs less than 4. The optimum is 9. A kit that had hard-coded the direction would report the wrong claim here rather than the wrong number, which is the harder failure to notice.
This one inequality reappears twice more on this path wearing different nouns. In Networks: Flows, Paths and Assignments it is the statement that any cut's capacity bounds any flow, with the cut playing the part of the prices. In Integer Programming it is the optimality gap that lets a search stop early, with the relaxation's value playing the part of bᵀy. Both of those are this chain, and both cite it.
Interactive
c·x ≤ y·Ax ≤ b·y, with exact numbers at each link and the refusal named
Method
Feasibility first, both times. The three numbers are worthless if either point has not been checked.
Substitute and compare, one row at a time, and check the sign restrictions too. A plan with a negative entry fails before any row is reached, and the lab reports that as a sign failure rather than as a broken constraint.
One substitution per primal column, plus the sign rule each row's direction imposed. This is the step that gets skipped, and skipping it is how a number that bounds nothing gets quoted as a bound.
cᵀx, then Ax and yᵀ(Ax), then bᵀy. The middle quantity is what splits the gap into the part the prices overvalue and the part the plan leaves unused, and computing it is how you check your own arithmetic.
With a gap: the optimum lies between these two numbers. With no gap: both points are optimal, and no algorithm was needed. Never say the optimum is near the middle quantity — it need not be.
The first pair is deliberately poor: a plan making one of each product and prices somebody rounded off. It still proves something. The second pair is the optimum, and the point of putting them side by side is that the second proof is no harder than the first.
The second half is a complete proof of optimality for a two-variable programme, and it consists of eight substitutions and two dot products. No pivot, no tableau, no corner enumeration. That is what a certificate buys.
It also leaves an obvious question, which is the next lesson's: where did y = (0, 3/2, 1) come from? Guessing prices that close the gap exactly is not something you would want to rely on. They were read off the final tableau of the primal solve, and “Strong Duality from the Final Tableau” is where that stops being a coincidence.
For a faded rehearsal, take the bakery: max 5x + 4y subject to 6x + 4y ≤ 24, x + 2y ≤ 6, x + y ≥ 2. The supplied move is the plan x = (1, 1). Find any dual-feasible set of prices by inspection, compute all three quantities, and write down the bracket you have proved. Then compare it with the true optimum of 21 and say how much of your gap each link accounts for.
You should be able to check a pair for feasibility on both programmes, compute all three quantities of the chain, name which sign restriction produces each link, split a gap into its two parts, and state the conclusion as a bracket or as a proof of optimality — without ever saying the optimum is near the middle number.
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.