Assignment Problem: The Hungarian Method Step by Step
The assignment problem pairs workers to jobs at minimum total cost. Learn the Hungarian method: row and column reduction, covering zeros and the final assignment.
The assignment problem matches n workers to n jobs, one each, so that the total cost (or time) is minimum. It is a special transportation problem where every supply and demand is 1. The data is an n by n cost matrix. If the matrix is not square, add dummy rows or columns of zeros. If the goal is to maximize profit, convert it by subtracting every entry from the largest entry, then minimize.
The Hungarian method has these steps. One, row reduction: subtract the smallest value in each row from every entry in that row. Two, column reduction: subtract the smallest value in each column from every entry in that column. Three, cover all zeros with the minimum number of horizontal and vertical lines. If the number of lines equals n, an optimal assignment exists among the zeros. Four, otherwise find the smallest uncovered value, subtract it from all uncovered entries and add it to entries covered twice, then repeat step three.
To make the final assignment, start with rows or columns that contain exactly one zero, assign that zero, and cross out the rest of its row and column. Continue until every row has one assignment. The total cost is read from the original matrix, not the reduced one. When several assignments have the same cost, the problem has multiple optimal solutions.
Key points
- Square matrix needed, add dummy rows or columns if not.
- Row reduction then column reduction.
- Minimum covering lines = n means optimal.
- Otherwise adjust with the smallest uncovered value.
- Maximization: subtract entries from the largest value first.
Worked example
Costs for 2 workers and 2 jobs: W1 = [8, 6], W2 = [5, 9]. Row reduction: W1 becomes [2, 0], W2 becomes [0, 4]. Column reduction: column 1 minimum 0, column 2 minimum 0, no change. Zeros are at (W1, J2) and (W2, J1), and two lines cover them, equal to n = 2. Assign W1 to J2 and W2 to J1. Total cost from the original matrix = 6 + 5 = 11.
Common questions
What if there are more jobs than workers?
Add dummy workers (rows of zeros) to make the matrix square.
How do you turn a maximization assignment into minimization?
Subtract every entry from the largest entry in the matrix and then run the Hungarian method.
Related topics
- Transportation Problem: Northwest Corner, Least Cost and Vogel
- Linear Programming: Formulation and the Graphical Method
- Simplex Method: Steps, Slack Variables and the Tableau
- All topics: Operations Research
BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.