The core idea is that a maximization primal often has a minimization dual, with constraints and variables switching roles. Weak duality says any feasible dual solution bounds any feasible primal solution, while strong duality says the optimal values are equal when both optimal solutions exist. Complementary slackness links primal slack to dual variables and dual slack to primal variables, making it a powerful tool for finding or verifying optima.
Key Facts
- For the primal max c^T x subject to Ax <= b and x >= 0, the dual is min b^T y subject to A^T y >= c and y >= 0.
- For the primal min c^T x subject to Ax >= b and x >= 0, the dual is max b^T y subject to A^T y <= c and y >= 0.
- Weak duality states that for any feasible primal x and feasible dual y in a max primal and min dual pair, c^T x <= b^T y.
- Strong duality states that if a primal linear program has a finite optimal solution, then its dual also has a finite optimal solution and c^T x* = b^T y*.
- A primal <= constraint produces a nonnegative dual variable in a maximization primal standard form.
- A primal variable x_j >= 0 produces a dual constraint of the form column_j(A)^T y >= c_j in a maximization primal standard form.
- Complementary slackness for max Ax <= b says y_i(b_i - A_i x) = 0 for each primal constraint i.
- Complementary slackness for max Ax <= b says x_j((A^T y)_j - c_j) = 0 for each primal variable j.
Vocabulary
- Primal problem
- The original linear programming problem from which the related dual problem is constructed.
- Dual problem
- A linear program formed from the primal by exchanging the roles of constraints and variables.
- Weak duality
- The principle that every feasible solution of one problem gives a bound on the objective value of the other problem.
- Strong duality
- The theorem that primal and dual optimal objective values are equal when a finite optimum exists.
- Complementary slackness
- A set of conditions stating that each constraint slack is paired with a zero multiplier or each positive variable has a tight dual constraint.
- Shadow price
- The optimal dual variable value that measures the marginal change in the objective value caused by changing a resource limit.
Common Mistakes to Avoid
- Reversing the inequality directions incorrectly is wrong because the sign of each variable and the primal constraint type determine the dual inequality.
- Forgetting to transpose the constraint matrix is wrong because dual constraints use A^T, so primal rows become dual variables and primal columns become dual constraints.
- Assuming weak duality proves optimality by itself is wrong because it only gives a bound unless the primal and dual objective values match.
- Ignoring complementary slackness is wrong because it provides necessary equations that identify which constraints are tight at optimality.
- Treating every dual variable as nonnegative is wrong because equality constraints and unrestricted variables create dual variables or constraints with different sign rules.
Practice Questions
- 1 Write the dual of the primal problem: maximize 3x1 + 2x2 subject to x1 + x2 <= 4, 2x1 + x2 <= 5, x1 >= 0, x2 >= 0.
- 2 For the primal maximize 4x1 + x2 subject to x1 + 2x2 <= 6, 3x1 + x2 <= 9, x1 >= 0, x2 >= 0, verify whether x = (2, 1) and y = (1, 1) satisfy weak duality.
- 3 Use complementary slackness to test whether x = (1, 3) and y = (2, 0) can both be optimal for a primal max problem with Ax <= b if b - Ax = (0, 4).
- 4 Explain why a positive optimal shadow price means the corresponding primal resource constraint should be tight at the optimum.
Understanding Duality in Linear Programming
A useful way to understand a dual problem is to treat each primal constraint as a limited resource. In a production model, constraints may represent labor hours, machine time, material, or a budget. The dual variable attached to a resource is its implied value per extra unit.
It is not a market price chosen in advance. It is a price that makes the resource limits consistent with the best production plan. The dual objective totals the value assigned to all available resources.
A feasible set of dual prices must value the resources used by every product at least as highly as that product's profit contribution. Otherwise, producing that product would appear to create profit from resources valued too cheaply.
This resource interpretation explains why the direction of inequalities matters. A limit written as less than or equal to describes an upper bound on use. In a maximization setting, relaxing such a limit cannot make the best objective value worse.
Its resource value is therefore nonnegative. Other constraint directions lead to different sign rules because changing the right hand side has a different effect on what is allowed. Free variables require special care.
A variable that can be positive or negative corresponds to an equality condition in the other problem. Students should not memorize sign tables without checking what each restriction means. Rewriting a model into a clear standard form before building its dual prevents many errors.
Complementary slackness gives a practical reading of the final solution. If a resource is left unused, one more unit of it has no value at the optimum, so its dual variable must be zero. If a dual variable is positive, the related resource constraint must be tight.
On the variable side, if a product is produced in a positive amount, its dual condition must hold exactly. Its profit contribution matches the value of resources it consumes.
If a product's resource value is strictly greater than its profit contribution, producing it is not worthwhile, so its primal amount must be zero. These rules often let students solve small problems by combining active constraints with a few zero conditions.
Shadow prices are local sensitivity results, not permanent promises. A positive shadow price estimates how much the optimal objective changes when one right hand side increases by one unit, provided the current optimal basis stays valid. A large change can alter which constraints bind, causing the shadow price to change.
This is why sensitivity reports include allowable ranges. In real settings, this helps a manager compare the value of overtime, extra storage, or another unit of raw material. When checking coursework, first confirm feasibility, then match the objective values, then test complementary slackness.
Be alert for multiple optimal solutions and degeneracy. A binding constraint can still have a zero dual value, so tightness alone does not prove that a resource is valuable.