← 2023 Paper 2

UPSC 2023 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

A department head has 5 subordinates and 5 jobs to be performed. The time (in hours) that each subordinate will take to perform each job is given in the matrix below:

How should the jobs be assigned, one to each subordinate, so as to minimize the total time? Also, obtain the total minimum time to perform all the jobs if the subordinate $IV$ cannot be assigned job $C$.

Technique

Hungarian algorithm — row/column reduction; cover zeros with minimum lines; if fewer than $n$ lines, subtract uncovered min from uncovered and add to doubly-covered; repeat.

Solution

Apply the Hungarian algorithm (minimization, $5\times 5$).

Part 1 — Unrestricted optimum

Step 1.1 — Row reduction. Subtract the row minimum from each row.

Step 1.2 — Column reduction. Every column minimum is already $0$; matrix unchanged.

Step 1.3 — Attempt an assignment of zeros.

Singleton-zero rows first: II→D, III→B, V→A (V has a single zero at A). Remaining rows: I has zeros at A (taken), C, E; IV has zeros at A (taken), D (taken). IV has no available zero — assignment incomplete. (Only 4 zeros assignable so far.)

Step 1.4 — Cover all zeros with the minimum number of lines.

Standard marking:

• Mark unassigned row IV.
• From row IV, mark columns A, D (containing zeros).
• From column A, mark row V (assigned at A); from column D, mark row II (assigned at D).
• No new marks possible.

Lines: unmarked rows {I, III} and marked columns {A, D}. Total: 4 lines $<5$, so optimum not yet reached.

Step 1.5 — Revise the matrix.

Smallest uncovered element (in rows {II, IV, V} × columns {B, C, E}):

Subtract $2$ from every uncovered element; add $2$ to every element covered twice (rows {I, III} × columns {A, D}); leave singly-covered elements unchanged.

Step 1.6 — Re-attempt assignment.

Singletons: II→D, III→B, V→A. IV now has zeros at A (taken), C, D (taken); assign IV→C. I has zeros at C (taken), E; assign I→E.

Complete assignment: I–E, II–D, III–B, IV–C, V–A.

Step 1.7 — Total time.

Part 2 — With restriction IV ≠ C

Replace entry $(IV,C)=11$ by $\infty$ (so the Hungarian algorithm cannot select it) and rerun. Row reductions through Step 1.5 are unaffected by this change because:

• IV’s row minimum is still $9$ (at A and D, not C);
• column C’s minimum is still $0$ (from row I).

Hence the matrix after Step 1.5 differs only in the (IV, C) entry, which is $\infty$ instead of $2$ — but $(IV,C)$ was the smallest uncovered element, so the smallest uncovered element here is now:

Step 2.1 — Revise with $\theta=3$.

Subtract $3$ from uncovered, add $3$ to doubly-covered. The (IV, C) cell stays $\infty$.

Step 2.2 — Assign.

Singletons: III→B. Then:

• V has only A: V→A.
• IV has zeros at A (taken) and D; assign IV→D.
• II has zeros at D (taken) and E; assign II→E.
• I has zeros at C and E (taken); assign I→C.

Complete assignment: I–C, II–E, III–B, IV–D, V–A.

(Uniqueness: any swap fails. E.g. I→E forces II→D; then V→A; IV needs D or A — both taken — fail. So the assignment is unique.)

Step 2.3 — Total time (with restriction).

Costs: I–C $=4$, II–E $=8$, III–B $=7$, IV–D $=9$, V–A $=6$.

The restriction costs the department exactly one extra hour ($34-33=1$).