QBUS2310 Chap.6 Duality, Certificates and Shadow Prices
Duality, Certificates and Shadow Prices
Duality gives a second optimisation model whose feasible values bound the primal objective. Matching primal and dual values can certify optimality without searching every feasible plan. Dual variables also quantify local resource value, but a shadow price applies only while the active basis remains valid. Farkas-type alternatives turn infeasibility into a verifiable linear certificate.
These terms let a reader match a primal candidate against its dual certificate before declaring optimality. Dual Problem is a companion optimisation model that prices or combines the primal constraints. Weak Duality is the rule that every feasible dual value bounds every feasible primal value in the appropriate direction. Strong Duality is equality of optimal primal and dual values under the relevant conditions.
Complementary Slackness is conditions linking positive variables with binding constraints across primal and dual models. Shadow Price is the local marginal change in optimal value from changing a resource bound. Farkas Certificate is a vector of multipliers that proves a linear constraint system is infeasible.
The primal-dual pair above is verified for a matching bound: The primal and dual candidates both have value 13, so neither can be improved. Complementary slackness is consistent because both primal resource constraints bind and both primal variables are positive.
What this chapter covers
- 01
Primal and dual viewpoints
- 02
Weak duality bounds
- 03
Strong duality conditions
- 04
Complementary slackness
- 05
Dual feasibility
- 06
Farkas certificates
- 07
Shadow prices
- 08
Range of validity
Duality, Certificates and Shadow Prices worked example
- +1Assign nonnegative dual variables u and v to the two resource constraints.
- +1The dual minimises 5u+8v subject to u+2v at least three and u+v at least two.
- +1Choose u=1 and v=1. Both dual inequalities hold and the dual objective equals thirteen.
- +1The primal point (3,2) is feasible with value thirteen. Equal feasible values certify optimality by weak duality.
Key terms
- Dual Problem
- A companion optimisation model that prices or combines the primal constraints.
- Weak Duality
- The rule that every feasible dual value bounds every feasible primal value in the appropriate direction.
- Strong Duality
- Equality of optimal primal and dual values under the relevant conditions.
- Complementary Slackness
- Conditions linking positive variables with binding constraints across primal and dual models.
- Shadow Price
- The local marginal change in optimal value from changing a resource bound.
- Farkas Certificate
- A vector of multipliers that proves a linear constraint system is infeasible.
Duality, Certificates and Shadow Prices FAQ
Why does primal and dual viewpoints matter?
Dual Problem: A companion optimisation model that prices or combines the primal constraints. Weak Duality: The rule that every feasible dual value bounds every feasible primal value in the appropriate direction. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How can I check complementary slackness?
Weak Duality: The rule that every feasible dual value bounds every feasible primal value in the appropriate direction. Strong Duality: Equality of optimal primal and dual values under the relevant conditions. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
What separates dual problem from weak duality?
Strong Duality: Equality of optimal primal and dual values under the relevant conditions. Complementary Slackness: Conditions linking positive variables with binding constraints across primal and dual models. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Which error is most likely around farkas certificates?
Complementary Slackness: Conditions linking positive variables with binding constraints across primal and dual models. Shadow Price: The local marginal change in optimal value from changing a resource bound. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How should I practise range of validity?
Shadow Price: The local marginal change in optimal value from changing a resource bound. Farkas Certificate: A vector of multipliers that proves a linear constraint system is infeasible. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Exam move
Use a certificate table: primal feasibility, dual feasibility, objective equality, then complementary slackness. Do not interpret a dual value as a permanent price outside its valid basis range. Rehearse the chapter method in this order: Assign nonnegative dual variables u and v to the two resource constraints. The dual minimises 5u+8v subject to u+2v at least three and u+v at least two.
Choose u=1 and v=1. Both dual inequalities hold and the dual objective equals thirteen. The primal point (3,2) is feasible with value thirteen. Equal feasible values certify optimality by weak duality.
Working through Duality, Certificates and Shadow Prices in QBUS2310? Sia is AskSia’s AI Mathematics tutor — ask any QBUS2310 Duality, Certificates and Shadow Prices question and get a clear, step-by-step explanation grounded in how QBUS2310 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
