The Hungarian method on one card

Lesson notes

Solve an assignment problem using the Hungarian method

Key points

• Square the matrix: If lecturers and courses differ in number, add a dummy row or column of zeros.
• Row reduction: Subtract each row's smallest preparation time from every entry in that row.
• Column reduction: Then subtract each column's minimum; skipping this is the classic lost mark.
• Minimum lines: Cover all zeros with the fewest lines; optimal when lines equal matrix order.
• Adjust the matrix: Subtract the smallest uncovered value from uncovered cells, add it at intersections.
• Assign on zeros: Pick one zero per row and column, then sum original times for total.

Takeaway: Reduce rows and columns, then lines must equal the matrix order.

Hungarian methodopportunity cost matrix