Back to the on-screen lesson ·
Every feasible plan is a floor, every feasible price is a ceiling, and at the optimum the two meet.
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 use a feasible primal plan and a feasible dual solution to bracket the optimal value, give the two-step proof of weak duality, say what an unbounded or infeasible primal forces on its dual, and recognise a matching pair of feasible solutions as a certificate of optimality that can be checked without an algorithm.
You can form the dual of a program. This lesson is the reason for doing so: the two problems bound each other, and at the optimum the bound is exact.
Weak duality is the inequality between any feasible primal and dual values. The duality gap is the distance between the best pair in hand. Strong duality is the theorem that the gap closes at the optimum. A matching pair of feasible solutions is a certificate: a proof of optimality that can be checked without rerunning anything.
Weak duality. For any feasible $x$ and any feasible $y$, $c^{T}x \le b^{T}y$. The proof is one line: $c^{T}x \le y^{T}Ax \le b^{T}y$, where the first step multiplies the dual constraints by $x \ge 0$ and the second multiplies the primal constraints by $y \ge 0$. Non-negativity is what keeps both inequalities pointing the same way.
So every feasible plan is a floor under the optimum and every feasible dual solution is a ceiling over it. Two consequences follow immediately: an unbounded primal forces an infeasible dual, and vice versa.
Strong duality. If either problem has an optimum then so does the other, and their values are equal. This is not free — it is the theorem of the unit — and it is what makes a matching pair possible to find at all.
The certificate. A feasible $x$ and a feasible $y$ with equal values prove each other optimal, by weak duality alone. Three substitutions check it, and no trust in any algorithm is required.
Another way: steps
Another way: example
Workshop: the plan $(\tfrac{100}{11}, \tfrac{180}{11})$ is worth $\tfrac{12000}{11}$, and the prices $y = (\tfrac{90}{11}, \tfrac{50}{11})$ are worth $100y_1 + 60y_2 = \tfrac{12000}{11}$ too. Equal, so both are optimal — and that is checkable without the tableau.
Weak duality is remembered with the inequality the wrong way round, so a dual value is read as a floor. It is a ceiling for a maximisation. The second error is symmetry where there is none: an unbounded primal does force an infeasible dual, but an infeasible primal forces nothing definite, because both problems can be infeasible at once.
A solver reports the best plan so far as $920$ and the best dual bound as $1000$.
A floor and a ceiling.
The optimum lies between them, so at most $80$ of improvement remains — at most $8.7\%$.
The gap is what is unknown.
Stopping here is a decision with a stated cost, not a guess. That is what the dual bound buys.
A bound is an argument.
Weak duality says every feasible primal value is at most every feasible dual value, so $40 \le 37$ would have to hold.
The inequality fails.
It does not, so one of the two is not feasible: an arithmetic or a formulation error, and the pair has just found it.
A maximisation has a feasible plan worth $12$ and a feasible dual solution worth $19$. Fill in what is known about the optimal value.
| Value | |
|---|---|
| At least | |
| At most | |
| The gap still open |
A maximisation has a feasible plan worth $14$ and a feasible dual solution worth $18$. Give the interval the optimal value must lie in.
This task has no paper form; do it on a device.
Build the proof of weak duality: for any feasible $x$ of the primal and any feasible $y$ of its dual, $c^{T}x \le b^{T}y$.
This task has no paper form; do it on a device.
A maximisation is unbounded: it has feasible plans worth more than $81$, more than twice $81$, and so on without limit. What must be true of its dual?
A primal maximisation is solved and reports one of three statuses. Match each to what it forces on the dual.
| The dual has an optimum, also $66$ | The dual is infeasible | The dual is unbounded or infeasible | |
|---|---|---|---|
| The primal has an optimum of $66$ | |||
| The primal is unbounded | |||
| The primal is infeasible |
You hold a feasible plan worth $90$ and a feasible dual solution also worth $90$, for a maximisation. How many feasible plans are worth more than $90$?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A maximisation has a feasible plan worth $49$ and a feasible dual solution worth $55$. Fill in what is known about the optimal value.
| Value | |
|---|---|
| At least | |
| At most | |
| The gap still open |
You can bracket an optimal value between a feasible plan and a feasible dual solution, and recognise a matching pair as a proof. Say in your own words why non-negativity is needed in the proof of weak duality.
7. Your turn: a feasible plan is worth $40$ and a feasible dual solution is worth $37$, for a maximisation. What has gone wrong?, step 2