← 2015 Paper 2

UPSC 2015 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

Solve the following LPP by the simplex method. Write its dual. Also, write the optimal solution of the dual from the optimal table of the given problem:

subject to $x_1+4x_2-2x_3\le 2$, $-x_1+2x_2+3x_3\le 1$, $x_1,x_2,x_3\ge 0$.

Technique

Standard simplex on the standard form (max with $\le$, slack variables); iterate till all reduced costs $\ge 0$; dual optimum = $z_j-c_j$ row at slack-variable columns of optimal tableau (this is the standard “shadow price” reading).

Solution

Step 1 — Convert to standard form (add slacks $s_1,s_2$)

subject to

Step 2 — Initial simplex tableau

Basis: $\{s_1,s_2\}$.

($z_j-c_j$ for the negative-of-coefficient form: $-c_j$ initially. Most-negative is $-5$ for $x_3$.)

Step 3 — Iteration 1: $x_3$ enters

Ratio test on positive entries in $x_3$ column:

• Row $s_1$: $-2$ (negative; skip).
• Row $s_2$: $3$; ratio $=1/3$.

So $s_2$ leaves; pivot on row $s_2$, column $x_3$.

New row $s_2$ (becomes $x_3$): divide by 3: $(-1/3,\;2/3,\;1,\;0,\;1/3\;|\;1/3)$.

New row $s_1$: $R_{s_1}+2\cdot R_{x_3}$ (to make $-2$ become $0$):

• $1+2(-1/3)=1-2/3=1/3$
• $4+2(2/3)=4+4/3=16/3$
• $-2+2(1)=0$ ✓
• $1+2(0)=1$
• $0+2(1/3)=2/3$
• $2+2(1/3)=2+2/3=8/3$.

New $z_j-c_j$ row: subtract $-5\times$ new pivot row from old $z_j-c_j$:

Actually let me redo. Standard: $(z_j-c_j)$ becomes $(z_j-c_j)+5\cdot$ (pivot row). The pivot was at the $x_3$ column with $z_j-c_j=-5$. So:

New $z_j-c_j$:

• $x_1$: $-2+(-5)(-1/3)\cdot(-1) = -2 -5/3$. Wait let me think more carefully.

Standard simplex update for $z_j-c_j$: $\text{new}=\text{old}-\text{(old pivot col entry)}\cdot\text{(new pivot row)}$.

Old $(z_j-c_j)$ row: $(-2, 4, -5, 0, 0\;|\;0)$. Pivot column was $x_3$ with old value $-5$.

New $(z_j-c_j)=\text{old}-(-5)\cdot\text{(new pivot row)} = \text{old}+5\cdot\text{(new pivot row)}$:

• $x_1$: $-2+5(-1/3)=-2-5/3=-11/3$.
• $x_2$: $4+5(2/3)=4+10/3=22/3$.
• $x_3$: $-5+5(1)=0$.
• $s_1$: $0+5(0)=0$.
• $s_2$: $0+5(1/3)=5/3$.
• RHS: $0+5(1/3)=5/3$.

Tableau:

Most-negative: $-11/3$ at $x_1$. $x_1$ enters.

Step 4 — Iteration 2: $x_1$ enters

Ratio test on positive entries in $x_1$ column:

• Row $s_1$: $1/3$; ratio $=(8/3)/(1/3)=8$.
• Row $x_3$: $-1/3$ (negative; skip).

$s_1$ leaves. Pivot on row $s_1$, column $x_1$.

New row $s_1$ (becomes $x_1$): divide by $1/3$ = multiply by 3: $(1, 16, 0, 3, 2 \;|\; 8)$.

New row $x_3$: $R_{x_3}+(1/3)\cdot R_{x_1}$:

• $-1/3+(1/3)(1)=0$ ✓
• $2/3+(1/3)(16)=2/3+16/3=18/3=6$
• $1+0=1$
• $0+(1/3)(3)=1$
• $1/3+(1/3)(2)=1/3+2/3=1$
• $1/3+(1/3)(8)=1/3+8/3=3$.

New $(z_j-c_j)$: $\text{old}+(11/3)\cdot R_{x_1\text{ new}}$:

• $x_1$: $-11/3+(11/3)(1)=0$.
• $x_2$: $22/3+(11/3)(16)=22/3+176/3=198/3=66$.
• $x_3$: $0+0=0$.
• $s_1$: $0+(11/3)(3)=11$.
• $s_2$: $5/3+(11/3)(2)=5/3+22/3=27/3=9$.
• RHS: $5/3+(11/3)(8)=5/3+88/3=93/3=31$.

Tableau:

All $z_j-c_j\ge 0$ ⇒ optimal.

Step 5 — Optimal solution

$x_1=8$, $x_3=3$, $x_2=0$, $s_1=0$, $s_2=0$.

$Z_{\max}=2(8)-4(0)+5(3)=16+15=31$. ✓

Answer