← 2014 Paper 2

UPSC 2014 Maths Optional Paper 2 Q2c — 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 to the following transportation problem by Vogel’s approximation method. Also, find its optimal solution and the minimum transportation cost:

Technique

Vogel’s approximation method (VAM) for IBFS; MODI/$u,v$ method for optimality testing.

Solution

Step 1 — Balance check

Total supply $=14+16+5=35$, total demand $=6+10+15+4=35$. Balanced ✓.

Step 2 — VAM iterations

Iteration 1. Penalties (difference between two smallest costs in each row/column):

Max penalty: $O_2$ ($=5$). Cheapest cell in $O_2$: $D_3$ (cost 2). Allocate $\min(16,15)=15$, i.e., $x_{23}=15$. Eliminate column $D_3$ (demand met).

Iteration 2. Updated supply for $O_2$: 1. New penalties (without $D_3$):

Max penalty: $D_4$ ($=3$). Cheapest in $D_4$: $O_3$ (cost 2). Allocate $\min(5,4)=4$, i.e., $x_{34}=4$. Eliminate $D_4$.

Iteration 3. Updated supply for $O_3$: 1. New penalties (without $D_3, D_4$):

Tie max penalty: $O_1$ vs $D_1$ (both 2). Pick $O_1$. Cheapest in $O_1$: $D_2$ (cost 4). Allocate $\min(14,10)=10$, i.e., $x_{12}=10$. Eliminate $D_2$.

Iteration 4. Updated $O_1$ supply: 4. Only $D_1$ left (demand 6). Allocate vertically: $x_{11}=4,\;x_{21}=1,\;x_{31}=1$ (filling remaining supply at each origin against $D_1$‘s demand).

Step 3 — Initial BFS

Number of allocations: $6=m+n-1=3+4-1$ ⇒ non-degenerate.

Total cost (IBFS): $24+40+8+30+4+8=\mathbf{114}$.

Step 4 — Optimality check (MODI / $u,v$ method)

For each allocated cell, $u_i+v_j=c_{ij}$. Set $u_1=0$:

• $x_{11}$: $v_1=6$.
• $x_{12}$: $v_2=4$.
• $x_{21}$: $u_2=8-v_1=2$.
• $x_{23}$: $v_3=2-u_2=0$.
• $x_{31}$: $u_3=4-v_1=-2$.
• $x_{34}$: $v_4=2-u_3=4$.

For non-allocated cells, compute $\Delta_{ij}=c_{ij}-u_i-v_j$:

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

Answer