Back to the on-screen lesson ·
At an optimum, slack and price are never both positive; the price of a binding row is what one more unit is worth.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to apply complementary slackness in both directions to fix the prices of non-binding constraints and to tighten the dual constraints of positive variables, use a shadow price as the rate at which the optimum improves with extra capacity, write the optimum as a linear function of that capacity, and recover a dual solution from an optimal plan.
You can form a dual and you know that at the optimum the two values agree. This lesson says what that agreement forces about which constraints bind and which prices are positive.
A constraint's slack is its unused capacity. Complementary slackness is the rule that at an optimum, for each pair, one of the two is tight: either the slack is zero or the price is. The dual variable of a constraint is its shadow price, the rate at which the optimum improves per extra unit of that capacity.
At an optimum, for every constraint: either it binds, or its dual variable is zero. And for every variable: either it is zero in the plan, or its dual constraint holds with equality. Those two families of conditions, together with feasibility on both sides, characterise optimality exactly.
Both read as economics. A resource you are not using up would change nothing if you had one more, so it is worth nothing at the margin. A product worth making must earn at least what its inputs are worth at these prices; a product not being made is one whose inputs are worth more than it earns.
Shadow price. The dual variable of a binding constraint is the gradient of the optimal value in that constraint's capacity. So the optimum as a function of the capacity is $v + yt$: a straight line of gradient $y$ — and it is a line only while the same basis stays optimal.
Using the rule. Given one optimal solution, the conditions become equations for the other. That is how a solver reports prices without solving a second problem, and how a claimed optimum can be checked without one.
Another way: steps
Another way: example
Workshop: both resources are used up at the optimum and both products are made, so both dual constraints are equalities: $2y_1 + 3y_2 = 30$ and $5y_1 + 2y_2 = 50$, giving $y_1 = \tfrac{90}{11}$ and $y_2 = \tfrac{50}{11}$.
The rule is read as 'a binding constraint has a positive price'. It does not: it says a binding constraint may have one, and a degenerate optimum often has a binding constraint priced at zero. The other error is treating a shadow price as valid for any amount of extra capacity, which extrapolates one straight segment of a bending curve.
Someone claims $x = (20, 0)$ is optimal for the workshop. $x_1 > 0$ forces $2y_1 + 3y_2 = 30$.
A positive variable tightens its dual row.
The wood row uses only $40$ of its $100$, so it has slack, so $y_1 = 0$, giving $y_2 = 10$.
Slack forces a zero price.
Now test the other dual constraint: $5(0) + 2(10) = 20$, which is less than $50$. Dual infeasible, so the claim is false.
The check fails, with a reason.
Complementary slackness forbids slack and price both being positive; it says nothing against both being zero.
The rule is one-sided.
So yes — and it is what a degenerate optimum typically looks like: a constraint that binds and is worth nothing to relax.
At the optimum, the first constraint has $3$ of its capacity spare, the second has none, and the third has $8$ spare. The second constraint's price is $3$. Fill in the other two prices.
| Its price | |
|---|---|
| First constraint, slack $3$ | |
| Second constraint, no slack | 3 |
| Third constraint, slack $8$ |
At the optimum a constraint with capacity $75$ is using only $66$, so it has $9$ to spare. What is its dual variable?
Answer:
The optimum is $37$ and a binding constraint has shadow price $9$. Its capacity rises, and the same basis stays optimal throughout. Complete the new optimum for each rise.
One extra unit gives a, two give b, and three give c.
A primal has $5$ variables and $4$ constraints. Complementary slackness gives one condition for each of what?
The optimum is $81$ and a binding constraint has shadow price $8$. Write the optimum as a function of $t$, the number of extra units of that capacity, while the basis holds.
Answer:
The optimal plan makes both products in positive quantities, and both resources are used up. A unit of the first product takes $2$ and $5$ of the two resources and earns $11$; a unit of the second takes $5$ and $3$ and earns $18$. Find the two resource prices.
| Value | |
|---|---|
| Price of the first resource | |
| Price of the second |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
At the optimum, the first constraint has $7$ of its capacity spare, the second has none, and the third has $4$ spare. The second constraint's price is $7$. Fill in the other two prices.
| Its price | |
|---|---|
| First constraint, slack $7$ | |
| Second constraint, no slack | 7 |
| Third constraint, slack $4$ |
You can use complementary slackness to price a solution and to check a claimed optimum, and read a shadow price as a rate. Say in your own words why a constraint with capacity to spare is worth nothing at the margin.
7. Your turn: a constraint binds at the optimum and its shadow price is $0$. Is that possible?, step 2