The Assignment Problem: Hungarian Method Step by Step

The assignment problem asks how to assign n workers to n jobs — one worker per job — so that the total cost is minimized (or total profit maximized). It appears everywhere: assigning employees to tasks, machines to orders, or players to positions. The Hungarian method solves it efficiently. This tutorial works through the full procedure.

Solve any assignment problem step by step with the free Assignment Problem Solver.

The Problem

Three workers must each do one of three jobs. The cost matrix (worker × job) is:

📐 Formula

J1 J2 J3 W1 4 2 8 W2 4 3 7 W3 3 1 6

We want the assignment with the lowest total cost.

Step 1: Row Reduction

Subtract the smallest value in each row from every entry in that row:

📐 Formula

Row minimums: W1=2, W2=3, W3=1 W1: 2 0 6 W2: 1 0 4 W3: 2 0 5

Step 2: Column Reduction

Subtract the smallest value in each column from every entry in that column:

📐 Formula

Column minimums: C1=1, C2=0, C3=4 W1: 1 0 2 W2: 0 0 0 W3: 1 0 1

Step 3: Cover the Zeros with Minimum Lines

Draw the fewest horizontal/vertical lines that cover all zeros. If the number of lines equals n (here 3), an optimal assignment exists. If it is fewer, adjust the matrix: subtract the smallest uncovered value from all uncovered cells and add it to every cell covered twice, then repeat.

Step 4: Make the Assignment

Choose one independent zero in each row and column:

📐 Formula

W1 → J2 (cost 2) W2 → J1 (cost 4) W3 → J3 (cost 6) Total minimum cost = 2 + 4 + 6 = 12

The minimum total cost is 12.

Maximization and Unbalanced Problems

For maximization (profit), convert to costs by subtracting every entry from the largest value, then minimize.
For unbalanced problems (more workers than jobs or vice versa), pad the matrix with dummy rows or columns of zeros to make it square.

Assignment vs. Transportation

The assignment problem is a special case of the transportation problem where every supply and demand equals 1. For general many-to-many shipping, use the Transportation Problem Solver instead.

Common Mistakes

Assigning to a non-zero cell — only zeros can be assigned after reduction.
Stopping when lines < n — you must adjust and repeat until the minimum number of covering lines equals n.
Forgetting to convert maximization — subtract from the max first.

Try It Yourself

Enter your cost matrix into the Assignment Problem Solver to see row/column reduction, line covering, and the optimal assignment with its total cost — downloadable as a PDF report.

Key Takeaways

The Hungarian method reduces rows and columns, covers zeros, and assigns independent zeros.
For the example, W1→J2, W2→J1, W3→J3 gives a minimum cost of 12.
Convert maximization to costs and pad unbalanced matrices with dummies.