← 2019 Paper 2

UPSC 2019 Maths Optional Paper 2 Q4d — Step-by-Step Solution

10 marks · Section A

Duality · Linear Programming · asked 4× in 13 yrs · Read the full method →

Question

Consider the following LPP, Maximize $Z=2x_1+4x_2+4x_3-3x_4$ subject to

and $x_1,x_2,x_3,x_4\ge 0$. Use the dual problem to verify that the basic solution $(x_1,x_2)$ is not optimal.

Technique

Construct the dual (free dual variables for equality constraints); use complementary slackness to read off the dual point forced by the basis, then test dual feasibility — a violated dual constraint certifies primal non-optimality (equivalently, a positive reduced cost).

Solution

Step 1 — The candidate basic solution $(x_1,x_2)$

With $x_3=x_4=0$, the constraints become

Subtracting: $3x_2=4\Rightarrow x_2=\tfrac43,\ x_1=4-\tfrac43=\tfrac83$. Both $>0$, so $(x_1,x_2)=(\tfrac83,\tfrac43)$ is a (feasible) basic solution with

Step 2 — Form the dual

The primal has equality constraints, so the dual variables $w_1,w_2$ are unrestricted in sign. For a maximization primal $\max c^\top x$ s.t. $Ax=b,\ x\ge0$, the dual is $\min b^\top w$ s.t. $A^\top w\ge c$:

subject to (one constraint per primal variable, columns of $A$):

Step 3 — Dual values implied by the basis $(x_1,x_2)$

By complementary slackness, since $x_1>0$ and $x_2>0$ their dual constraints must hold with equality at the corresponding dual solution:

Subtract: $3w_2=2\Rightarrow w_2=\tfrac23,\ w_1=2-\tfrac23=\tfrac43.$ Dual objective $W=4\cdot\tfrac43+8\cdot\tfrac23=\tfrac{16}{3}+\tfrac{16}{3}=\tfrac{32}{3}=Z$ (so weak duality holds with equality between these candidate values).

Step 4 — Test dual feasibility (this is the optimality certificate)

Check the remaining dual constraints (those for the nonbasic $x_3,x_4$):

• $x_3$ constraint: $w_1\ge4$? We have $w_1=\tfrac43\not\ge4$. Violated.
• $x_4$ constraint: $w_2\ge-3$? $\tfrac23\ge-3$. ✓

Because the dual solution induced by the basis $(x_1,x_2)$ is dual-infeasible (it violates $w_1\ge4$), the primal basic solution $(x_1,x_2)$ does not satisfy the optimality (complementary-slackness) conditions. Equivalently, the reduced cost of $x_3$ is

a positive reduced cost in a maximization — bringing $x_3$ into the basis would increase $Z$.

Answer