← 2017 Paper 2

UPSC 2017 Maths Optional Paper 2 Q4b — Step-by-Step Solution

15 marks · Section A

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

Question

For the following transportation problem, find the initial basic feasible solution using Vogel’s approximation method and find the cost.

Technique

Vogel’s Approximation Method — iterate (largest penalty → least-cost cell → allocate → cross out), tracking row/column penalties as (2nd-smallest − smallest) cost; sum cost over occupied cells.

Solution

Step 0 — Balance check

Total supply $=14+9+17=40$; total demand $=8+3+8+13+8=40$. Balanced, so no dummy row/column is needed. A non-degenerate basic feasible solution will have $m+n-1=3+5-1=7$ allocations.

Vogel’s Approximation Method (VAM): repeatedly compute, for every remaining row and column, the penalty = (second-smallest cost) $-$ (smallest cost); pick the row/column with the largest penalty and allocate as much as possible to its least-cost cell; cross out the exhausted row/column; repeat. (Negative costs are handled exactly like any other number when ordering.)

Step 1 — Iteration 1

Penalties (two smallest costs in each line):

• Rows: $O_1:3-0=3$, $O_2:1-(-3)=4$, $O_3:(-1)-(-1)$? smallest $-1$, next $0$ $\Rightarrow 0-(-1)=1$.
• Cols: $D_1:3-1=2$, $D_2:2-(-1)=3$, $D_3:0-(-3)=3$, $D_4:3-0=3$, $D_5:6-5=1$.

Max penalty $=4$ ($O_2$). Least-cost cell in $O_2$ is $(O_2,D_3)=-3$. Allocate $\min(9,8)=8$. → $x_{23}=8$. $D_3$ demand met (0). Cross out $D_3$. ($O_2$ supply $\to1$.)

Step 2 — Iteration 2 (columns $D_1,D_2,D_4,D_5$)

• Rows: $O_1:3-0$? costs $\{4,7,3,6\}\Rightarrow4-3=1$; $O_2$ costs $\{1,2,3,8\}\Rightarrow2-1=1$; $O_3$ costs $\{3,-1,0,5\}\Rightarrow0-(-1)=1$.
• Cols: $D_1:3-1=2$, $D_2:2-(-1)=3$, $D_4:3-0=3$, $D_5:6-5=1$.

Max penalty $=3$ (tie $D_2,D_4$; take $D_2$). Least-cost cell in $D_2$ is $(O_3,D_2)=-1$. Allocate $\min(17,3)=3$. → $x_{32}=3$. $D_2$ demand met. Cross out $D_2$. ($O_3$ supply $\to14$.)

Step 3 — Iteration 3 (columns $D_1,D_4,D_5$)

• Rows: $O_1:\{4,3,6\}\Rightarrow4-3=1$; $O_2:\{1,3,8\}\Rightarrow3-1=2$; $O_3:\{3,0,5\}\Rightarrow3-0=3$.
• Cols: $D_1:3-1=2$, $D_4:3-0=3$, $D_5:6-5=1$.

Max penalty $=3$ (tie $O_3,D_4$; take $O_3$). Least-cost cell in $O_3$ is $(O_3,D_4)=0$. Allocate $\min(14,13)=13$. → $x_{34}=13$. $D_4$ demand met. Cross out $D_4$. ($O_3$ supply $\to1$.)

Step 4 — Iteration 4 (columns $D_1,D_5$)

• Rows: $O_1:\{4,6\}\Rightarrow6-4=2$; $O_2:\{1,8\}\Rightarrow8-1=7$; $O_3:\{3,5\}\Rightarrow5-3=2$.
• Cols: $D_1:3-1=2$, $D_5:6-5=1$.

Max penalty $=7$ ($O_2$). Least-cost cell in $O_2$ is $(O_2,D_1)=1$. Allocate $\min(1,8)=1$. → $x_{21}=1$. $O_2$ supply exhausted. Cross out $O_2$. ($D_1$ demand $\to7$.)

Step 5 — Iteration 5 (rows $O_1,O_3$; columns $D_1,D_5$)

• Rows: $O_1:\{4,6\}\Rightarrow2$; $O_3:\{3,5\}\Rightarrow2$.
• Cols: $D_1:4-3=1$, $D_5:6-5=1$.

Max penalty $=2$ (tie $O_1,O_3$; take $O_1$). Least-cost cell in $O_1$ is $(O_1,D_1)=4$. Allocate $\min(14,7)=7$. → $x_{11}=7$. $D_1$ demand met. Cross out $D_1$. ($O_1$ supply $\to7$.)

Step 6 — Iteration 6 (column $D_5$; rows $O_1,O_3$)

Only $D_5$ remains (demand $8$), supplies $O_1:7,\ O_3:1$. Costs $(O_1,D_5)=6,\ (O_3,D_5)=5$. Allocate to satisfy: $x_{15}=7$ (exhausts $O_1$), then $x_{35}=1$ (exhausts $O_3$ and meets $D_5$).

Step 7 — Allocation table and cost

Number of occupied cells $=7=m+n-1$ → non-degenerate BFS.

Total transportation cost:

Answer