MATH2070 Chap.4 Duality and Shadow Prices
Duality and Shadow Prices
Duality reads a linear programme from the perspective of resource values rather than activity quantities. Weak duality places every primal objective below every dual objective under the course maximisation convention. Strong duality equates finite optimal values, making a feasible primal-dual equality an immediate certificate.
Complementary slackness links unused resources to zero prices and positive activities to tight dual requirements. Shadow prices are local marginal values whose interpretation depends on the current optimal basis. Dimensions provide an early construction check: primal constraints correspond to dual variables and primal variables correspond to dual constraints.
Sign rules follow from optimisation directions and variable restrictions rather than from one memorised template. A duality gap bounds the unknown optimum even before either candidate is final. When the gap closes for feasible solutions, optimality follows without enumerating other plans.
Sensitivity interpretation also requires units and a stability range, because the current multiplier need not remain valid after a large resource change alters the optimal basis.
What this chapter covers
- 01
Primal-dual construction
- 02
Weak duality bounds
- 03
Strong duality equality
- 04
Complementary slackness
- 05
Shadow prices
- 06
Sensitivity limits
Worked example · free
Certify an optimum with dual prices
- 1Write the dual by dimensions and signs.
- 1Use slackness to solve prices.
- 1Verify primal and dual feasibility.
- 1Match the objective values.
Key terms
- Dual programme
- The paired optimisation problem that provides bounds on the primal objective.
- Duality gap
- The difference between a dual feasible objective and a primal feasible objective.
- Complementary slackness
- The optimality relation that multiplies each slack by its paired variable to obtain zero.
- Shadow price
- The local objective change per extra unit of a named resource.
- Duality gap
- The difference between dual and primal objective values for feasible candidates under the standard maximisation pairing. It bounds the unresolved improvement, and a zero gap certifies that both candidates are optimal.
- Sensitivity range
- The interval of parameter changes over which the current basis remains optimal and its shadow price retains the same marginal interpretation. Beyond that interval, another constraint or activity may become decisive. Large proposed changes therefore require a fresh optimisation rather than unlimited extrapolation of one multiplier.
Duality and Shadow Prices FAQ
How can duality prove optimality without another simplex run?
Find one primal-feasible decision and one dual-feasible price vector with equal objective values. Weak duality says no feasible objective can cross that common value, so both candidates are optimal.
Does a binding constraint always have a positive shadow price?
No. Positive price implies zero slack, but a constraint can bind with zero price because of redundancy or local geometry. Complementary slackness does not make every implication reversible.
Can a shadow price be used for any capacity change?
No. It is a local rate valid while the current basis remains optimal. A large right-hand-side change can alter the active set, at which point the marginal value must be recomputed.
Exam move
Start each dual problem with dimensions. If the primal has m constraints and n variables, the dual has m variables and n constraint rows. Create a table linking every primal row to one dual variable and every primal variable to one dual constraint. Then add sign rules from the primal optimisation direction, constraint types and variable restrictions.
This method is slower than pattern recall on the first attempt but much more reliable when equalities or free variables appear. Practise weak-duality bounds before full construction. Given one primal-feasible plan and one dual-feasible price vector, compute both objectives, place the primal and dual values on the correct sides of the optimum and state the remaining gap. Next, design small cases where the objectives match.
Verify both feasibilities explicitly; equality then becomes an optimality certificate rather than an unsupported numerical coincidence. For complementary slackness, make paired statements instead of quoting the theorem abstractly. Positive slack in a primal constraint forces its matching dual variable to zero, while a positive primal variable forces the corresponding dual constraint to bind.
Work in both directions and include cases where both members are zero, since complementary slackness does not assert a strict either-or relationship. Use these equations to recover a candidate solution, then return to primal and dual feasibility before claiming optimality. Interpret every multiplier with units.
Divide objective units by the resource units of its constraint, identify whether the resource binds, and describe the value as a local marginal rate while the current basis remains optimal. Do not extrapolate it across an unlimited capacity change. A weekly review should include one dual conversion, one bound, one complementary-slackness recovery and one sensitivity explanation.
Mark errors as structural, sign-related or interpretive so that later practice targets the exact source rather than repeating more of the same arithmetic.
Working through Duality and Shadow Prices in MATH2070? Sia is AskSia’s AI Mathematics tutor — ask any MATH2070 Duality and Shadow Prices question and get a clear, step-by-step explanation grounded in how MATH2070 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
