UPSC Maths 2025 Paper 2 Q4c — Solution

20 marks · Section A

Question

The following table shows all the necessary information on the available supply to each warehouse, the requirement of each market and the unit transportation cost from each warehouse to each market:

	I	II	III	IV	Supply
A	5	2	4	3	22
B	4	8	1	6	15
C	4	6	7	5	8
Requirement	7	12	17	9

The shipping clerk has worked out the following schedule from experience: 12 units from $A$ to II, 1 unit from $A$ to III, 9 units from $A$ to IV, 15 units from $B$ to III, 7 units from $C$ to I and 1 unit from $C$ to III. Find the optimal schedule and minimum total shipping cost.

Technique

Start from the given basic feasible solution and apply the MODI (u–v / modified distribution) method: compute dual potentials, opportunity costs $d_{ij}=c_{ij}-(u_i+v_j)$ , identify the entering cell, trace the closed loop, and reallocate.

Solution

Balance check. Total supply $=22+15+8=45$ ; total requirement $=7+12+17+9=45$ . The problem is balanced, so a feasible transportation plan exists.

A note on the data: the clerk’s “experience” schedule given in the problem is not optimal — it costs 105, whereas the true optimum costs 104. One MODI iteration corrects it, as shown below.

Step 1 — The given (initial) basic feasible solution.

	I	II	III	IV	Supply
A	–	12	1	9	22
B	–	–	15	–	15
C	7	–	1	–	8
Req	7	12	17	9

Occupied (basic) cells: $A_{II},A_{III},A_{IV},B_{III},C_{I},C_{III}$ — that is $6 = m+n-1 = 3+4-1$ cells (non-degenerate). Initial cost: $Z_0 = 2(12)+4(1)+3(9)+1(15)+4(7)+7(1) = 24+4+27+15+28+7 = 105.$

Step 2 — Dual potentials (MODI). For each basic cell set $u_i+v_j = c_{ij}$ , with $u_A=0$ :

$A_{II}: v_{II}=2$ ; $A_{III}: v_{III}=4$ ; $A_{IV}: v_{IV}=3$ .
$B_{III}: u_B+4=1 \Rightarrow u_B=-3$ .
$C_{III}: u_C+4=7 \Rightarrow u_C=3$ ; then $C_{I}: u_C+v_I=4 \Rightarrow v_I=1$ .

So $u=(0,-3,3)$ , $v=(1,2,4,3)$ .

Step 3 — Opportunity costs $d_{ij}=c_{ij}-(u_i+v_j)$ for non-basic cells.

cell	$c_{ij}$	$u_i+v_j$	$d_{ij}$
$A_I$	5	1	+4
$B_I$	4	-2	+6
$B_{II}$	8	-1	+9
$B_{IV}$	6	0	+6
$C_{II}$	6	5	+1
$C_{IV}$	5	6	−1

The only negative entry is $d_{C_{IV}} = -1$ , so the current solution is not optimal. The entering cell is $C_{IV}$ .

Step 4 — Closed loop and reallocation. Form the closed loop on basic cells starting at $C_{IV}$ : $C_{IV}(+) \to C_{III}(-) \to A_{III}(+) \to A_{IV}(-) \to C_{IV}.$ The minus cells carry $C_{III}=1$ and $A_{IV}=9$ ; the reallocation amount is $\theta = \min(1,9) = 1.$ Adjust: $C_{IV}\!\uparrow1$ , $C_{III}\!\downarrow1\,(\to0)$ , $A_{III}\!\uparrow1\,(\to2)$ , $A_{IV}\!\downarrow1\,(\to8)$ . Cell $C_{III}$ leaves the basis.

Step 5 — New solution.

	I	II	III	IV	Supply
A	–	12	2	8	22
B	–	–	15	–	15
C	7	–	–	1	8
Req	7	12	17	9

Cost: $Z_1 = Z_0 + \theta\cdot d_{C_{IV}} = 105 + 1(-1) = 104$ . Directly: $Z_1 = 2(12)+4(2)+3(8)+1(15)+4(7)+5(1) = 24+8+24+15+28+5 = 104.$

Step 6 — Optimality check. Recompute potentials: $u=(0,-3,2)$ , $v=(2,2,4,3)$ . All non-basic opportunity costs are now $\ge 0$ : $d_{A_I}=3,\ d_{B_I}=5,\ d_{B_{II}}=9,\ d_{B_{IV}}=6,\ d_{C_{II}}=2,\ d_{C_{III}}=1.$ All $\ge 0 \Rightarrow$ the solution is optimal. Since every reduced cost is strictly positive, the optimum is unique.

Answer

Optimal schedule:

$A\to$ II: 12, $A\to$ III: 2, $A\to$ IV: 8
$B\to$ III: 15
$C\to$ I: 7, $C\to$ IV: 1

$\boxed{\;\text{Minimum total shipping cost} = 104.\;}$