Learning outcomes
- Construct the dual of any LP, including the ≥, = and free-variable rules.
- Apply weak duality, strong duality and complementary slackness.
- Read dual variables as shadow prices and use them for economic decisions.
- Compute ranging on objective coefficients and right-hand sides.
- Apply the 100 % rule — and know what it does not say.
Start here
Solving an LP tells you what to make. That answers the production manager. But there is a second question nobody has asked yet: what is the plan's raw material worth? That is the question facing the person negotiating for machine hours, quoting a transfer price between divisions, or deciding whether overtime at ₹1.20 an hour is worth taking.
The dual is that second question, written out as an LP in its own right. It carries one variable for every resource, and each of those variables is a price — not the price you paid, but what one more unit of that resource would be worth to you, given the plan you are already running.
You never have to solve the second problem separately. Those prices are already sitting in the final simplex tableau of the first, in the slack columns. Solve once, read twice.
Two ideas carry everything below. First, a resource you never run out of is worth nothing extra. Second, every one of these prices comes with a range of validity: acquire enough of a resource and some other constraint becomes the bottleneck instead, at which point the price changes — very often to zero. A price quoted without its range is the commonest way LP results get misused.
1. The dual problem
Every LP — the primal — has a companion, its dual. They describe one situation from opposite ends: the primal allocates scarce resources to activities, the dual prices them. Start from the canonical maximisation form.
What the dual variables mean. Before any mechanics: there is one yᵢ for each primal constraint, and yᵢ is a price per unit of resource i — what you would be willing to pay for one more unit of bᵢ. Hold that in mind and the dual stops being a transposed matrix and becomes three readable statements.
- The dual objective min W = ∑ᵢ bᵢyᵢ values your entire stock of resources at your own prices. You look for the cheapest such valuation, because you want the smallest honest figure the resources can be defended at.
- Each dual constraint ∑ᵢ aᵢⱼyᵢ ≥ cⱼ is what stops the prices sliding to zero. It says: the resources consumed by one unit of activity j must be valued at no less than the profit cⱼ that activity brings in. If they were valued lower, running activity j would create profit out of nothing, and the prices could not be right.
- yᵢ ≥ 0, because with a ≤ ceiling on a resource, having more of it can never make you worse off.
So the dual is a hunt for the lowest set of resource prices that no activity can beat. Those prices have a name — shadow prices — and the section below pins down exactly what they measure. Everything from here on is machinery for computing them and knowing when to trust them.
| Primal | Dual |
|---|---|
| max | min |
| m constraints | m variables |
| n variables | n constraints |
| objective coefficients c | right-hand sides c |
| right-hand sides b | objective coefficients b |
| constraint matrix A | Aᵀ |
| ≤ constraints | ≥ constraints |
A constraint's type fixes its dual variable's sign; a variable's sign fixes its dual constraint's type.
| Primal (max) | Dual (min) |
|---|---|
| constraint ≤ | variable yᵢ ≥ 0 |
| constraint ≥ | variable yᵢ ≤ 0 |
| constraint = | variable yᵢ unrestricted |
| variable xⱼ ≥ 0 | constraint ≥ |
| variable xⱼ ≤ 0 | constraint ≤ |
| variable xⱼ unrestricted | constraint = |
One primal runs through everything that follows: small enough to draw, rich enough to show a slack constraint alongside two binding ones. Read it as a factory making two products at profits of ₹3 and ₹5 a unit, limited by three resources with ceilings 4, 12 and 18.
2. The three duality theorems
If x is primal-feasible and y is dual-feasible, then cᵀx ≤ bᵀy: every dual-feasible point bounds every primal-feasible point from above.
The first inequality uses the dual constraints Aᵀy ≥ c with x ≥ 0; the middle step only rearranges a scalar; the second uses Ax ≤ b with y ≥ 0. ∎
Read economically, weak duality says you can never make more profit than your resources are worth under any honest set of prices.
Two corollaries follow. First, any dual-feasible y — not just the optimal one — puts a ceiling on the primal optimum. So if you hold a feasible plan worth 34 and any feasible price vector worth 36, the true optimum is trapped between them, and the difference bᵀy − cᵀx is the duality gap: the width of that trap. It is what a solver is quoting when it prints "gap 2 %" mid-run, and it is how a solver can stop early and still promise how far from optimal it might be. Second, if the primal is unbounded then no finite ceiling can exist at all, so no dual-feasible y exists either: the dual is infeasible. The same argument runs the other way round.
If either problem has a finite optimum then so does the other, and Z*primal = W*dual.
| Primal | Dual | Possible? |
|---|---|---|
| finite optimum | finite optimum | ✓ the usual case |
| unbounded | infeasible | ✓ |
| infeasible | unbounded | ✓ |
| infeasible | infeasible | ✓ rare but possible |
| finite | infeasible or unbounded | ✗ impossible |
Row four is the one people forget. Because both problems can be infeasible together, an infeasible dual does not on its own prove the primal unbounded — you still have to check that the primal is feasible. Only the last row is genuinely forbidden: a finite optimum on one side always forces a finite, equal optimum on the other.
x* and y* are optimal iff yᵢ*(bᵢ − ∑ⱼ aᵢⱼxⱼ*) = 0 for every i, and xⱼ*(∑ᵢ aᵢⱼyᵢ* − cⱼ) = 0 for every j.
That statement is easier than it looks. Take the first product. Its second factor bᵢ − ∑ⱼ aᵢⱼxⱼ* is just the slack in constraint i — how much of resource i is left over — and primal feasibility makes it ≥ 0. Its first factor yᵢ* is ≥ 0 by dual feasibility. A product of two non-negative numbers is zero only when at least one of them is zero. So for every constraint, either the slack is zero or the price is zero. Hence two working rules.
3. Shadow prices and what to do with them
yᵢ* = ∂Z*/∂bᵢ — the marginal value of one extra unit of resource i, the rate at which the optimum improves as the i-th right-hand side is relaxed.
The derivative is the whole content of the word "marginal". yᵢ* prices the next unit of resource i, not the average unit you already hold, and not what you originally paid for it.
Where to read them. Not from a second solve: in the final tableau yᵢ is the (zⱼ − cⱼ) entry of slack column sᵢ. The reason is that the slack sᵢ is the unused part of resource i, so its column measures what the tableau would give up by holding one more unit idle — which is exactly the value of one more unit. One run gives the plan and the prices together.
- Purchasing. Buy a unit of resource i if its market price is below yᵢ — and only while you stay inside the range computed in the next section.
- Pricing. yᵢ is the correct internal transfer price: charge a division that much for the resource and its local decision will match the firm's optimum.
- Priorities. The largest yᵢ names the tightest bottleneck, so it says where an expansion budget should go first.
- Product costing. Introduce a new product only if its revenue exceeds its imputed resource cost ∑ᵢ aᵢ,new yᵢ — the value of the resources it would take away from the products you already make.
4. Sensitivity analysis: ranging
An optimal plan is a statement about data that will change. Ranging asks how far a number may move before the answer does. It splits into two cases, and the split is not arbitrary — the two kinds of number threaten two different things:
- Changing a profit coefficient cⱼ cannot make a plan infeasible; the same corner is still available. What it can do is make a different corner more attractive. So a cⱼ range is a test of optimality.
- Changing a right-hand side bᵢ does not change which activity looks profitable; it moves the wall of the feasible region, so the current corner can slide until some variable would have to go negative. So a bᵢ range is a test of feasibility.
Both tests are read off the same final tableau. Recall from the simplex method that the basic variables are the ones holding a non-zero value in that tableau (here s₁, x₂ and x₁), while the non-basic ones sit at zero; the set of basic variables is the basis, and it is really a label for "which constraints are binding".
Ranging an objective coefficient cⱼ
A non-basic xⱼ is currently not produced. It stays out of the basis — leaving the plan unchanged — until raising its profit makes it worth entering, which happens exactly when zⱼ − cⱼ would turn negative. So the plan survives while cⱼ ≤ zⱼ, that is cⱼ ≤ cⱼcurrent + (zⱼ − cⱼ): the current profit plus the amount by which the variable currently falls short.
A basic xⱼ is harder, because it appears in the tableau's objective row, so changing cⱼ shifts the whole row at once. Optimality survives while every non-basic k keeps (z_k − c_k) + Δcⱼ·αⱼ_k ≥ 0, with αⱼ_k the final-tableau entry in row xⱼ, column k. Each k with αⱼ_k > 0 caps how far Δcⱼ may fall; each k with αⱼ_k < 0 caps how far it may rise; columns with αⱼ_k = 0 impose nothing. Take the tightest cap on each side.
If no non-basic column has αⱼ_k < 0, the right-hand side is a minimum over nothing at all, and the coefficient may rise without limit. Problem 4 below is exactly that case.
Ranging a right-hand side bᵢ
Changing bᵢ by Δ moves the basic variables along the sᵢ column of the final tableau — the i-th column of B⁻¹. This is the one fact worth memorising here: the tableau already carries, in each slack column, the direction the solution slides when you loosen that constraint.
The zⱼ − cⱼ row does not depend on b at all, so optimality is never at risk here; the only thing that can fail is feasibility, x_Bnew ≥ 0. Work through it entry by entry: a basic variable with a positive entry βₖᵢ shrinks as Δ falls, so it limits how far Δ may fall; one with a negative entry shrinks as Δ rises, so it limits the rise. The first variable to reach zero on each side sets that end of the range.
5. The 100 % rule for simultaneous changes
Every range above was computed with all the other data held fixed, and reality rarely changes one thing at a time. Two changes that are each individually safe can still break the basis between them, because they eat into the same slack. The 100 % rule is the cheap test for that: express each change as a fraction of its own allowable range in the direction it is actually moving — an increase against the allowable increase, a decrease against the allowable decrease — and add the fractions. You are asking what share of the available room the changes consume in total.
Note carefully what the rule does not do. Above 1 it is silent. It does not say the basis changed; it says only that you can no longer conclude it did not, so you must re-solve to find out. The condition is sufficient, not necessary — deliberately conservative, which is what you want from a safety check, but which means a sum of 1.667 is a prompt to check rather than a verdict. Problem 5 shows a case that fails the test and survives anyway.
6. Solved problems
Count first. Three primal constraints give three dual variables y₁, y₂, y₃ ≥ 0, one price per resource; two primal variables give two dual constraints, one per column of A.
Now fill them in. The dual objective coefficients are the primal right-hand sides 4, 12 and 18 — the amounts of each resource you hold — so W = 4y₁ + 12y₂ + 18y₃ is the total value of the stock. Each dual constraint reads down a column of the primal, not across a row: the x₁ column of A is (1, 0, 3), so producing one unit of x₁ consumes 1 of resource 1, none of resource 2 and 3 of resource 3, and those must be worth at least the ₹3 that unit earns. Likewise the x₂ column is (0, 2, 2) against a profit of ₹5.
s.t. y₁ + 3y₃ ≥ 3 (the x₁ column)
2y₂ + 2y₃ ≥ 5 (the x₂ column), y₁, y₂, y₃ ≥ 0
| Basis | c_B | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
|---|---|---|---|---|---|---|---|
| s₁ | 0 | 0 | 0 | 1 | 1/3 | −1/3 | 2 |
| x₂ | 5 | 0 | 1 | 0 | 1/2 | 0 | 6 |
| x₁ | 3 | 1 | 0 | 0 | −1/3 | 1/3 | 2 |
| zⱼ − cⱼ | 0 | 0 | 0 | 3/2 | 1 | 36 |
Every entry of the bottom row is ≥ 0, which is the simplex stopping test: no column can improve Z, so this tableau is optimal. Read the answer off the basis column against the RHS column — x₁ = 2, x₂ = 6, and s₁ = 2 of resource 1 left over. Check it against the original objective: Z* = 3(2) + 5(6) = 6 + 30 = 36, which is the 36 already sitting in the bottom-right cell.
No second solve is needed. Take the bottom-row entry under each slack column: under s₁ it is 0, under s₂ it is 3/2, under s₃ it is 1. Those three numbers are the dual solution.
Before trusting them, check they satisfy the dual constraints written in Step 1. First: y₁ + 3y₃ = 0 + 3(1) = 3 ≥ 3 ✓. Second: 2y₂ + 2y₃ = 2(1.5) + 2(1) = 3 + 2 = 5 ≥ 5 ✓. Both hold with equality, and that is not luck: complementary slackness says any activity actually produced must break even exactly at these prices, and here both x₁ > 0 and x₂ > 0.
Value the whole stock at these prices: W = 4(0) + 12(1.5) + 18(1) = 0 + 18 + 18 = 36. That is exactly Z*, so the duality gap is zero. In words, the profit the factory can earn equals the value of the resources it consumes to earn it — nothing is left unaccounted for, which is what strong duality guarantees.
| i | Constraint | LHS | Slack | yᵢ | yᵢ × slack |
|---|---|---|---|---|---|
| 1 | x₁ ≤ 4 | 2 | 2 | 0 | 0 ✓ |
| 2 | 2x₂ ≤ 12 | 12 | 0 | 3/2 | 0 ✓ |
| 3 | 3x₁ + 2x₂ ≤ 18 | 18 | 0 | 1 | 0 ✓ |
Every product in the last column is zero, as the theorem requires. The highlighted row is the interesting one: constraint 1 finishes with 2 units unused, and its price comes out at exactly 0. Rule 1 confirmed — resource 1 is not scarce, so a further unit of it would be worth nothing, and the factory should not pay a paisa for more.
Resource 2 is worth y₂ = ₹1.50 a unit to the factory and can be had for ₹1.20, so each unit bought adds ₹1.50 of profit at a cost of ₹1.20 — a gain of ₹0.30. For three units, net gain = 3 × (1.50 − 1.20) = ₹0.90.
Range check — do not skip this. The ₹1.50 rate is only a derivative, so before multiplying it by 3 we must confirm that all three units fall inside its range. Take the s₂ column of the final tableau, (1/3, 1/2, −1/3)ᵀ, against the basic values (2, 6, 2) in the same order (s₁, x₂, x₁). Raising b₂ by Δ moves each of them:
s₁ = 2 + Δ/3 and x₂ = 6 + Δ/2 both grow with Δ, so neither can ever turn negative for an increase. Only x₁ = 2 − Δ/3 shrinks, and x₁ ≥ 0 forces Δ/3 ≤ 2, that is Δ ≤ 6. Here Δ = 3, comfortably inside, so the ₹1.50 rate really does apply to all three units. BUY.
Nothing about the factory has changed, so the resource is still worth ₹1.50 a unit — but now the asking price is ₹2.00. Each unit bought adds ₹1.50 of profit at a cost of ₹2.00, destroying ₹0.50, and three of them lose ₹1.50. DO NOT BUY. The general rule: buy resource i only when its market price is below yᵢ. Note that the offer is refused even though resource 2 is a genuine bottleneck — being scarce does not make it worth any price.
The new product would need 1 unit of resource 1, 2 of resource 2 and 2 of resource 3. Those units are not free: they would be taken away from the products already being made. Price them at the shadow prices to get the imputed resource cost:
The product sells for ₹6. The difference between what it earns and what it displaces is its reduced cost: c_new − z_new = 6 − 5 = +₹1 > 0. A positive reduced cost means the product pays for the disruption it causes. Introduce it — each unit leaves the firm ₹1 better off than before.
Notice that resource 1 contributed nothing to the cost, because y₁ = 0: the new product helps itself to the idle capacity for free.
This calculation is exactly the simplex entering-variable test, applied to a column that was never in the problem. Doing that on demand instead of enumerating every possible column in advance is column generation, the engine of large-scale LP. Had the product sold for ₹4 instead, the reduced cost would be 4 − 5 = −₹1, and it should not be made: it would consume ₹5 of resources to earn ₹4.
Because we are changing a right-hand side, only feasibility is at stake, and the direction of travel is the s₃ column of the final tableau: (−1/3, 0, 1/3)ᵀ, read against the basic values (s₁, x₂, x₁) = (2, 6, 2) in that order. Writing b₃ = 18 + Δ:
x₂ has a zero entry, so it does not move at all and imposes no restriction. That leaves two conditions. From s₁ ≥ 0: 2 − Δ/3 ≥ 0, so Δ/3 ≤ 2, so Δ ≤ 6 — an increase in b₃ eats the spare capacity of resource 1. From x₁ ≥ 0: 2 + Δ/3 ≥ 0, so Δ/3 ≥ −2, so Δ ≥ −6 — a decrease in b₃ squeezes production of x₁ down towards nothing.
Finally translate the range on Δ back into a range on b₃ itself by adding 18: −6 ≤ Δ ≤ 6 becomes 18 − 6 ≤ b₃ ≤ 18 + 6, that is 12 ≤ b₃ ≤ 24.
Test both ends against the claim that y₃ = 1, that is that Z should move by ₹1 for each unit of b₃.
At b₃ = 24 (Δ = +6): x₁ = 2 + 6/3 = 4, x₂ = 6, s₁ = 2 − 6/3 = 0, so Z = 3(4) + 5(6) = 12 + 30 = 42. And 36 + 6(1) = 42 ✓. At b₃ = 12 (Δ = −6): x₁ = 2 − 6/3 = 0, x₂ = 6, s₁ = 2 + 6/3 = 4, so Z = 3(0) + 5(6) = 30. And 36 − 6(1) = 30 ✓. Both endpoints confirm the rate of exactly ₹1 per unit.
Watch what happens at the top end. At b₃ = 24 the slack s₁ has just hit zero, which means x₁ ≤ 4 has become binding: x₁ cannot grow past 4 no matter how much of resource 3 arrives. Resource 3 has stopped being the bottleneck, and resource 1 has taken over.
So extra resource 3 now buys nothing at all. At b₃ = 30 the plan is still x₁ = 4, x₂ = 6 and Z is still 42 — six extra units of resource 3 bought precisely ₹0 of profit. For b₃ > 24 the shadow price drops to zero. This is why "resource 3 is worth ₹1 per unit" is only true up to 24 units. A manager who bought ten more units at ₹0.80 each would earn ₹1 on the first six, nothing on the last four, and pay ₹8 for the lot — turning an apparently profitable purchase into a loss of ₹2.
x₂ = 6 > 0, so x₂ is a basic variable and we are in the harder of the two cases: its profit appears in the objective row through the whole of its tableau row. Read that row off the tableau of Problem 1 — across (x₁, x₂, s₁, s₂, s₃) it is (0, 1, 0, 1/2, 0). The non-basic variables are the three slacks s₁, s₂, s₃, carrying zⱼ − cⱼ = (0, 3/2, 1).
Writing c₂ = 5 + Δ, each non-basic column's z_k − c_k moves by Δ·α₂_k, where α₂_k is that column's entry in x₂'s row. Optimality holds as long as every one of them stays ≥ 0.
| Non-basic k | z_k − c_k | α₂_k | New value |
|---|---|---|---|
| s₁ | 0 | 0 | 0 (unaffected) |
| s₂ | 3/2 | 1/2 | 3/2 + Δ/2 |
| s₃ | 1 | 0 | 1 (unaffected) |
Only s₂ has a non-zero entry in x₂'s row, so it is the only column Δ can disturb; s₁ and s₃ have α₂_k = 0 and hold their values whatever Δ does. The one live condition is 3/2 + Δ/2 ≥ 0, giving Δ/2 ≥ −3/2 and so Δ ≥ −3.
That is a floor, not a ceiling. An upper limit could only come from a non-basic column with a negative entry in x₂'s row, and there is none — the row's non-basic entries are 0, 1/2 and 0. So Δ has no upper restriction at all.
Translate back to c₂ itself: c₂ = 5 + Δ ≥ 5 − 3 = 2. Hence c₂ ≥ 2, with no upper limit. The plan (2, 6) stays optimal however high product 2's profit climbs, and only the value of Z changes. Sensible, on reflection: making x₂ more profitable can never argue for producing less of it.
A range is worth testing at its edge. At c₂ = 2 the objective becomes 3x₁ + 2x₂. At the current corner, Z(2, 6) = 3(2) + 2(6) = 6 + 12 = 18. At the neighbouring corner, Z(4, 3) = 3(4) + 2(3) = 12 + 6 = 18. A tie — so c₂ = 2 is precisely the point where a second optimum appears, which is what the end of a range should look like ✓.
Step just past it, to c₂ = 1.9: Z(2, 6) = 6 + 11.4 = 17.4 while Z(4, 3) = 12 + 5.7 = 17.7. Now (4, 3) wins outright, so the basis really has changed the moment we leave the range, exactly as predicted ✓.
The rule needs each change measured against its own one-at-a-time range, so compute those first. For b₂ the direction is the s₂ column (1/3, 1/2, −1/3)ᵀ against basics (s₁, x₂, x₁) = (2, 6, 2). An increase Δ₂ raises s₁ and x₂ — neither can go negative — and lowers only x₁ = 2 − Δ₂/3, so the single binding condition is Δ₂ ≤ 6. Allowable increase in b₂: 6. For b₃ Problem 3 already did the work: allowable increase also 6.
b₂ rises by 2 out of an allowable 6, using 2/6 = 0.333 of its room; b₃ rises by 3 out of 6, using 3/6 = 0.500. Together they consume
So the basis holds and both shadow prices stay valid — which is exactly the permission needed to price the changes at those shadow prices rather than re-solving:
Z*_new = 36 + 2(1.5) + 3(1) = 36 + 3 + 3 = 42. Each extra unit of resource 2 is worth ₹1.50 and each extra unit of resource 3 is worth ₹1, and both rates are still in force.
Trust, then check. The new right-hand sides are b₂ = 12 + 2 = 14 and b₃ = 18 + 3 = 21. Move the basic values along both slack columns at once — the s₂ column for Δ₂ = 2 and the s₃ column for Δ₃ = 3:
s₁ = 2 + 2/3 − 3/3 = 1.667, x₂ = 6 + 2/2 = 7, x₁ = 2 − 2/3 + 3/3 = 2.333. All three are non-negative ✓, so the basis is genuinely still feasible, and Z = 3(2.333) + 5(7) = 7 + 35 = 42 ✓ — the same 42 the shadow prices predicted.
Against the original constraints: x₁ = 2.333 ≤ 4 ✓ (still slack, by 1.667), 2x₂ = 14 ≤ 14 ✓ and 3(2.333) + 2(7) = 7 + 14 = 21 ≤ 21 ✓. The same two constraints bind as before, which is another way of saying the basis did not change.
Now suppose the changes had been 5 and 5. Then 5/6 + 5/6 = 1.667 > 1, the test fails, and the honest conclusion is that you have no guarantee and must re-solve.
Re-solve, and: x₁ = 2 − 5/3 + 5/3 = 2 ≥ 0 ✓ and s₁ = 2 + 5/3 − 5/3 = 2 ≥ 0 ✓. The basis survives after all. The two increases happened to pull s₁ and x₁ in opposite directions and cancel, which the rule — adding magnitudes, never looking at directions — cannot see. So the rule is conservative: it sometimes refuses to certify a change that is perfectly safe. Failing the test is a reason to check, never a proof that anything broke.
7. Where this is used
Airline crew scheduling
Dual prices on flight legs generate only pairings with negative reduced cost — Problem 2(c) at industrial scale.
Cutting stock
Dual prices on each width drive a knapsack subproblem that invents the next cutting pattern.
Electricity markets
Locational marginal prices are shadow prices of the network balance constraints.
Capital budgeting
The price on the budget constraint is the internal hurdle rate.
Capacity expansion
The largest price names the bottleneck; ranging says how much to add.
Transfer pricing
Divisions charge each other at shadow prices, so local choices match the optimum.
8. Common mistakes
- Quoting a shadow price without its range. ₹1 per unit of resource 3 holds only for 12 ≤ b₃ ≤ 24; past 24 the price is zero.
- Treating a shadow price as an average. It is a derivative, valid only while the basis is.
- Pricing a constraint that has slack. Complementary slackness forces yᵢ* = 0.
- Expecting a finite primal beside an infeasible or unbounded dual. Impossible.
- Reading a sum above 100 % as proof the basis changed. You simply cannot conclude — re-solve.
- Mis-transposing signs. In a max primal a ≥ constraint gives yᵢ ≤ 0; an equality gives an unrestricted yᵢ.
- Confusing the ranging tests. Changing bᵢ threatens feasibility; changing cⱼ threatens optimality.
9. Practice problems
- Write the dual of min 4y₁ + 6y₂ subject to y₁ + 2y₂ ≥ 3, 3y₁ + y₂ ≥ 5, y ≥ 0.
- If a primal is unbounded, what can you say about its dual? [Ans: infeasible]
- Given slack = 5 on constraint 2, what is y₂? [Ans: 0, by complementary slackness]
- A resource costs ₹8 per unit and has shadow price ₹6. Buy or not? [Ans: do not buy]
- Verify bᵀy* = Z* for the furniture problem of L05.
- Changes use 40 %, 30 % and 20 % of their ranges. Is the basis still optimal? [Ans: 90 % ≤ 100 %, yes]
- A new product's imputed cost is ₹12 and it sells for ₹10. Introduce it? [Ans: no — reduced cost −2]
10. What you can now do
- Write down the dual of any LP and say what its variables mean. Transpose — m constraints become m variables, n variables become n constraints, b and c swap, A becomes Aᵀ, ≤ becomes ≥ — and then say out loud that yᵢ is the price of resource i, and that each dual constraint insists an activity's resources be worth at least its profit. Dualising twice returns you to the primal.
- Bound an optimum without solving to the end. Any dual-feasible y is a ceiling on the primal optimum (weak duality); at optimality the two meet, Z* = W* (strong duality); and a finite optimum on one side can never sit beside an infeasible or unbounded other side.
- Say which resources are worth paying for, without a second solve. Read the zⱼ − cⱼ entries under the slack columns of the final tableau. Complementary slackness tells you what to expect before you look: any constraint with slack left over must price at zero, and any activity you actually run must break even exactly at those prices.
- Turn prices into decisions. Buy a resource when its market price is below yᵢ; charge yᵢ as an internal transfer price; expand the resource with the largest yᵢ; and accept a new product only when its revenue beats its imputed resource cost ∑ᵢ aᵢ,new yᵢ — the reduced-cost test that column generation runs at industrial scale.
- Say how far the data may move before any of that stops being true. A right-hand side may move while x_B + Δ(B⁻¹)·ᵢ ≥ 0 keeps every basic variable non-negative — a feasibility test. An objective coefficient may move while every z_k − c_k ≥ 0 — an optimality test. Never quote a shadow price without the range it lives in; outside that range the price is a different number, and frequently zero.
- Test several changes at once, and read the result honestly. If the fractions of the allowable ranges sum to at most 1, the 100 % rule certifies that the basis and every shadow price survive. Above 1 it certifies nothing either way: re-solve, and do not report that the basis has changed.
- Get all of this out of one tableau. For the running example that single tableau yielded x* = (2, 6), y* = (0, 1.5, 1) and Z* = W* = 36, and from those alone the ₹0.90 gain on the cheap resource, the refusal at ₹2.00, the +₹1 reduced cost on the new product, the range 12 ≤ b₃ ≤ 24 with the price collapsing to zero beyond it, the range c₂ ≥ 2, and the new optimum of 42 after two simultaneous changes.