← 2022 Paper 2

UPSC 2022 Maths Optional Paper 2 Q1e — Step-by-Step Solution

10 marks · Section A

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

Question

Use two-phase method: Minimize $Z=x_1+x_2$ subject to $2x_1+x_2\ge 4$, $x_1+7x_2\ge 7$, $x_1,x_2\ge 0$.

Technique

Two-phase method: Phase 1 drives artificials to zero (minimize sum of artificials); Phase 2 minimizes the original objective with the remaining basis.

Solution

Setup. Two $\ge$-constraints; need surplus variables and artificial variables.

Standard form:

• $2x_1+x_2-s_1+a_1=4$
• $x_1+7x_2-s_2+a_2=7$
• $x_1,x_2,s_1,s_2,a_1,a_2\ge 0$.

Phase 1 — Minimize $w=a_1+a_2$

Initial basis: $a_1,a_2$. Initial values: $a_1=4,a_2=7$, $w=11$.

Reduced cost for Phase 1 ($c=(0,0,0,0,1,1)$): $\bar c_j=c_j-c_B^T A_j$.

For $x_1$: $0-(1)(2)-(1)(1)=-3$. For $x_2$: $0-(1)(1)-(1)(7)=-8$. For $s_1$: $0-(1)(-1)=1$. For $s_2$: $0-(1)(-1)=1$.

Most negative: $-8$ for $x_2$. $x_2$ enters.

Ratio test: $a_1: 4/1=4$, $a_2: 7/7=1$. Min at $a_2$ row. $a_2$ leaves.

Pivot on $(a_2, x_2)$:

New $x_2$ row: $(1/7, 1, 0, -1/7, 0, 1/7, 1)$ (divide $a_2$ row by 7).

New $a_1$ row: $a_1-1\cdot x_2$: $(2-1/7, 0, -1, 1/7, 1, -1/7, 3)=(13/7, 0, -1, 1/7, 1, -1/7, 3)$.

Updated reduced costs: $\bar c_{x_1}=0-(1)(13/7)-(0)(1/7)=-13/7$.

Most negative: $-13/7$ for $x_1$. $x_1$ enters.

Ratio test: $a_1: 3/(13/7)=21/13$, $x_2: 1/(1/7)=7$. Min at $a_1$. $a_1$ leaves.

Pivot on $(a_1, x_1)$:

New $x_1$ row: $(1, 0, -7/13, 1/13, 7/13, -1/13, 21/13)$.

New $x_2$ row: $x_2-1/7\cdot x_1$: $(0, 1, -7/13\cdot(-1/7)\cdot\ldots)$ — let me redo carefully.

Old $x_2$ row: $(1/7, 1, 0, -1/7, 0, 1/7, 1)$. Subtract $(1/7)$ times new $x_1$ row: $(1/7-1/7, 1-0, 0-(1/7)(-7/13), -1/7-(1/7)(1/13), 0-(1/7)(7/13), 1/7-(1/7)(-1/13), 1-(1/7)(21/13))$ $=(0, 1, 1/13, -2/13, -1/13, 2/13, 1-3/13)=(0, 1, 1/13, -2/13, -1/13, 2/13, 10/13)$.

Wait, $-1/7-(1/7)(1/13)=-1/7\cdot(1+1/13)=-1/7\cdot 14/13=-2/13$ ✓.

All artificial variables $a_1,a_2$ are now out of the basis. Phase 1 complete with $w=0$.

Phase 1 solution: $x_1=21/13, x_2=10/13, s_1=s_2=0, a_1=a_2=0$.

Phase 2 — Restore original objective

Drop artificial columns; minimize $Z=x_1+x_2$.

Basis: $\{x_1,x_2\}$. Current values: $x_1=21/13,x_2=10/13$. $Z=31/13$.

Tableau (drop $a_1,a_2$ columns):

Reduced costs for $Z$: $c=(1,1,0,0)$. $c_B=(1,1)$.

For $s_1$: $0-(1)(-7/13)-(1)(1/13)=7/13-1/13=6/13>0$. For $s_2$: $0-(1)(1/13)-(1)(-2/13)=-1/13+2/13=1/13>0$.

All non-basic reduced costs are non-negative ⇒ current solution is optimal.

Answer