Primal
max 3x + 2y s.t. x + y ≤ 4, x + 3y ≤ 6: optimum (4, 0), value 12
Check vertices.
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).
This page is easier if you are comfortable with:
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).
Every linear programme has a twin whose optimal value is the same.
The best vertex gives 3x + 2y = 12, matching the dual value.
These examples are worked by hand, step by step, so you can compare your own working.
Find the optimum of max , , .
Evaluate the dual objective at .
Find the common value for max , , .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
max 3x + 2y s.t. x + y ≤ 4, x + 3y ≤ 6: optimum (4, 0), value 12
Check vertices.
min 4u + 6w s.t. u + w ≥ 3, u + 3w ≥ 2: optimum (3, 0), value 12
Same value.
any feasible dual value ≥ any feasible primal value
E.g. dual (3, 0.5): 15.
optimal values are equal
12 = 12.
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.
Maximise 3x + 2y with x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0.
Minimise 4u + 6w with u + w ≥ 3, u + 3w ≥ 2.
Evaluate the dual objective at the feasible point (3, 0.5).
Evaluate the primal at (3, 1).
max in the dual ✗
minimise the dual of a max problem ✓
Directions swap.
Aᵀy ≤ c ✗
Aᵀy ≥ c ✓
Dual constraints reverse.
x in the dual ✗
dual variables y ✓
One per primal constraint.
values equal ✗
equal only at optimality ✓
Weak duality is an inequality.
Try each one on paper, then open the answer. Use the solver above to see the full working.
12
4
12
13
3
4
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Every LP has a dual whose optimum equals its own.
Any dual feasible value bounds the primal from above.
The dual variables.
Swap max/min, constraints and variables.
simplex pivot.
KKT conditions.
More in Numerical methods and optimisation and the formula sheets.