The following table represents the estimated costs of assigning jobs to machines. Solve this assignment problem to minimize the total cost.
Machine: M₁, M₂, M₃, M₄
Job J₁: 8, 24, 28, 32
Job J₂: 8, 13, 17, 19
Job J₃: 8, 15, 19, 22
Is the assignment unique for the total minimum cost ? Justify your answer and obtain an alternate assignment, if it exists.
15 marks · directive: Solve
The core of a good answer
After adding a dummy job J₄ with zero costs and applying the Hungarian method, the minimum total cost is 40, with J₁ → M₁, J₂ → M₂, J₃ → M₃ (M₄ idle); the assignment is not unique because the final reduced matrix has a 2 × 2 block of zeros for J₂, J₃ on M₂, M₃, giving the alternate J₁ → M₁, J₂ → M₃, J₃ → M₂, also costing 40.
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
An unbalanced (3 × 4) assignment problem: balance it with a dummy row, then apply the Hungarian method (row and column reduction, covering zeros with the minimum number of lines, and revising until n lines are needed). The second half asks for uniqueness: look for more than one complete set of independent zeros in the optimal reduced matrix.
Answer outline
Introduction
There are 3 jobs and 4 machines, so add a dummy job J₄ with cost 0 on every machine; one machine will stay idle.
Step 1: Row and column reduction
- Subtract row minima (8, 8, 8, 0):
- J₁: 0, 16, 20, 24; J₂: 0, 5, 9, 11; J₃: 0, 7, 11, 14; J₄: 0, 0, 0, 0.
- Column minima are all 0 (dummy row), so the matrix is unchanged.
Step 2: First revision
- Zeros covered by 2 lines (column M₁, row J₄) < 4.
- Smallest uncovered entry = 5: subtract from uncovered, add at intersection.
- J₁: 0, 11, 15, 19; J₂: 0, 0, 4, 6; J₃: 0, 2, 6, 9; J₄: 5, 0, 0, 0.
Step 3: Second revision
- Minimum lines = 3 (column M₁, rows J₂ and J₄) < 4.
- Smallest uncovered entry = 2.
- J₁: 0, 9, 13, 17; J₂: 2, 0, 4, 6; J₃: 0, 0, 4, 7; J₄: 7, 0, 0, 0.
Step 4: Third revision
- Minimum lines = 3 (columns M₁, M₂, row J₄) < 4.
- Smallest uncovered entry = 4.
- J₁: 0, 9, 9, 13; J₂: 2, 0, 0, 2; J₃: 0, 0, 0, 3; J₄: 11, 4, 0, 0.
- Now 4 lines are needed: optimal.
Step 5: Make the assignment
- J₁ has a single zero at M₁: J₁ → M₁ (cross M₁ for J₃).
- Column M₄ has a single zero at J₄: J₄ → M₄ (dummy).
- J₂ and J₃ both have zeros at M₂ and M₃: J₂ → M₂, J₃ → M₃.
- Cost = 8 + 13 + 19 = 40.
Step 6: Uniqueness
- The zeros at (J₂, M₂), (J₂, M₃), (J₃, M₂), (J₃, M₃) form a 2 × 2 block, so a second independent choice exists.
- Alternate: J₁ → M₁, J₂ → M₃, J₃ → M₂, J₄ → M₄; cost = 8 + 17 + 15 = 40.
- So the optimal assignment is not unique; in both M₄ is left idle.
Conclusion
Minimum total cost = 40 by either J₁M₁, J₂M₂, J₃M₃ or J₁M₁, J₂M₃, J₃M₂. A brute-force check of all 24 ways of assigning three jobs to distinct machines confirms 40 as the minimum and these two as the only optimal assignments.
Facts to remember
- An unbalanced assignment problem is balanced by adding dummy rows or columns with zero cost.
- Hungarian method: an optimal assignment exists among the zeros when the minimum number of covering lines equals the order of the matrix.
- Revision step: subtract the smallest uncovered element from all uncovered elements and add it to elements at line intersections.
- Multiple optimal solutions arise when the final reduced matrix allows more than one complete set of independent zeros.