A company has 4 workers and 4 jobs. Each worker can perform any job, but the cost (in ₹) of assigning a worker to a job varies, as shown in the table given below :
Worker \ Job | 1 | 2 | 3 | 4
1 | 9 | 2 | 7 | 8
2 | 6 | 4 | 3 | 7
3 | 5 | 8 | 1 | 8
4 | 7 | 6 | 9 | 4
Assign each worker to exactly one job such that the total cost of assignment is minimum.
10 marks · directive: Solve
The core of a good answer
By the Hungarian method the optimal assignment is Worker 1 → Job 2, Worker 2 → Job 1, Worker 3 → Job 3, Worker 4 → Job 4, with minimum total cost ₹(2 + 6 + 1 + 4) = ₹13; this is the unique optimum (the next best assignment costs ₹14).
An outline written by upsc.help, not an official UPSC answer; every fact checked by a separate review. How we work
What the question asks
A balanced 4 × 4 assignment problem. Use the Hungarian method: row reduction, column reduction, cover zeros with the minimum number of lines, and assign when four independent zeros exist. Show each matrix.
Answer outline
Introduction
The cost matrix is square (4 workers, 4 jobs), so the problem is balanced. Subtracting a constant from a row or column does not change the optimal assignment.
Step 1: Row reduction (row minima 2, 3, 1, 4)
- W1: 7 0 5 6
- W2: 3 1 0 4
- W3: 4 7 0 7
- W4: 3 2 5 0
Step 2: Column reduction (column minima 3, 0, 0, 0)
- W1: 4 0 5 6
- W2: 0 1 0 4
- W3: 1 7 0 7
- W4: 0 2 5 0
Step 3: Optimality test and assignment
- Row W1 has a single zero at Job 2: assign W1 → J2, cross column 2.
- Row W3 has a single zero at Job 3: assign W3 → J3, cross column 3.
- Row W2: remaining zero at Job 1: assign W2 → J1, cross column 1.
- Row W4: remaining zero at Job 4: assign W4 → J4.
- Four independent zeros, i.e. the minimum number of covering lines is 4 = n, so the solution is optimal.
Step 4: Cost
- Total = c₁₂ + c₂₁ + c₃₃ + c₄₄ = 2 + 6 + 1 + 4 = ₹13.
- Check: the sum of all reductions is 2 + 3 + 1 + 4 + 3 = 13, a lower bound that is attained.
- Enumerating all 24 permutations in Python confirms ₹13 is the unique minimum.
Conclusion
Optimal assignment: W1-J2, W2-J1, W3-J3, W4-J4 at a minimum cost of ₹13.
Examples and data to cite
- The Hungarian method was published by H. W. Kuhn in 1955, building on the work of König and Egerváry.
- Assignment problems are a special case of the transportation problem with all supplies and demands equal to 1.
Facts to remember
- Adding or subtracting a constant from any row or column does not change the optimal assignment.
- Optimal when n independent zeros can be selected (minimum covering lines = n).
- If lines < n, subtract the smallest uncovered element from uncovered cells and add it at intersections.
- The sum of row and column reductions is a lower bound on the optimal cost.