← 2022 Paper 2

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

20 marks · Section A

Transportation problem · Linear Programming · asked 5× in 13 yrs · Read the full method →

Question

Find IBFS by Vogel’s method and optimal solution by MODI:

Total avail = 11+13+19 = 43 = Total req. Balanced.

Technique

VAM for initial BFS (penalty-based row/column selection); MODI test using row/column potentials; opportunity costs nonnegative ⇒ optimal.

Solution

Step 1 — VAM (Vogel’s Approximation Method)

For each row/column, compute the penalty = difference between two smallest costs.

Initial penalties:

• $S_1$: 13, 16 → penalty = 3.
• $S_2$: 14, 17 → penalty = 3.
• $S_3$: 18, 27 → penalty = 9.
• A: 17, 21 → 4.
• B: 16, 18 → 2.
• C: 14, 18 → 4.
• D: 13, 23 → 10.

Max penalty = 10 at D. Smallest in D = 13 (at $S_1$). Allocate $\min(11,15)=11$ to $(S_1,D)$.

$S_1$ exhausted. Remaining D demand = 15-11 = 4.

Updated table (drop $S_1$ row):

Penalties:

• $S_2$: 14, 17 → 3.
• $S_3$: 18, 27 → 9.
• A: 17, 32 → 15.
• B: 18, 27 → 9.
• C: 14, 18 → 4.
• D: 23, 41 → 18.

Max = 18 at D. Smallest in D = 23 (at $S_2$). Allocate $\min(13,4)=4$ to $(S_2,D)$.

D exhausted. Remaining $S_2$ avail = 13-4 = 9.

Updated table (drop D):

Penalties:

• $S_2$: 14, 17 → 3.
• $S_3$: 18, 27 → 9.
• A: 17, 32 → 15.
• B: 18, 27 → 9.
• C: 14, 18 → 4.

Max = 15 at A. Smallest in A = 17 ($S_2$). Allocate $\min(9,6)=6$ to $(S_2,A)$.

A exhausted. Remaining $S_2$ = 9-6 = 3.

Updated table:

Penalties:

• $S_2$: 14, 18 → 4.
• $S_3$: 18, 27 → 9.
• B: 18, 27 → 9.
• C: 14, 18 → 4.

Max = 9 (tie at $S_3$, B). Pick B. Smallest in B = 18 ($S_2$). Allocate $\min(3,10)=3$ to $(S_2,B)$.

$S_2$ exhausted. Remaining B = 10-3 = 7.

Updated table:

Only $S_3$ left. Allocate $\min(19,7)=7$ to $(S_3,B)$, then $\min(12,12)=12$ to $(S_3,C)$.

Step 2 — IBFS allocations and cost

Cost = $11(13)+6(17)+3(18)+4(23)+7(27)+12(18)$ $=143+102+54+92+189+216=796$.

Step 3 — MODI test for optimality

Let $u_i$ = row potentials, $v_j$ = column potentials. For occupied cells: $u_i+v_j=c_{ij}$.

Set $u_1=0$.

From $(S_1,D)=13$: $u_1+v_D=13\Rightarrow v_D=13$. From $(S_2,D)=23$: $u_2+v_D=23\Rightarrow u_2=10$. From $(S_2,A)=17$: $u_2+v_A=17\Rightarrow v_A=7$. From $(S_2,B)=18$: $u_2+v_B=18\Rightarrow v_B=8$. From $(S_3,B)=27$: $u_3+v_B=27\Rightarrow u_3=19$. From $(S_3,C)=18$: $u_3+v_C=18\Rightarrow v_C=-1$.

Row potentials: $u_1=0, u_2=10, u_3=19$. Column potentials: $v_A=7, v_B=8, v_C=-1, v_D=13$.

For unoccupied cells, opportunity cost $\Delta_{ij}=c_{ij}-(u_i+v_j)$:

• $(S_1,A)$: $21-(0+7)=14$.
• $(S_1,B)$: $16-(0+8)=8$.
• $(S_1,C)$: $25-(0+(-1))=26$.
• $(S_2,C)$: $14-(10+(-1))=5$.
• $(S_3,A)$: $32-(19+7)=6$.
• $(S_3,D)$: $41-(19+13)=9$.

All $\Delta_{ij}\ge 0$ ⇒ IBFS is optimal.

Answer