← 2016 Paper 2

UPSC 2016 Maths Optional Paper 2 Q2c — Step-by-Step Solution

20 marks · Section A

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

Question

Maximize $z=2x_1+3x_2+6x_3$ subject to

Is the optimal solution unique? Justify your answer.

Technique

Simplex (two iterations: enter $x_3$ then $x_1$); uniqueness via strict negativity of all non-basic reduced costs at the optimal table.

Solution

We solve by the simplex method, then test uniqueness via the reduced costs of the non-basic variables at the optimal table: a maximization optimum is unique iff every non-basic variable has a strictly negative reduced cost ($c_j-z_j<0$); a zero reduced cost on a non-basic variable signals alternative optima.

Step 1 — Standard form with slacks

Add slacks $s_1,s_2\ge0$:

Initial basis $\{s_1,s_2\}$, $z=0$. Row-0 (reduced costs $c_j-z_j$, since all $z_j=0$ initially): $x_1:2,\ x_2:3,\ x_3:6$.

Step 2 — Iteration 1: enter $x_3$ (largest positive reduced cost $6$)

Ratios (RHS / column of $x_3$): row $s_1$: $5/1=5$; row $s_2$: $6/2=3$ (min). So $s_2$ leaves, $x_3$ enters; pivot on the $s_2$-row coefficient $2$.

Pivot row ($\div2$): $\ \tfrac32x_2+x_3+\tfrac12 s_2=3$. Update $s_1$-row ($-1\times$ pivot row): $\ 2x_1+x_2+x_3+s_1=5\Rightarrow 2x_1+(1-\tfrac32)x_2+s_1-\tfrac12 s_2=5-3$, i.e.

New $z=6\cdot3=18$. Reduced costs $c_j-z_j$ ($z_j=c_B\cdot(\text{column})$, $c_B=(0,6)$ for basis $\{s_1,x_3\}$):

• $x_1$: $2-6\cdot0=2>0$ (column $(2,0)$, $z_j=6\cdot0=0$).
• $x_2$: $3-6\cdot\tfrac32=3-9=-6<0$.
• $s_2$: $0-6\cdot\tfrac12=-3<0$.

$x_1$ still positive $\Rightarrow$ not optimal.

Step 3 — Iteration 2: enter $x_1$

Ratios (RHS / $x_1$-column $(2,0)$): row $s_1$: $2/2=1$ (min); row $x_3$: column entry $0$, skip. So $s_1$ leaves, $x_1$ enters; pivot on $2$ in the $s_1$-row.

Pivot row ($\div2$): $\ x_1-\tfrac14 x_2+\tfrac12 s_1-\tfrac14 s_2=1.$ $x_3$-row unchanged in $x_1$ (coefficient $0$): $\ \tfrac32 x_2+x_3+\tfrac12 s_2=3.$

Basic solution: $x_1=1,\ x_3=3,\ x_2=0,\ s_1=s_2=0$.

Step 4 — Optimality check (reduced costs)

Basis $\{x_1,x_3\}$, $c_B=(2,6)$. Compute $c_j-z_j$ for non-basic $x_2,s_1,s_2$ using $B^{-1}$:

• $x_2$ (column $(1,3)$): $z_j=c_B B^{-1}(1,3)^T$; $c_2-z_2=3-8.5=-5.5<0$.
• $s_1$ (column $(1,0)$): $c-z=0-1=-1<0$.
• $s_2$ (column $(0,1)$): $c-z=0-2.5=-2.5<0$.

All non-basic reduced costs are strictly negative, so the table is optimal and

Step 5 — Uniqueness

A maximization LP at an optimal basic feasible solution has alternative optima iff some non-basic variable has reduced cost exactly $0$ (it could enter without changing $z$). Here every non-basic reduced cost is strictly negative ($-5.5,\,-1,\,-2.5$). Bringing any of them in would strictly decrease $z$. Hence

Answer