Duality in Linear Programming: How to Write the Dual of an LPP (With Examples)

Every linear programming problem, called the primal, has a partner problem called the dual. The two are built from the same numbers, and when both have optimal solutions their optimal objective values are equal. Duality explains shadow prices, gives a way to check an answer, and underlies the dual simplex method.

This guide shows how to write the dual of any LPP, states the main theorems, and works through two examples where the primal and dual answers are checked against each other.

Rules for Writing the Dual

For a primal in the usual form, maximize with ≤ constraints and non-negative variables, the dual is:

• Minimize instead of maximize.
• One dual variable y_i for each primal constraint.
• One dual constraint for each primal variable.
• The primal RHS values become the dual objective coefficients.
• The primal objective coefficients become the dual RHS values.
• The constraint matrix is transposed: rows become columns.
• The dual constraints are ≥, and the dual variables are ≥ 0.

For problems that are not in this form, use the correspondence table:

Primal (maximize)	Dual (minimize)
Constraint i is ≤	y_i ≥ 0
Constraint i is ≥	y_i ≤ 0
Constraint i is =	y_i unrestricted
Variable x_j ≥ 0	Dual constraint j is ≥
Variable x_j ≤ 0	Dual constraint j is ≤
Variable x_j unrestricted	Dual constraint j is =

Read the table from right to left to go from a minimization primal to its maximization dual. The dual of the dual is always the original primal.

Example 1: Maximization Primal

Primal

• Maximize Z = 12x1 + 16x2
• Subject to 10x1 + 20x2 ≤ 120 and 8x1 + 8x2 ≤ 80
• x1, x2 ≥ 0

Writing the dual. There are two constraints, so two dual variables, y1 and y2. There are two primal variables, so two dual constraints. The RHS values 120 and 80 become the dual objective; the objective coefficients 12 and 16 become the dual RHS; the column of x1 (10, 8) becomes the first dual constraint, and the column of x2 (20, 8) becomes the second.

Dual

• Minimize W = 120y1 + 80y2
• Subject to 10y1 + 8y2 ≥ 12 and 20y1 + 8y2 ≥ 16
• y1, y2 ≥ 0

Solutions. The primal optimum is x1 = 8, x2 = 2 with Z = 128. This is solved step by step in how to solve an LPP by the simplex method. The dual optimum is y1 = 2/5, y2 = 1 with W = 120(2/5) + 80(1) = 48 + 80 = 128. The two values are equal, as the strong duality theorem says they must be.

The dual values also appear in the final primal tableau: they are the Zj entries under the slack columns, 2/5 and 1. They are the shadow prices of the two resources.

Example 2: Minimization Primal

Primal (a diet problem)

• Minimize Z = 20x1 + 30x2
• Subject to 2x1 + x2 ≥ 8 and x1 + 2x2 ≥ 10
• x1, x2 ≥ 0

For a minimization primal with ≥ constraints, the dual is a maximization with ≤ constraints.

Dual

• Maximize W = 8y1 + 10y2
• Subject to 2y1 + y2 ≤ 20 and y1 + 2y2 ≤ 30
• y1, y2 ≥ 0

Primal solution. The corner points of the primal feasible region are (0, 8), (2, 4) and (10, 0), with costs 240, 160 and 200. The minimum is Z = 160 at x1 = 2, x2 = 4.

Dual solution. The dual corners are (0, 0), (10, 0), (0, 15) and the intersection of 2y1 + y2 = 20 with y1 + 2y2 = 30, which is (10/3, 40/3). The objective values are 0, 80, 150 and 8(10/3) + 10(40/3) = 480/3 = 160. The maximum is W = 160, equal to the primal minimum.

Interpretation. In a diet problem the dual variables are the value of one unit of each nutrient. y1 = 10/3 and y2 = 40/3 say how much the minimum cost would rise if each nutrient requirement went up by one unit.

The Duality Theorems

Weak duality. For any feasible primal solution and any feasible dual solution of a maximization primal, Z ≤ W. Every feasible dual solution gives an upper bound on the primal. For example, y = (1, 1) is feasible in the dual of Example 1 (10 + 8 = 18 ≥ 12 and 20 + 8 = 28 ≥ 16), giving W = 200, so the primal can never exceed 200.

Strong duality. If the primal has an optimal solution, so does the dual, and the optimal values are equal. Both examples above show this: 128 = 128 and 160 = 160.

Unbounded and infeasible cases. If the primal is unbounded, the dual is infeasible. If the primal is infeasible, the dual is either unbounded or infeasible.

Complementary Slackness

At the optimum, for every constraint, either the constraint is binding (no slack) or its dual variable is zero, and the same holds in the other direction for the variables.

In Example 1, both x1 = 8 and x2 = 2 are positive, so both dual constraints must be binding: 10(2/5) + 8(1) = 12 ✓ and 20(2/5) + 8(1) = 16 ✓. Both y values are positive, so both primal constraints must be binding: 10(8) + 20(2) = 120 ✓ and 8(8) + 8(2) = 80 ✓.

Complementary slackness is a fast way to check an answer: if you know the primal optimum, you can often find the dual optimum by solving only the binding equations.

Why Duality Matters

• Shadow prices: dual values tell you what one more unit of each resource is worth.
• Checking answers: matching primal and dual objective values prove that a solution is optimal.
• Choosing the easier problem: if the primal has many constraints and few variables, the dual has few constraints and many variables, which can be quicker to solve.
• The dual simplex method works on the primal tableau while keeping dual feasibility. See primal vs dual simplex method for how the two methods differ.

Common Mistakes

• Forgetting to transpose. The dual constraints come from the columns of the primal, not the rows.
• Wrong constraint direction. A maximization primal with ≤ constraints always gives a minimization dual with ≥ constraints.
• Ignoring the sign rules for = constraints (free dual variable) and for constraints that point the “wrong” way.

Check Your Answer

Solve the primal with the simplex method calculator with steps, then solve the dual you wrote in the same calculator. If the two optimal objective values match, your dual is correct.