UPSC Maths 2025 Paper 2 Q3c — Solution

15 marks · Section A

Question

Apply the principle of duality to solve the following linear programming problem: Maximize $Z = 3x_1 + 4x_2$ subject to the constraints $x_1 - x_2 \leq 1$ $x_1 + x_2 \geq 4$ $x_1 - 3x_2 \leq 3$ $x_1, x_2 \geq 0$

Technique

Construct the dual LP and apply the duality theorem: if the dual is infeasible while the primal is feasible, the primal is unbounded. Duality exposes the unboundedness without iterating the primal simplex.

Solution

A note before starting: as printed, this maximization LP is unbounded — it has no finite optimal vertex. The duality machinery below is exactly what detects this; we solve the problem as stated and arrive at the honest verdict (unbounded). A bounded textbook version would need a sign change (e.g. the second constraint as $x_1+x_2\le4$ , or a minimization objective).

Step 1 — Put the primal in standard ” $\le$ , maximize” form. Multiply the $\ge$ constraint by $-1$ :

\begin{cases} x_1 - x_2 \le 1\\ -x_1 - x_2 \le -4\\ x_1 - 3x_2 \le 3\\ x_1,x_2\ge0. \end{cases}$$ **Step 2 — Write the dual.** With dual variables $y_1,y_2,y_3\ge0$ (one per primal constraint), the dual of a max-$\le$ primal is a **min-$\ge$** problem: $$\min\; W = 1\,y_1 - 4\,y_2 + 3\,y_3$$ subject to (one constraint per primal variable, transposing the coefficient matrix): $$\text{(from } x_1\text{): } \;\; y_1 - y_2 + y_3 \ge 3,$$ $$\text{(from } x_2\text{): } \;\; -y_1 - y_2 - 3y_3 \ge 4,$$ $$y_1,y_2,y_3 \ge 0.$$ **Step 3 — Examine dual feasibility.** Consider the second dual constraint: $$-y_1 - y_2 - 3y_3 \ge 4.$$ With $y_1,y_2,y_3\ge0$, the left-hand side $-y_1-y_2-3y_3 \le 0$ for all feasible $y$. Since $0 < 4$, this inequality **can never be satisfied**. Hence the **dual is infeasible** (its feasible region is empty). **Step 4 — Apply the duality theorem.** The primal is feasible: e.g. $(x_1,x_2)=(0,4)$ gives $0-4=-4\le1$, $0+4=4\ge4$, $0-12=-12\le3$ — all satisfied. The duality theorem states: if the dual has no feasible solution but the primal is feasible, then the primal objective is **unbounded** (above, for a maximization). Therefore the primal is **unbounded**: $Z$ can be made arbitrarily large. **Step 5 — Direct confirmation.** Take $x_1=0$, $x_2=t$ for $t\ge4$. The constraints hold: $-t\le1$, $t\ge4$, $-3t\le3$, all satisfied. The objective $Z = 4t \to +\infty$ as $t\to\infty$. So no finite optimum exists, consistent with the duality verdict. ## Answer $$\boxed{\;\text{The primal LP has NO finite optimum — it is unbounded } (Z\to+\infty).\;}$$ The dual is **infeasible** (its second constraint $-y_1-y_2-3y_3\ge4$ is impossible with $y\ge0$); since the primal is feasible, the duality theorem forces the primal to be unbounded. Concretely, along $x_1=0,\ x_2=t\to\infty$, $Z=4t\to\infty$.