Linear Programming Duality Explained with Worked Examples

The primal problem has the dual . When both are feasible their optimal values are equal (strong duality), and any dual-feasible value bounds the primal from above (weak duality).

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Linear programming duality means

Primal: maximise subject to , , . The optimum is at the vertex with value 12 (the optimum at a vertex). Dual: minimise subject to , , ; the point is feasible with value 12, the same. A second problem: maximise subject to , : optimum with value 21; the dual optimum , gives .

The dual variables are shadow prices: in the first problem says each extra unit of the first resource raises the optimum by 3. Complementary slackness links the two solutions: a constraint with positive dual price is tight at the optimum. Weak duality: any feasible dual value (e.g. gives ) is an upper bound on the primal optimum 12.

Duality is the linear special case of the KKT conditions (KKT conditions) and of Lagrangian duality. It explains the stopping rule of the simplex method (simplex pivot, reading the simplex tableau) and the max-flow min-cut theorem (max-flow min-cut), as well as two-player zero-sum games (optimal mixed strategies).

What is it used for?

Every linear programme has a twin whose optimal value is the same.

How to use linear programming duality

  1. Write the primal in the form max c·x, Ax ≤ b, x ≥ 0.
  2. Form the dual: min b·y, Aᵀy ≥ c, y ≥ 0.
  3. Solve either (they have the same value).
  4. Read the dual values as shadow prices.

Graph

Feasible region of x + y ≤ 4, x + 3y ≤ 6 with optimum 12 at (4, 0)optimum 12vertex (3, 1): 11-0.500.511.522.533.544.55-0.500.511.522.53Feasible region of x + y ≤ 4, x + 3y ≤ 6 with optimum 12 at (4, 0)xyGraph with x from -0.5 to 5 and y from -0.5 to 3. Shows feasible region (5); point optimum 12 at (4, 0); point vertex (3, 1): 11 at (3, 1).

The best vertex gives 3x + 2y = 12, matching the dual value.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: primal optimum

Find the optimum of max , , .

Worked example
Answer
1212
  1. Vertex
  2. Value

Example 2: dual value

Evaluate the dual objective at .

Worked example
Answer
1212
  1. Feasible

Example 3: second problem

Find the common value for max , , .

Worked example
Answer
2121
  1. Primal at (3, 1.5)
  2. Dual at (0.75, 0.5)

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Primal

max 3x + 2y s.t. x + y ≤ 4, x + 3y ≤ 6: optimum (4, 0), value 12

Check vertices.

Dual

min 4u + 6w s.t. u + w ≥ 3, u + 3w ≥ 2: optimum (3, 0), value 12

Same value.

Weak duality

any feasible dual value ≥ any feasible primal value

E.g. dual (3, 0.5): 15.

Strong duality

optimal values are equal

12 = 12.

Word problems

The dual of max cᵀx s.t. Ax ≤ b, x ≥ 0 is min bᵀy s.t. Aᵀy ≥ c, y ≥ 0. Weak duality gives dual ≥ primal; at optimality the two values are equal.

The primal optimum

Maximise 3x + 2y with x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0.

  1. Vertices(0,0), (4,0), (3,1), (0,2)
  2. Values0, 12, 11, 4
  3. Check: maximum 12 ✓12.

The dual

Minimise 4u + 6w with u + w ≥ 3, u + 3w ≥ 2.

  1. Try (3, 0)3 ≥ 3 ✓, 3 ≥ 2 ✓
  2. Value12
  3. Check: equals the primal ✓12.

Weak duality Higher

Evaluate the dual objective at the feasible point (3, 0.5).

  1. 4 × 3 + 6 × 0.5
  2. Check: 15 ≥ 12 ✓15.

Check a vertex Higher

Evaluate the primal at (3, 1).

  1. 3 × 3 + 2 × 1
  2. Check: 11 < 12 ✓11.

Common mistakes

Maximising the dual

max in the dual ✗

minimise the dual of a max problem ✓

Directions swap.

Wrong inequality direction

Aᵀy ≤ c ✗

Aᵀy ≥ c ✓

Dual constraints reverse.

Mixing variables

x in the dual ✗

dual variables y ✓

One per primal constraint.

Expecting equality for any feasible points

values equal ✗

equal only at optimality ✓

Weak duality is an inequality.

Exam tips

  1. Max ↔ min.
  2. Constraints flip.
  3. One dual variable per constraint.
  4. Weak duality: dual ≥ primal.
  5. Optimal values equal.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Primal at (4, 0): 3x + 2y Foundation

12

2. Primal at (0, 2): 3x + 2y Foundation

4

3. Dual at (3, 0): 4u + 6w Foundation

12

4. Dual at (2.5, 0.5): 4u + 6w Higher

13

5. Check u + w ≥ 3 at (2.5, 0.5) Higher

3

6. Check u + 3w ≥ 2 at (2.5, 0.5) Higher

4

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Primal problem
The original LP.
Dual problem
The associated LP.
Weak duality
Dual ≥ primal.
Strong duality
Optimal values equal.
Feasible region
All allowed points.
Shadow price
Dual variable value.

Frequently asked questions

What is LP duality?

Every LP has a dual whose optimum equals its own.

What is weak duality?

Any dual feasible value bounds the primal from above.

What are shadow prices?

The dual variables.

How is the dual formed?

Swap max/min, constraints and variables.

Which page covers the simplex pivot?

simplex pivot.

Which page covers KKT?

KKT conditions.

More in Numerical methods and optimisation and the formula sheets.