Duality and Shadow Prices in Linear Programming

Understand Duality and Shadow Prices

Key rules to remember

Primal to dual: objective

Max Z = c1x1 + ... + cnxn ↔ Min W = b1y1 + ... + bmym

Maximisation primal gives a minimisation dual, and the reverse. Dual objective coefficients are the primal right-hand sides (b values).

Primal to dual: constraints

Number of dual constraints = number of primal variables; number of dual variables = number of primal constraints

Each primal constraint gives one dual variable. Each primal variable gives one dual constraint. The dual's right-hand sides are the primal's objective coefficients (c values).

Transpose rule

Dual coefficient matrix = transpose of primal coefficient matrix (rows become columns)

The coefficient of xj in constraint i of the primal becomes the coefficient of yi in constraint j of the dual.

Standard pair (max, ≤)

Primal: Max Z = cx, Ax ≤ b, x ≥ 0 ↔ Dual: Min W = by, Aᵀy ≥ c, y ≥ 0

Put the primal in this form first. For a min primal with ≥ constraints, the dual is a max with ≤ constraints.

Handling = and ≥ in a max primal

A ≥ constraint: multiply by -1 to get ≤ form. An = constraint: gives a dual variable unrestricted in sign (or write it as two inequalities, ≤ and ≥).

Convert ≥ constraints before forming the dual. An unrestricted primal variable gives an = constraint in the dual.

Strong duality

Optimal Z (primal) = Optimal W (dual)

Holds when both problems have optimal solutions. Use it as a check on your answer.

Shadow price

Shadow price of resource i = yi* = ΔZ ÷ Δbi

Change in optimal objective per unit change in resource i, valid only within the range where the optimal basis stays the same.

Complementary slackness

If slack in constraint i > 0, then yi* = 0. If yi* > 0, then constraint i is binding.

Likewise, if xj* > 0 then the j-th dual constraint holds as an equality.

How to solve Duality and Shadow Prices questions

1. 1Write the primal clearly: objective, constraints, and non-negativity. Label the constraints by resource (machine hours, labour hours, material).
2. 2Bring it to standard form. For a maximisation, all constraints should be ≤. For a minimisation, all should be ≥. Multiply by -1 where needed. An = constraint needs no conversion: its dual variable is unrestricted in sign (or you can write it as two inequalities, ≤ and ≥).
3. 3Create one dual variable (y1, y2, ...) for each primal constraint, in the same order.
4. 4Build the dual objective: swap Max with Min (or the reverse) and use the b values (right-hand sides) as coefficients of the y variables.
5. 5Build one dual constraint per primal variable using the transposed coefficients. Use ≥ for a max primal and ≤ for a min primal, with the primal c values on the right-hand side. Add y ≥ 0, except for the variable of an = constraint, which is unrestricted.
6. 6Obtain the optimal values. Either solve the dual graphically or by simplex, or read them from the Zj row under the slack columns of the final simplex table of a maximisation problem with ≤ constraints.
7. 7Check that optimal Z equals optimal W. Then interpret: state each shadow price in rupees per unit of that resource, and identify resources with zero shadow price as having spare capacity.
8. 8Give the decision: compare any offered price for extra resource with its shadow price and recommend accordingly.

Quickest way: Transpose and read: dual in under two minutes

Common mistakes in Duality and Shadow Prices

• Not converting the primal to standard form before writing the dual.

  Students apply the transpose rule straight away to a max problem with a ≥ constraint.

  Fix: For a max problem, make every constraint ≤ first (multiply a ≥ constraint by -1). For a min problem, make every constraint ≥. Then dualise.

• Using the wrong inequality direction in the dual.

  Students copy the primal's sign instead of reversing it.

  Fix: Max primal with ≤ gives a min dual with ≥. Min primal with ≥ gives a max dual with ≤. Say it aloud once before writing.

• Mixing up the c and b values.

  The roles swap between the two problems and the swap is easy to forget.

  Fix: The primal's right-hand sides become the dual's objective coefficients. The primal's objective coefficients become the dual's right-hand sides.

• Stating a shadow price as the cost of the resource or as the profit per unit of product.

  The word 'price' suggests a purchase price.

  Fix: A shadow price is the increase in optimal profit (contribution) from one extra unit of the resource. It is what the resource is worth at the margin, over and above any cost already deducted in the contribution figures.

• Giving a positive shadow price to a resource that has unused capacity.

  Students read the dual value without checking the slack in the primal's optimal solution.

  Fix: Use complementary slackness. If the primal optimum leaves slack in a constraint, its shadow price is zero.

• Applying a shadow price to any size of change in the resource.

  The value looks like a fixed rate.

  Fix: State that the shadow price is valid only within the range over which the current set of binding constraints stays optimal. Beyond it, recompute.

Worked examples