At the optimum, the objective-row entries under the columns that started as the identity are exactly c_BᵀB⁻¹. That vector is dual feasible and its dual objective equals the primal optimum, so the simplex method has been solving both programmes all along and the final tableau is a proof of strong duality on this instance rather than evidence for it. The prices are not in the right-hand column, and on a floor or a quota the identity columns are not the slack columns.
Core ideas
One hard idea: the second programme was never solved separately. Everything else here is knowing which columns to look under.
Column i of B⁻¹ is the tableau column standing over whatever column of the original data was eᵢ. The objective-row entry there is c_BᵀB⁻¹eᵢ, which is yᵢ. So the whole price vector is m numbers already printed in the tableau you finished with, in a row most readers walk past.
On a ≤ row the identity column is the slack. On a ≥ row the slack is a surplus, whose original column is −eᵢ, so the identity column is the artificial beside it. An = row has no slack column at all, and its identity column is the artificial. The lab prints the kind of every column it used for exactly this reason.
Check yᵀaⱼ ≥ cⱼ column by column and you have dual feasibility. Check bᵀy = z* and weak duality does the rest: equal values at a feasible pair prove both points optimal. Together those are a proof of strong duality on this instance, done in exact fractions, with no appeal to a general theorem.
The material
Which columns hold the inverse, why the objective row over them is the price vector, and the two checks that close the argument.
The previous lesson ended with prices that closed the gap exactly and no account of where they came from. They were not guessed. They were sitting in the final tableau of the primal solve, in the objective row, and this lesson is the whole of that fact.
In standard form the constraint matrix A contains, for each row i, some column equal to the unit vector eᵢ. Call those the initial identity columns. A ≤ row contributes its slack; a ≥ row contributes its artificial, because its surplus column is −eᵢ; an = row contributes its artificial, having no slack at all.
The tableau is B⁻¹[A | b], so the tableau column standing over the initial identity column for row i is B⁻¹eᵢ, which is column i of B⁻¹. That is the sentence the rest of the lesson rests on.
Let the simplex method finish on a maximisation with basis B, and set y = c_BᵀB⁻¹, read off the objective row under the initial identity columns. Then y is dual feasible and bᵀy = z*. Consequently y is optimal for the dual and the primal optimum equals the dual optimum.
Dual feasibility is the optimality test itself: the objective-row entry over column j is c_BᵀB⁻¹aⱼ − cⱼ = yᵀaⱼ − cⱼ, and the method stopped precisely because every one of those is non-negative. And bᵀy = c_BᵀB⁻¹b = c_Bᵀx_B = z*, because B⁻¹b is the basic part of the plan. Weak duality then gives optimality of both points.
This is an argument about the instance in front of you, and it is the version this course takes, because it is the one a reader can execute. The separating-hyperplane route through the theorems of the alternative proves more and shows less.
The three initial identity columns are the slacks s1, s2, s3, and the objective row over them reads 0, 3/2, 1. So the cutting row is worth nothing, an hour of glazing is worth 3/2, and an hour of assembly is worth 1.
The dual check, column by column: x1 gives (0)(1) + (3/2)(0) + (1)(3) = 3 ≥ 3, a gap of 0; x2 gives (0)(0) + (3/2)(2) + (1)(2) = 5 ≥ 5, a gap of 0; the three slack columns give 0, 3/2 and 1 against a cost of 0, gaps of 0, 3/2 and 1. Every gap is non-negative, so y is dual feasible. And bᵀy = 4(0) + 12(3/2) + 18(1) = 36, which is z*.
Notice which gaps came out zero. The two decision columns are in the basis or were brought into it, and a basic column's gap is exactly zero; the slack columns' gaps are the prices themselves. That pattern is not a coincidence either, and it is the next lesson.
Every worked example above has only ≤ rows, which is the case where the two lists coincide and the distinction is invisible. The moment a row is a floor or a quota the lists part company, and reading the price out of the slack column gives a number that is not a price.
The bakery maximises 5x + 4y subject to 6x + 4y ≤ 24 (flour), x + 2y ≤ 6 (sugar) and x + y ≥ 2 (contract). Its standard form has columns x, y, s1, s2, e3, a3: two slacks, then a surplus and an artificial for the floor.
The lab reports the columns it read as slack, slack, artificial. The prices are y = (3/4, 1/2, 0), and bᵀy = 24(3/4) + 6(1/2) + 2(0) = 21, which is z* at the plan (3, 3/2). Read the third price out of the surplus column e3 instead and you get the negative of it, because that column of the original data is −e₃.
Replace the bakery's floor with x + y = 3. Now the standard form is x, y, s1, s2, a3 — there is no third slack to read anything out of. The identity column for that row is the artificial, the prices are y = (0, 0, 5), and bᵀy = 24(0) + 6(0) + 3(5) = 15 = z* at the plan (3, 0).
Both of the ≤ rows have slack here and are priced at nothing, and the entire value of the programme is attributed to the quota. The y column's dual gap is 5 − 4 = 1, which says the second product is worth 1 less than the quota room it would consume.
The claim that the tableau is B⁻¹[A | b] can be checked rather than believed. Gather the basis columns out of the original matrix, invert that, multiply by the original A, and compare entry for entry with the tableau on the screen. On the workshop the basis is x1, s1, x2, B⁻¹ has rows (0, −1/3, 1/3), (1, 1/3, −1/3) and (0, 1/2, 0), and B⁻¹b = (2, 2, 6) — the right-hand column. The lab's second view does this for every preset, and the engine's own checks do it on 178 programmes.
So the reading is not a rule of thumb about where numbers sit. It is a consequence of what the tableau is, and once that is seen, the sensitivity questions in the second half of this course are all ratio tests on the same object.
Interactive
y = c_B·B⁻¹, read off the columns that started as the identity
Method
Identify the columns before reading any numbers. Everything that goes wrong here goes wrong at that step.
One per row. A ≤ row gives its slack, a ≥ row gives its artificial, an = row gives its artificial. Do this from the original standard form, not from the final tableau, because the final tableau is what those columns have become.
That is y, row by row, and the order is the constraint order. Do not read the right-hand column: that holds the plan, and the single number at the end of the objective row is z*.
For each primal column j, compute yᵀaⱼ − cⱼ and confirm it is non-negative for a maximisation. Every basic column gives exactly zero; a nonbasic column's gap is its reduced cost, which the ranging lessons use directly.
In fractions, not in decimals. If the two agree you have proved both points optimal by weak duality, with no further argument; if they do not, the identity columns were misidentified, which is the failure this check is here to catch.
The tableau below is what the simplex method left behind. Nothing is recomputed: the prices are copied out of it, and then the two checks turn the copy into a proof.
The two checks are doing different work. Dual feasibility is what makes y a certificate at all; the equality is what makes it a sharp one. Neither needed the dual programme to be solved, and the second is the whole of strong duality on this instance.
For a faded rehearsal, do the same on the bakery, where the third row is a floor. The supplied move is the one that matters: its initial identity column is the artificial a3, not the surplus e3. Read all three prices, check the two dual constraints, and confirm bᵀy = 21. Then predict what you would have got from e3 instead, and check that prediction in the lab.
A reader who wants the third case should then do the quota preset, where there is no third slack column at all and the entire value of the programme is attributed to one equality row.
You should be able to name the initial identity column of a ≤, a ≥ and an = row, read y out of the objective row over them, check yᵀaⱼ ≥ cⱼ for every column, and confirm bᵀy = z* in exact fractions — and say what it proves when it does.
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.