← 2023 Paper 2

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

20 marks · Section A

Big-M / two-phase method (artificial variables) · Linear Programming · asked 5× in 13 yrs · Read the full method →

Question

Solve the following linear programming problem by Big M method:

subject to

Is the optimal solution unique? Justify your answer.

Technique

Big-M simplex; two iterations sufficed because both artificials left the basis with positive penalties.

Solution

Step 1 — Standard form

Introduce surplus $s_1,s_2$ for the $\ge$ constraints, slack $s_3$ for the $\le$, and artificials $a_1,a_2$ for the $\ge$ constraints to obtain a starting BFS:

Big-M objective (minimisation; artificials carry large penalty $M$):

Step 2 — Initial simplex tableau

Initial basis $B^{(0)}=\{a_1,a_2,s_3\}$ with $a_1=9,\;a_2=15,\;s_3=9$, $Z^{(0)}=24M$. Cost row $c_B=(M,M,0)^{T}$.

$z_j-c_j$ values (recall: for a min problem, enter the variable with the largest positive $z_j-c_j$; optimal when all $z_j-c_j\le 0$):

Largest positive: $x_2$ column. Min-ratio: $\min\{9/1,15/2\}=15/2=7.5$ → $a_2$ leaves. Pivot on entry $(\text{row}_2,x_2)$.

Step 3 — Iteration 1: $x_2$ in, $a_2$ out

Divide row 2 by 2; eliminate $x_2$ from rows 1 and 3.

($a_2$ column is dropped; it has left and won’t re-enter.)

New $c_B=(M,3,0)^{T}$.

Largest positive: $x_1$ ($0.5M-0.5$). Min-ratio: $\min\{1.5/0.5,\;7.5/0.5,\;31.5/3.5\}=\min\{3,15,9\}=3$ → $a_1$ leaves. Pivot on entry $(\text{row}_1,x_1)$.

Step 4 — Iteration 2: $x_1$ in, $a_1$ out

Divide row 1 by $0.5$; eliminate $x_1$ from rows 2, 3.

($a_1$ column dropped.)

New $c_B=(2,3,0)^{T}$, $Z=2(3)+3(6)+0=24$.

$z_j-c_j$:

All $z_j-c_j\le 0$ → optimal.

Step 5 — Optimum and uniqueness

Answer