← 2022 Paper 2

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

15 marks · Section A

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

Question

Solve $\max Z=x_1+x_2+x_3$ subject to $2x_1+x_2+x_3\le 2$, $4x_1+2x_2+x_3\le 2$, $x_i\ge 0$ by simplex. Write dual; read dual optimum from optimal table.

Technique

Standard simplex; degenerate pivot (RHS becomes 0 during pivot); continue until all $z-c\ge 0$.

Solution

Step 1 — Standard form with slacks $s_1,s_2$

$2x_1+x_2+x_3+s_1=2$ $4x_1+2x_2+x_3+s_2=2$

Step 2 — Initial simplex tableau

Most negative: any of $-1$. Pick $x_3$ (ties broken by choosing smallest index, but $x_3$‘s column gives a cleaner pivot).

Actually let me pick $x_1$ (smallest index).

Pivot on $x_1$: Ratio test: $s_1: 2/2=1$, $s_2: 2/4=1/2$. $s_2$ leaves.

New $x_1$ row: $(s_2/4)$: $(1, 1/2, 1/4, 0, 1/4, 1/2)$.

New $s_1$ row: $s_1-2\cdot x_1$: $(0, 0, 1/2, 1, -1/2, 1)$.

New $z-c$: add $1\cdot x_1$ row: $(-1+1, -1+1/2, -1+1/4, 0, 1/4, 1/2)=(0, -1/2, -3/4, 0, 1/4, 1/2)$.

Tableau:

Most negative: $-3/4$ at $x_3$. $x_3$ enters.

Ratio test: $s_1: 1/(1/2)=2$, $x_1: (1/2)/(1/4)=2$. Tie.

Pick $s_1$ leaving (degenerate, but either works).

Pivot on $x_3$, row $s_1$:

New $x_3$ row: multiply $s_1$ by 2: $(0, 0, 1, 2, -1, 2)$.

New $x_1$ row: $x_1-(1/4)\cdot x_3$: $(1, 1/2, 0, -1/2, 1/2, 0)$.

New $z-c$: add $(3/4)\cdot x_3$ row: $(0, -1/2, 0, 3/2, 1/4-3/4, 1/2+3/2)=(0, -1/2, 0, 3/2, -1/2, 2)$.

Hmm — still $-1/2$ for $x_2$. Continue.

Pivot on $x_2$: Ratio test on $x_2$ column.

$x_3$ row $x_2$-coeff $=0$: skip. $x_1$ row $x_2$-coeff $=1/2$, ratio $0/(1/2)=0$. $x_1$ leaves.

But ratio 0 means a degenerate pivot — Bland’s rule typically prevents cycling.

Hmm actually if $x_1$ has $x_2$-coefficient $1/2$ and RHS $=0$ in the $x_1$ row (after last pivot), then ratio $=0$. The pivot will keep things at $x_1=0$ but introduce $x_2$ into the basis. The objective doesn’t increase.

Let me re-examine: after the second pivot, do I have RHS$=0$ for $x_1$ row? Yes: $x_1$ row is $(1, 1/2, 0, -1/2, 1/2, 0)$ with RHS $0$.

OK this means $x_1=0$ now (degenerate). The current solution is $x_1=0, x_2=0, x_3=2, s_1=0, s_2=0$, with $Z=0+0+2=2$.

But there’s still room to improve: $-1/2$ in $z-c$ for $x_2$. Pivot:

New $x_2$ row: multiply $x_1$ row by 2: $(2, 1, 0, -1, 1, 0)$.

New $x_3$ row: $x_3-0\cdot x_2$: $(0, 0, 1, 2, -1, 2)$ (unchanged).

New $z-c$: add $(1/2)\cdot x_2$ row: $(0+1, -1/2+1/2, 0, 3/2-1/2, -1/2+1/2, 2+0)=(1, 0, 0, 1, 0, 2)$.

All $z-c\ge 0$ ⇒ optimal.

Tableau:

$x_2=0, x_3=2, x_1=0$. $Z=0+0+2=2$.

Primal optimum: $x_1=0,x_2=0,x_3=2,Z=2$.

Step 3 — Dual

Primal: max $Z=x_1+x_2+x_3$, two $\le$ constraints, $x\ge 0$.

Dual: min $W=2y_1+2y_2$, three $\ge$ constraints (one per primal variable), $y\ge 0$.

Constraints:

• $2y_1+4y_2\ge 1$ (from $x_1$).
• $y_1+2y_2\ge 1$ (from $x_2$).
• $y_1+y_2\ge 1$ (from $x_3$).

Step 4 — Read dual optimum from primal optimal tableau

Dual values = $z-c$ row entries at slack-variable columns:

• $y_1^*=1$ (at $s_1$).
• $y_2^*=0$ (at $s_2$).

Dual optimum: $y_1=1,y_2=0,W=2(1)+2(0)=2$ ✓ (matches $Z=2$, strong duality).

Step 5 — Verify dual feasibility

• $2(1)+4(0)=2\ge 1$ ✓.
• $1+2(0)=1\ge 1$ ✓ (binding).
• $1+0=1\ge 1$ ✓ (binding).

Complementary slackness: bindings 2 and 3 correspond to nonzero primal variables $x_2,x_3$? But $x_2=0$ in optimum. Hmm, primal degenerate.

Actually the primal optimum is at vertex $x_1=x_2=0,x_3=2$ where only $x_3$ is positive — so only dual constraint 3 needs to bind. Constraint 2 binding is consistent (degenerate vertex with multiple optimal vertices possible).

Answer