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

20 marks · Section A

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

Question

Solve the following linear programming problem by simplex method:

\text{Maximize } z=3x_1+5x_2+4x_3

subject to

\begin{aligned}2x_1+3x_2&\le 8\\ 2x_2+5x_3&\le 10\\ 3x_1+2x_2+4x_3&\le 15\\ x_1,x_2,x_3&\ge 0.\end{aligned}

Technique

Primal simplex in tableau form; slack variables for the initial basis; entering variable = most positive $c_j-z_j$ , leaving variable = minimum ratio test; iterate to non-positive $c_j-z_j$ .

Solution

Step 1 — Standard form with slack variables

Add slacks $s_1,s_2,s_3\ge0$ :

\begin{aligned}2x_1+3x_2\phantom{+0x_3}+s_1&=8\\ 2x_2+5x_3+s_2&=10\\ 3x_1+2x_2+4x_3+s_3&=15\end{aligned}\qquad z-3x_1-5x_2-4x_3=0.

Initial basis $(s_1,s_2,s_3)=(8,10,15)$ with $z=0$ .

Step 2 — Iteration 0 (initial tableau)

Basis $\{s_1,s_2,s_3\}$ . Row $c_j-z_j=(3,5,4,0,0,0)$ .

Basis	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	RHS	ratio (RHS/ $x_2$ )
$s_1$	2	3	0	1	0	0	8	$8/3$ ← min
$s_2$	0	2	5	0	1	0	10	$5$
$s_3$	3	2	4	0	0	1	15	$15/2$

Most positive $c_j-z_j=5$ at $x_2$ → $x_2$ enters; min ratio $8/3$ → $s_1$ leaves. Pivot on $3$ .

Step 3 — Iteration 1

Basis $\{x_2,s_2,s_3\}$ , $z=40/3$ . Row $c_j-z_j=\left(-\tfrac13,\,0,\,4,\,-\tfrac53,\,0,\,0\right)$ .

Basis	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	RHS	ratio (RHS/ $x_3$ )
$x_2$	$2/3$	1	0	$1/3$	0	0	$8/3$	—
$s_2$	$-4/3$	0	5	$-2/3$	1	0	$14/3$	$14/15$ ← min
$s_3$	$5/3$	0	4	$-2/3$	0	1	$29/3$	$29/12$

Most positive $c_j-z_j=4$ at $x_3$ → $x_3$ enters; min ratio $14/15$ → $s_2$ leaves. Pivot on $5$ .

Step 4 — Iteration 2

Basis $\{x_2,x_3,s_3\}$ , $z=256/15$ . Row $c_j-z_j=\left(\tfrac{11}{15},\,0,\,0,\,-\tfrac{17}{15},\,-\tfrac45,\,0\right)$ .

Basis	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	RHS	ratio (RHS/ $x_1$ )
$x_2$	$2/3$	1	0	$1/3$	0	0	$8/3$	$4$
$x_3$	$-4/15$	0	1	$-2/15$	$1/5$	0	$14/15$	—
$s_3$	$41/15$	0	0	$-2/15$	$-4/5$	1	$89/15$	$89/41$ ← min

Most positive $c_j-z_j=\tfrac{11}{15}$ at $x_1$ → $x_1$ enters; min ratio $89/41$ → $s_3$ leaves. Pivot on $41/15$ .

Step 5 — Iteration 3 (optimal)

Basis $\{x_2,x_3,x_1\}$ . Row $c_j-z_j=\left(0,\,0,\,0,\,-\tfrac{45}{41},\,-\tfrac{24}{41},\,-\tfrac{11}{41}\right)\le0$ → optimal.

Basis	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	RHS
$x_2$	0	1	0	$15/41$	$8/41$	$-10/41$	$50/41$
$x_3$	0	0	1	$-6/41$	$5/41$	$4/41$	$62/41$
$x_1$	1	0	0	$-2/41$	$-12/41$	$15/41$	$89/41$

All $c_j-z_j\le0$ , so the current solution is optimal:

x_1=\frac{89}{41},\quad x_2=\frac{50}{41},\quad x_3=\frac{62}{41},

z=3\cdot\frac{89}{41}+5\cdot\frac{50}{41}+4\cdot\frac{62}{41}=\frac{267+250+248}{41}=\frac{765}{41}.

Answer

\boxed{\;z_{\max}=\frac{765}{41}\approx18.66\quad\text{at}\quad \left(x_1,x_2,x_3\right)=\left(\frac{89}{41},\frac{50}{41},\frac{62}{41}\right).\;}