← 2024 Paper 2

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

20 marks · Section A

Assignment problem (Hungarian method) · Linear Programming · asked 6× in 13 yrs · Read the full method →

Question

The personnel manager wants to assign officers A, B, C to offices Delhi, Mumbai, Kolkata, Chennai. Relocation costs (Rs. thousand):

Find the assignment minimising total cost.

Technique

Add a dummy officer D (all zeros) to balance the $3\times4$ matrix; apply the Hungarian algorithm.

Solution

Balanced matrix (add dummy row D with costs 0):

Row reduction (subtract each row minimum)

Column minimums are all 0 — no column reduction needed.

Iteration 1

Cover zeros with 2 lines (column 1, row D). Smallest uncovered = 4 (A,Chennai). Subtract 4 from uncovered; add 4 to doubly-covered (D,Delhi).

Iteration 2

3 lines cover all zeros (column 1, column 4, row D). Smallest uncovered = 2 (A,Mumbai). Subtract 2; add to doubly-covered cells.

Iteration 3

3 lines still needed. Smallest uncovered = 2 (B,Chennai). After update:

Now 4 lines cover all zeros (row A, row D, column 1, column 4) — optimality reached.

Assignment

• Row C: only zero at C,Delhi → C → Delhi.
• Row B: B,Delhi is taken; only zero at B,Chennai → B → Chennai.
• Row A: A,Chennai is taken; zero at A,Mumbai → A → Mumbai.
• Row D → Kolkata (dummy; Kolkata goes unstaffed).

Cost

Answer