← 2014 Paper 2

UPSC 2014 Maths Optional Paper 2 Q4c — Step-by-Step Solution

20 marks · Section A

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

Question

Find all optimal solutions of the following linear programming problem by the simplex method:

Technique

Simplex method; alternative-optima detection via $c_j-z_j=0$ for a non-basic variable at optimum; iterate to find both extreme optimal vertices.

Solution

Step 1 — Standard form

Introduce slacks $s_1,s_2,s_3$ for each $\le$ constraint:

Initial BFS: $x_1=x_2=0$, $(s_1,s_2,s_3)=(200,32,40)$, $Z=0$.

Step 2 — Iteration 1: $x_1$ in, $s_2$ out

For max simplex: enter the variable with the largest $c_j-z_j$. Initially $c_j-z_j$ equals $c_j$: $(30, 24, 0, 0, 0)$. Largest: $x_1$ at 30.

Min ratio in $x_1$ column: $\min(200/5,\;32/1)=\min(40, 32)=32$ at $s_2$. So $s_2$ leaves.

Pivot. New tableau:

$Z=30\cdot 32=960$.

Step 3 — Iteration 2: $x_2$ in, $s_1$ out

$c_j-z_j$: $x_2: 24-0=24$ (largest), $s_2: 0-30=-30$. Enter $x_2$.

Min ratio: $40/4=10$, $40/1=40$. Min 10 at $s_1$.

Pivot. New tableau:

$Z=24(10)+30(32)=240+960=1200$.

Step 4 — Optimality check

$c_j-z_j$ for non-basic:

• $s_1: 0-(24\cdot 1/4+30\cdot 0)=-6\le 0$ ✓.
• $s_2: 0-(24\cdot(-5/4)+30\cdot 1)=0-(0)=0$.

All $\le 0$ ⇒ optimal. The $0$ at $s_2$ signals alternative optima.

Optimum 1: $x_1=32,\;x_2=10,\;Z=1200$.

Step 5 — Find other optimal vertex (bring $s_2$ into basis)

Min ratio in $s_2$ column (positive entries): $x_1: 32/1=32$, $s_3: 30/(5/4)=24$. Min 24 at $s_3$.

Pivot. New tableau:

$Z=24\cdot 40+30\cdot 8=960+240=1200$ ✓.

Optimum 2: $x_1=8,\;x_2=40,\;Z=1200$.

Step 6 — All optimal solutions

The set of optimal solutions is the line segment joining $(32,10)$ and $(8,40)$. Parametrically:

Verification of $Z$ on segment: $Z=30(32-24t)+24(10+30t)=960-720t+240+720t=1200$ for all $t\in[0,1]$ ✓.

Both endpoints satisfy $5x_1+4x_2=200$ (binding constraint), and the entire segment lies on this constraint boundary.

Answer