Duality

At a Glance

• Frequency: 4 sub-parts across 4 of 13 years (2019, 2021, 2024, 2025)
• Priority tier: T3
• Marks (count): 10 (1), 15 (3)
• Average solve time: ~11 min
• Difficulty mix: medium 3, easy 1
• Section: A | Dominant type: computation

Why This Chapter Matters

Every linear program has a paired “dual” problem, and UPSC has tested three distinct uses of that pairing: forming the dual from scratch (2021), solving a problem by working through the dual (2024, 2025), and using complementary slackness to certify that a given basis is not optimal (2019). The questions carry 10–15 marks and are entirely algorithmic — there is no heavy computation, only careful bookkeeping of signs and direction. Mastering the four conversion rules (constraint type → dual variable sign, variable type → dual constraint type) and the two complementary-slackness conditions is sufficient to score full marks.

Minimum Theory

Primal–Dual Correspondence. Given a primal minimisation $\min\; c^\top x$ subject to $Ax \ge b$, $x \ge 0$, the dual is $\max\; b^\top w$ subject to $A^\top w \le c$, $w \ge 0$. The number of dual variables equals the number of primal constraints; the number of dual constraints equals the number of primal variables. The conversion rule for mixed-constraint problems: a $\ge$-constraint in a Min primal gives a dual variable $w_i \ge 0$; a $\le$-constraint gives $w_i \le 0$; an equality constraint gives $w_i$ unrestricted. Symmetrically, a non-negative primal variable $x_j \ge 0$ gives a $\le c_j$ dual constraint, while an unrestricted $x_j$ gives a $= c_j$ equality constraint.

Weak and Strong Duality. For any primal-feasible $x$ and dual-feasible $w$, the weak duality inequality $c^\top x \ge b^\top w$ always holds. At optimality, the strong duality theorem guarantees equality: $c^\top x^* = b^\top w^*$. Consequence: if the dual is infeasible while the primal is feasible, the primal objective is unbounded (no finite optimum).

Complementary Slackness. At optimality, two conditions must hold simultaneously: (i) for each primal variable $x_j$, either $x_j = 0$ or the $j$-th dual constraint is binding ($c_j - a_j^\top w = 0$); (ii) for each dual variable $w_i$, either $w_i = 0$ or the $i$-th primal constraint is binding ($a_i^\top x - b_i = 0$). These conditions provide an optimality test: given a candidate primal basis, read off the implied $w$ by setting binding dual constraints to equality; if any remaining dual constraint is violated, the basis is not optimal.

Question Archetypes

solve-via-dual (2 question(s); 2024, 2025)

Recognition Cues — The question phrase is “using the duality principle, solve…” or “apply the principle of duality to solve…”. The primal usually has three or more variables (hard to solve graphically) but only two constraints, so the dual has only two variables and can be solved graphically. Be alert for the case where the dual is infeasible — that signals the primal is unbounded, which is itself the answer.

Solution Template

1. Write the primal in standard form for duality. For a Min problem with $\ge$ constraints, keep as-is. For a Max problem with $\le$ constraints, keep as-is. For mixed constraints, convert $\le$ to $\ge$ by multiplying by $-1$.
2. Pair each primal constraint with a dual variable $y_i \ge 0$, each primal variable with a dual constraint. Write the dual objective and constraints.
3. Solve the dual (typically a 2-variable LP) graphically: find all vertices of the dual feasible region, evaluate the objective at each, identify the optimum.
4. If the dual is infeasible, invoke the duality theorem: primal is unbounded. Stop.
5. Otherwise, at the dual optimum $(y_1^*, y_2^*)$, apply complementary slackness to recover the primal optimum: a slack dual constraint forces the corresponding primal variable to zero; a positive dual variable forces the corresponding primal constraint to be binding. Solve the resulting system.
6. Verify: primal objective $=$ dual objective at the recovered solution.

Worked Example(s)

2024 Paper 2, 2024-P2-Q3c (15 marks)

Using the duality principle, solve: $\min z = 4x_1 + 3x_2 + x_3$ subject to $x_1 + 2x_2 + 4x_3 \ge 12$, $3x_1 + 2x_2 + x_3 \ge 8$, $x_1, x_2, x_3 \ge 0$.

Step 1 — Form the dual. Primal is Min with $\ge$ constraints; dual is Max with $\le$ constraints. With dual variables $y_1, y_2 \ge 0$:

$\max\; w = 12y_1 + 8y_2$

subject to:

$y_1 + 3y_2 \le 4, \quad 2y_1 + 2y_2 \le 3, \quad 4y_1 + y_2 \le 1, \quad y_1, y_2 \ge 0.$

Step 2 — Solve the dual graphically. The third constraint $4y_1 + y_2 \le 1$ is the most restrictive. Enumerate vertices of the feasible region:

• $(0, 0)$: $w = 0$.
• $(1/4, 0)$ (intersection of $4y_1 + y_2 = 1$ with $y_2 = 0$): check $y_1 + 3y_2 = 1/4 \le 4$ ✓, $2y_1 + 2y_2 = 1/2 \le 3$ ✓. So $w = 12(1/4) = 3$.
• $(0, 1)$ (intersection of $4y_1 + y_2 = 1$ with $y_1 = 0$): check $y_1 + 3y_2 = 3 \le 4$ ✓, $2y_1 + 2y_2 = 2 \le 3$ ✓. So $w = 8(1) = 8$.
• Intersections of $4y_1 + y_2 = 1$ with the other two constraints give $y_1 < 0$ — infeasible.

Maximum of $w$ is 8 at $(y_1, y_2) = (0, 1)$.

Step 3 — Recover primal via complementary slackness. By strong duality, $\min z = \max w = 8$.

At $(y_1, y_2) = (0, 1)$:

• Dual constraint 1: $y_1 + 3y_2 = 3 < 4$ (slack) $\Rightarrow x_1 = 0$.
• Dual constraint 2: $2y_1 + 2y_2 = 2 < 3$ (slack) $\Rightarrow x_2 = 0$.
• $y_2 = 1 > 0$: primal constraint 2 must be binding: $3(0) + 2(0) + x_3 = 8 \Rightarrow x_3 = 8$.
• Check primal constraint 1: $4(8) = 32 \ge 12$ ✓ (slack, consistent with $y_1 = 0$).

$\boxed{x_1 = 0,\; x_2 = 0,\; x_3 = 8,\; z_{\min} = 8.}$

2025 Paper 2, 2025-P2-Q3c (15 marks)

Apply the principle of duality to solve: Maximize $Z = 3x_1 + 4x_2$ subject to $x_1 - x_2 \le 1$, $x_1 + x_2 \ge 4$, $x_1 - 3x_2 \le 3$, $x_1, x_2 \ge 0$.

Step 1 — Standard form. Multiply the $\ge$ constraint by $-1$:

$\max Z = 3x_1 + 4x_2 \quad\text{s.t.}\quad x_1 - x_2 \le 1,\quad -x_1 - x_2 \le -4,\quad x_1 - 3x_2 \le 3,\quad x_1, x_2 \ge 0.$

Step 2 — Write the dual. Dual variables $y_1, y_2, y_3 \ge 0$; dual of a max-$\le$ primal is min-$\ge$:

$\min\; W = y_1 - 4y_2 + 3y_3$

subject to:

$y_1 - y_2 + y_3 \ge 3, \quad -y_1 - y_2 - 3y_3 \ge 4, \quad y_1, y_2, y_3 \ge 0.$

Step 3 — Dual is infeasible. The second dual constraint requires $-y_1 - y_2 - 3y_3 \ge 4$. Since $y_1, y_2, y_3 \ge 0$, the left side is $\le 0 < 4$. No feasible point exists — the dual is infeasible.

Step 4 — Apply duality theorem. The primal is feasible (e.g., $(x_1, x_2) = (0, 4)$ satisfies all constraints). A feasible primal with an infeasible dual is unbounded.

Confirmation. Take $x_1 = 0$, $x_2 = t \ge 4$: constraints $-t \le 1$ ✓, $-t \le -4$ ✓, $-3t \le 3$ ✓; objective $Z = 4t \to \infty$.

$\boxed{\text{The primal LP is UNBOUNDED — no finite optimum exists.}}$

Common Traps

• Dual direction. For a Min primal with $\ge$ constraints, the dual is a Max with $\le$ constraints (and vice versa). Mixing these up flips the feasible region.
• Complementary slackness has two parts. Slack dual constraint forces primal variable to zero; positive dual variable forces primal constraint to bind. Both must be used to recover all primal variables.
• Dual infeasibility signals primal unboundedness — do not try to iterate the primal simplex when this happens.
• Mis-transposing the dual. Each column of $A$ becomes a row of the dual constraint matrix. Number of dual variables = number of primal constraints; number of dual constraints = number of primal variables.

duality-optimality-check (1 question(s); 2019)

Recognition Cues — The question provides a specific basic solution (naming which variables are basic) and asks you to “use the dual” or “verify using the dual” that it is or is not optimal. The primal typically has equality constraints (so dual variables are unrestricted in sign).

Solution Template

1. Identify the candidate basic variables. Set nonbasic variables to zero and solve for the basic values. Confirm feasibility.
2. Write the dual. Equality primal constraints → unrestricted dual variables. Inequality constraints → sign-restricted dual variables.
3. Use complementary slackness: since basic variables $> 0$, their corresponding dual constraints must be binding. Solve this system for the implied dual point $w^*$.
4. Check dual feasibility: verify all remaining dual constraints (for the nonbasic variables) are satisfied at $w^*$.
5. If any dual constraint is violated, the basis is not optimal. State the certificate: which constraint is violated, and what the positive reduced cost is.

Worked Example(s)

2019 Paper 2, 2019-P2-Q4d (10 marks)

Use the dual problem to verify that the basic solution $(x_1, x_2)$ is not optimal for: $\max Z = 2x_1 + 4x_2 + 4x_3 - 3x_4$ subject to $x_1 + x_2 + x_3 = 4$, $x_1 + 4x_2 + x_4 = 8$, $x_1, x_2, x_3, x_4 \ge 0$.

Step 1 — The candidate basic solution. With $x_3 = x_4 = 0$: $x_1 + x_2 = 4$, $x_1 + 4x_2 = 8$. Subtract: $3x_2 = 4 \Rightarrow x_2 = 4/3$, $x_1 = 8/3$. Both positive, so this is a feasible basis with $Z = 2(8/3) + 4(4/3) = 32/3$.

Step 2 — Form the dual. Equality constraints → dual variables $w_1, w_2$ are unrestricted. Dual of a max-equality primal is min-$\ge$ (unrestricted $w$):

$\min\; W = 4w_1 + 8w_2 \quad \text{subject to:} \quad w_1 + w_2 \ge 2,\quad w_1 + 4w_2 \ge 4,\quad w_1 \ge 4,\quad w_2 \ge -3,\quad w_1, w_2\;\text{free.}$

Step 3 — Implied dual point. Basic variables $x_1 > 0$ and $x_2 > 0$ force their dual constraints to be binding:

$w_1 + w_2 = 2, \quad w_1 + 4w_2 = 4.$

Subtract: $3w_2 = 2 \Rightarrow w_2 = 2/3$, $w_1 = 4/3$.

Step 4 — Test dual feasibility. Check the nonbasic-variable constraints:

• $x_3$ constraint: $w_1 \ge 4$? We have $w_1 = 4/3 \not\ge 4$. Violated.
• $x_4$ constraint: $w_2 \ge -3$? $2/3 \ge -3$ ✓.

Step 5 — Certificate. The dual solution induced by basis $(x_1, x_2)$ violates $w_1 \ge 4$. Equivalently, the reduced cost of $x_3$ is $\bar{c}_3 = c_3 - w^\top a_3 = 4 - 4/3 = 8/3 > 0$ — a positive reduced cost in maximisation means $x_3$ should enter the basis.

$\boxed{\text{The dual solution }(w_1, w_2) = (4/3, 2/3)\text{ violates }w_1 \ge 4,\text{ so basis }(x_1, x_2)\text{ is NOT optimal.}}$

Common Traps

• Equality constraints give unrestricted dual variables. Do not impose $w \ge 0$ when the primal has equality constraints. The dual constraints $A^\top w \ge c$ still apply, but $w$ itself is free.
• The certificate is dual infeasibility. Non-optimality is proved by showing the dual point implied by the basis fails at least one dual constraint — not merely by arguing the objective could be larger.
• Reduced cost interpretation. The violated dual constraint $w_1 < 4$ is exactly a positive reduced cost $\bar{c}_3 = 8/3 > 0$, confirming $x_3$ entering the basis would increase $Z$.

form-dual (1 question(s); 2021)

Recognition Cues — The question asks to “convert to dual” or “write the dual” of a given LPP. The primal has a mix of $\le$, $\ge$, and/or $=$ constraints; some primal variables may be unrestricted. The core task is to apply the conversion table without error.

Solution Template

1. Identify the primal direction (Min or Max) and list each constraint type ($\le$, $\ge$, $=$) and each variable type ($\ge 0$ or unrestricted).
2. Apply the conversion table:

3. Write the dual objective: $\max\; W = b^\top y$ (for a Min primal).
4. Write one dual constraint per primal variable using the transposed coefficient matrix $A^\top$.
5. State the sign restrictions on each dual variable from step 2.

Worked Example(s)

2021 Paper 2, 2021-P2-Q3c (15 marks)

Convert to dual: $\min\; Z = x_1 - 3x_2 - 2x_3$ subject to $3x_1 - x_2 + 2x_3 \le 7$, $2x_1 - 4x_2 \ge 12$, $-4x_1 + 3x_2 + 8x_3 = 10$; $x_1, x_2 \ge 0$, $x_3$ unrestricted.

Step 1 — Constraint types. Constraint 1 is $\le 7$ → $y_1 \le 0$. Constraint 2 is $\ge 12$ → $y_2 \ge 0$. Constraint 3 is $= 10$ → $y_3$ unrestricted.

Step 2 — Variable types. $x_1, x_2 \ge 0$ → dual constraints of the $\le c_j$ form. $x_3$ unrestricted → dual constraint of the $= c_j$ form.

Step 3 — Dual objective.

$\max\; W = 7y_1 + 12y_2 + 10y_3$

Step 4 — Dual constraints (transpose the coefficient columns of $A$):

• For $x_1$ (coefficients $3, 2, -4$): $3y_1 + 2y_2 - 4y_3 \le 1$.
• For $x_2$ (coefficients $-1, -4, 3$): $-y_1 - 4y_2 + 3y_3 \le -3$.
• For $x_3$ (coefficients $2, 0, 8$, unrestricted): $2y_1 + 8y_3 = -2$.

$\boxed{\max\; W = 7y_1 + 12y_2 + 10y_3;\quad y_1 \le 0,\; y_2 \ge 0,\; y_3\;\text{unrestricted;}\quad \text{3 constraints as above.}}$

Common Traps

• Sign of dual variable depends on Min vs Max direction. For a Min primal, a $\le$-constraint gives $y_i \le 0$ (not $\ge 0$). This is the most frequent error — students apply the Max-primal table to a Min problem.
• Equality constraint → unrestricted dual variable, not $y_i \ge 0$ or $y_i \le 0$.
• Unrestricted primal variable → equality dual constraint, not an inequality.
• There are $m$ dual variables (one per primal constraint) and $n$ dual constraints (one per primal variable). Check the counts before writing.

Marks-Aware Writing

10-mark answer (2019-style duality-optimality-check): (1) Find the basic solution values and state $Z$. (2) Write out the complete dual problem with all constraints and sign conditions. (3) Solve for the implied dual point from the two binding equations. (4) Test every remaining dual constraint; identify the violated one. (5) State the certificate: the dual constraint violated, or equivalently the positive reduced cost. Five clearly labelled steps; no prose needed beyond the conclusion sentence.

15-mark answer (form-dual or solve-via-dual): For form-dual: show the conversion table or state the rules applied; write the dual objective; list all dual constraints with workings for each transposed column; state all sign restrictions on dual variables. For solve-via-dual: form the dual with full justification; enumerate all vertices of the dual feasible region (show feasibility checks); identify the optimum; apply complementary slackness step-by-step to recover each primal variable; verify with the primal objective. Either type needs six to eight lines of algebra clearly laid out.

Practice Set

• 2015-P2-Q4c (20 m) — — Hint: form the dual of a mixed-constraint Min LPP; track sign restrictions carefully.
• 2022-P2-Q3c (15 m) — — Hint: solve via dual graphically; use complementary slackness to recover the primal solution.