← 2019 Paper 2

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

15 marks · Section A

Simplex method (basic) · Linear Programming · asked 9× in 13 yrs · Read the full method →

Question

Solve the linear programming problem using Simplex method. Minimize $Z=x_1+2x_2-3x_3-2x_4$ subject to

and $x_1,x_2,x_3,x_4\ge 0$.

Technique

Two-phase simplex (artificial variables for equality constraints); the structural cancellation $4x_3+x_4=0$ collapses the feasible region.

Solution

Step 1 — A structural observation (feasible region forces $x_3=x_4=0$)

Subtract the first equation from the second:

With $x_3,x_4\ge0$ this forces $x_3=0$ and $x_4=0$. Substituting back, both constraints reduce to the single equation $x_1+2x_2=4$. So every feasible point has $x_3=x_4=0$ and $x_1+2x_2=4$, on which

Thus $Z\equiv4$ on the entire feasible region; the minimum (and maximum) is $4$. We confirm this with a formal simplex run.

Step 2 — Phase-I setup (artificial variables)

Both RHS are $+4>0$; introduce artificials $a_1,a_2\ge0$ and minimize $a_1+a_2$:

Initial basis $(a_1,a_2)=(4,4)$.

Iteration 1. Phase-I reduced costs (cost row $a_1+a_2$): for a structural column, $z_j-c_j=(\text{column sum})-0$. Column sums: $x_1:2,\ x_2:4,\ x_3:-3+1=-2,\ x_4:1+2=3$. Most positive is $x_2$ ($=4$); enter $x_2$. Ratios $4/2=2,\ 4/2=2$ (tie); pivot on row 1, $a_1$ leaves. Pivot (divide row1 by 2):

Eliminate $x_2$ from row 2 (subtract $2\times$row1): row2 becomes

Iteration 2. Remaining artificial $a_2=0$ (degenerate). Phase-I objective now $a_2$; its row has $4x_3+x_4$ with positive entries but RHS $0$, so any pivot keeps the value at $0$; Phase-I optimum $=0$ is reached — feasibility achieved with $a_1=a_2=0$. Drop artificials. Basic feasible solution: $x_2=2,\ x_1=x_3=x_4=0$ (the row-2 relation $4x_3+x_4=0\Rightarrow x_3=x_4=0$ as found in Step 1).

Step 3 — Phase-II (optimize $Z=x_1+2x_2-3x_3-2x_4$)

Current basis $\{x_2\}$ with the second (reduced) row $4x_3+x_4=0$ pinning $x_3,x_4$. Express $Z$ in nonbasic variables using $x_2=2-\tfrac12x_1+\tfrac32x_3-\tfrac12x_4$ (from the pivoted row 1) and $x_3=\tfrac14(-x_4)$, i.e. on the feasible set $x_3=x_4=0$:

All reduced costs are $0$ along feasible directions (and the only feasible directions keep $x_3=x_4=0$, $x_1+2x_2=4$). No entering variable improves $Z$: optimal.

Answer