← 2020 Paper 2

UPSC 2020 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 the initial basic feasible solution of the following transportation problem by Vogel’s approximation method (VAM) and use it to find the optimal solution and the transportation cost. Cost matrix (rows = sources S1,S2,S3; cols = destinations D1,D2,D3,D4): S1: [10, 0, 20, 11], availability 15 S2: [12, 8, 9, 20], availability 25 S3: [0, 14, 16, 18], availability 10 Demand: D1=5, D2=20, D3=15, D4=10.

Technique

Vogel’s Approximation Method for the initial BFS (penalty = gap between two least costs), then MODI/u–v method for optimality; one loop pivot ($\theta=5$) reaches the optimum.

Solution

Step 0 — Check balance

Total supply $=15+25+10=50$; total demand $=5+20+15+10=50$. Balanced, so no dummy needed. A basic feasible solution will have $m+n-1=3+4-1=6$ occupied cells.

Step 1 — Vogel’s Approximation Method (penalties = difference of two smallest costs)

We repeatedly compute, for each remaining row/column, the penalty = (2nd smallest cost) − (smallest cost), pick the row/column with the largest penalty, and allocate the maximum to its least-cost cell.

Allocation 1. Penalties — Rows: S1 $|0,10|\to10$, S2 $|8,9|\to1$, S3 $|0,14|\to14$; Cols: D1 $|0,10|\to10$, D2 $|0,8|\to8$, D3 $|9,16|\to7$, D4 $|11,18|\to7$. Largest $=14$ (S3). Least cost in S3 is cell $(S3,D1)=0$. Allocate $\min(10,5)=5$ → $x_{31}=5$. D1 satisfied (remove column D1); S3 left with $5$.

Allocation 2. Remaining cols D2,D3,D4. Penalties — Rows: S1 $|0,11|\to11$, S2 $|8,9|\to1$, S3 $|14,16|\to2$; Cols: D2 $|0,8|\to8$, D3 $|9,16|\to7$, D4 $|11,18|\to7$. Largest $=11$ (S1). Least cost in S1 (over D2,D3,D4) is $(S1,D2)=0$. Allocate $\min(15,20)=15$ → $x_{12}=15$. S1 exhausted (remove row S1); D2 left with $5$.

Allocation 3. Rows S2,S3; cols D2,D3,D4. Penalties — Rows: S2 $|8,9|\to1$, S3 $|14,16|\to2$; Cols: D2 $|8,14|\to6$, D3 $|9,16|\to7$, D4 $|18,20|\to2$. Largest $=7$ (D3). Least cost in D3 is $(S2,D3)=9$. Allocate $\min(25,15)=15$ → $x_{23}=15$. D3 satisfied (remove D3); S2 left with $10$.

Allocation 4. Rows S2,S3; cols D2,D4. Penalties — Rows: S2 $|8,20|\to12$, S3 $|14,18|\to4$; Cols: D2 $|8,14|\to6$, D4 $|18,20|\to2$. Largest $=12$ (S2). Least cost in S2 (over D2,D4) is $(S2,D2)=8$. Allocate $\min(10,5)=5$ → $x_{22}=5$. D2 satisfied (remove D2); S2 left with $5$.

Allocation 5 & 6. Only D4 remains (demand $10$) with S2 ($5$) and S3 ($5$). Allocate $x_{24}=5$ and $x_{34}=5$. All supplies/demands met.

Initial BFS (VAM)

Occupied cells $=6=m+n-1$ (non-degenerate). Cost:

Step 2 — Optimality test by MODI (u–v method)

Set $u_1=0$ and solve $u_i+v_j=c_{ij}$ on the $6$ basic cells $\{(1,2),(2,2),(2,3),(2,4),(3,1),(3,4)\}$:

Opportunity costs $\Delta_{ij}=c_{ij}-u_i-v_j$ for the non-basic cells:

$\Delta_{14}=-1<0$, so the solution is not optimal; cell $(S1,D4)$ should enter the basis.

Step 3 — Loop pivot on entering cell $(S1,D4)$

Closed loop with alternating $+/-$ signs starting at $(1,4)$:

The minimum allocation on the "$-$" cells is $\theta=\min\{x_{24},x_{12}\}=\min\{5,15\}=5$. Adjust:

$(2,4)$ leaves the basis.

New solution

Step 4 — Re-test optimality (MODI)

New potentials ($u_1=0$): $u_2=8,\ u_3=7;\ v_1=-7,\ v_2=0,\ v_3=1,\ v_4=11$. Opportunity costs for all non-basic cells:

All $\Delta_{ij}\ge0$ ⟹ optimal.

Step 5 — Optimal cost

Answer