UPSC 2025 Maths Optional Paper 2 Q3c — Step-by-Step Solution

15 marks · Section A

Duality · Linear Programming · asked 5× in 14 yrs · Read the full method →

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$ :

\max Z = 3x_1 + 4x_2 \quad\text{s.t.}\quad \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$ .