Pratidin
2026 · Mathematics Optional Paper II · 15 marksMainsQuestion 3c

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

Answer

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

Step 2: First revision

Step 3: Second revision

Step 4: Third revision

Step 5: Make the assignment

Step 6: Uniqueness

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

Facts to remember

Sources used for the explanation

Write a timed answer in the app