โ Operations Research learning pathOperations Research ยท Module 5 of 10
Assignment problem
One-to-one allocation at minimum cost.
๐ Key ideas
- The assignment problem assigns n jobs to n workers, one each, minimising cost or time.
- The Hungarian method solves it efficiently.
- Steps: subtract row minimums, subtract column minimums, cover zeros with minimum lines, adjust until n lines are needed.
- Maximisation problems are converted by subtracting all values from the largest.
- Unbalanced problems use dummy rows or columns.
๐ก Real-life example: Like assigning five interns to five projects so total completion time is lowest.
Assignment problemMatching n tasks to n agents one-to-one
Hungarian methodAlgorithm for assignment problems
Opportunity cost matrixMatrix after row and column reductions
Dummy rowFictitious agent to balance the matrix