UPSC 2021 Maths Optional Paper 2 Q1e — Step-by-Step Solution

10 marks · Section A

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

Question

Assign 5 jobs (A-E) to 5 employees (I-V) to minimise total processing time:

	I	II	III	IV	V
A	10	5	13	15	16
B	3	9	18	13	6
C	10	7	2	2	2
D	7	11	9	7	12
E	7	9	10	4	12

Technique

Standard Hungarian method: row/col reduction, line covering, iterative reduction until 5-line cover exists.

Solution

Hungarian method.

Step 1 — Row reduction (subtract row min)

Row mins: A:5, B:3, C:2, D:7, E:4.

M_1=\begin{pmatrix}5 & 0 & 8 & 10 & 11\\ 0 & 6 & 15 & 10 & 3\\ 8 & 5 & 0 & 0 & 0\\ 0 & 4 & 2 & 0 & 5\\ 3 & 5 & 6 & 0 & 8\end{pmatrix}.

Step 2 — Column reduction (subtract col min)

Col mins: I:0, II:0, III:0, IV:0, V:0. (Each column already has a 0.)

So $M_2=M_1$ .

Step 3 — Find assignment with one zero per row/col

Zeros:

A: (A,II)
B: (B,I)
C: (C,III),(C,IV),(C,V) — 3 zeros
D: (D,I),(D,IV)
E: (E,IV)

Try matching greedy on unique zeros first:

A→II (only zero in row A)
B→I (only zero in row B)
E→IV (only zero in row E)
D: rows I and IV both taken; no zero left.

Conflict. Need another iteration.

Cover all zeros with lines.

Try lines: col II (covers A), col I (covers B,D), col IV (covers E,D), row C (covers all C zeros).

Lines: {col I, col II, col IV, row C} = 4 lines. Cover all zeros? Let’s check uncovered:

A: (A,II) covered.
B: (B,I) covered.
C: covered by row C.
D: (D,I) covered, (D,IV) covered.
E: (E,IV) covered.

All zeros covered with 4 lines. Since 4 < 5, not yet optimal.

Step 4 — Reduce uncovered

Uncovered rows: A, B, D, E. Uncovered cols: III, V.

Uncovered entries:

(A,III)=8, (A,V)=11
(B,III)=15, (B,V)=3
(D,III)=2, (D,V)=5
(E,III)=6, (E,V)=8

Min uncovered = 2 (at (D,III)).

Subtract 2 from uncovered entries; add 2 to doubly-covered (intersections of two covering lines: row C ∩ each of cols I, II, IV — that’s (C,I), (C,II), (C,IV)).

M_3=\begin{pmatrix}5 & 0 & 6 & 10 & 9\\ 0 & 6 & 13 & 10 & 1\\ 10 & 7 & 0 & 2 & 0\\ 0 & 4 & 0 & 0 & 3\\ 3 & 5 & 4 & 0 & 6\end{pmatrix}.

Step 5 — Re-try assignment

Zeros:

A: (A,II)
B: (B,I)
C: (C,III),(C,V)
D: (D,I),(D,III),(D,IV)
E: (E,IV)

Greedy:

A→II.
B→I.
E→IV.
C and D remaining; C can go to III or V; D can go to III (I,IV taken).

If D→III: C→V. Check all assigned: A→II, B→I, C→V, D→III, E→IV. ✓

Step 6 — Compute total cost

From original matrix:

A→II: 5
B→I: 3
C→V: 2
D→III: 9
E→IV: 4

Total = $5+3+2+9+4=23$ .

Answer

\boxed{\;\text{Assignment: A→II, B→I, C→V, D→III, E→IV; total time }=23\text{ hours.}\;}