โ† Operations Research learning path
Operations Research ยท Module 5 of 10

Assignment problem

One-to-one allocation at minimum cost.

๐Ÿ“– Key ideas

  1. The assignment problem assigns n jobs to n workers, one each, minimising cost or time.
  2. The Hungarian method solves it efficiently.
  3. Steps: subtract row minimums, subtract column minimums, cover zeros with minimum lines, adjust until n lines are needed.
  4. Maximisation problems are converted by subtracting all values from the largest.
  5. 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