← 2013 Paper 2

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

20 marks · Section A

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

Question

Minimize $z=5x_1-4x_2+6x_3-8x_4$ subject to the constraints

Technique

Standard simplex with slack variables; two pivots reach optimum.

Solution

Strategy. Standard simplex with slack variables. Since all constraints are $\le$ with non-negative RHS, the slacks form a feasible starting basis.

Step 1 — Standard form

Introduce slacks $s_1,s_2,s_3\ge 0$:

Min $z=5x_1-4x_2+6x_3-8x_4$ (zero objective contribution from slacks).

Initial BFS: $x_j=0$, $(s_1,s_2,s_3)=(40,8,10)$, $z=0$.

Step 2 — Iteration 1: $x_4$ enters, $s_2$ leaves

For minimisation, entering variable = one with most positive $z_j-c_j$. Compute $z_j-c_j=-c_j$ (initial $c_B=0$):

Min-ratio test on $x_4$ column: $40/4=10$, $8/2=4$, $10/(-1)$ skip (negative coefficient). Min = 4 at $s_2$.

Pivot on entry $(s_2,\,x_4)=2$. Resulting tableau (after row operations):

$c_B=(0,-8,0)$, $z=-32$.

Step 3 — Iteration 2: $x_2$ enters, $s_1$ leaves

Recompute $z_j-c_j$:

Largest positive: $x_2$ (with $+8$). Enter $x_2$.

Min-ratio on $x_2$ column: $s_1$: $24/4=6$; $x_4$: $-1/2$ (skip); $s_3$: $-5/2$ (skip). Min = 6 at $s_1$.

Pivot on $(s_1,\,x_2)=4$. Resulting tableau:

$c_B=(-4,-8,0)$, $z=-4(6)+(-8)(7)=-24-56=-80$.

Step 4 — Optimality check

Compute $z_j-c_j$ for non-basic variables:

All $z_j-c_j\le 0$ — optimal. The value $z_{s_2}-c_{s_2}=0$ indicates alternative optima exist along the edge into $s_2$.

Step 5 — Optimum

Answer