Hungarian Method Calculator (Assignment Problem Solver)
Solve balanced assignment problems step-by-step using the Hungarian algorithm, from row and column reduction to optimal zero-line coverage.
| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Worker 1 | |||
| Worker 2 | |||
| Worker 3 |
The Assignment Problem & Hungarian Algorithm: An Academic Guide
A rigorous mathematical walkthrough of the Kuhn-Munkres (Hungarian) algorithm for bipartite weighted matching and minimal cost task allocation.
1. What Problem Does the Assignment Model Solve?
The Assignment Problem is a classical combinatorial optimization model where n workers (or machines) must be allocated to n tasks (or jobs) on a strict one-to-one basis. Given a cost matrix C where cᵢⱼ represents the expense or time incurred when assigning worker i to task j, the objective is to find a bijective permutation that minimizes total assignment cost ∑ cᵢⱼ xᵢⱼ subject to ∑ xᵢⱼ = 1 for each row and column, with xᵢⱼ ∈ {0, 1}. While integer simplex can solve it, Harold Kuhn's Hungarian method achieves this in strongly polynomial O(n³) time.
2. The 5-Step Hungarian Algorithm (Kuhn-Munkres)
Find the minimum value in each row and subtract it from all entries in that row. This creates at least one zero in every row without altering the optimal assignment relative order.
Find the minimum value in each column of the row-reduced matrix and subtract it from all elements in that column, ensuring every column contains at least one zero.
Draw the minimum number of horizontal and vertical lines needed to cover all zeros. If the number of lines equals n, an optimal zero assignment exists (proceed to Step 5). If lines < n, go to Step 4.
Locate the smallest uncovered element k. Subtract k from every uncovered cell, and add k to cells located at the intersection of two covering lines. Uncovered entries change; single-line entries remain constant. Return to Step 3.
Identify unique zeros in rows and columns to form an independent set of n coordinates. Map these coordinates back to the original matrix to compute minimal total cost.
3. Solved Academic Example: 4 Workers × 4 Tasks
Follow the step-by-step reduction of a 4×4 cost matrix to verify the exact engine output.
| Worker / Machine | Task 1 (T₁) | Task 2 (T₂) | Task 3 (T₃) | Task 4 (T₄) |
|---|---|---|---|---|
| Worker 1 (W₁) | 9 | 2 | 7 | 8 |
| Worker 2 (W₂) | 6 | 4 | 3 | 7 |
| Worker 3 (W₃) | 5 | 8 | 1 | 8 |
| Worker 4 (W₄) | 7 | 6 | 9 | 4 |
A. Row Reduction (Subtract Row Minimums)
Row 1 min = 2 → [7, 0, 5, 6] | Row 2 min = 3 → [3, 1, 0, 4] | Row 3 min = 1 → [4, 7, 0, 7] | Row 4 min = 4 → [3, 2, 5, 0]. Each row now possesses at least one zero.
B. Column Reduction (Subtract Column Minimums)
Column 1 minimum is 3 → [4, 0, 1, 0]. Columns 2, 3, and 4 already have minimum 0 and remain unchanged: Col 2 = [0, 1, 7, 2], Col 3 = [5, 0, 0, 5], Col 4 = [6, 4, 7, 0].
C. Line Covering & Independence Verification
The resulting zero coordinates are (W₁, T₂), (W₂, T₁), (W₂, T₃), (W₃, T₃), (W₄, T₁), and (W₄, T₄). The minimum number of lines required to cover all zeros is exactly 4 (= n). Thus, an optimal assignment is immediately achieved without requiring Step 4 shifts.
| Assigned Worker | Matched Task | Original Cost |
|---|---|---|
| Worker 1 (W₁) | Task 2 (T₂) | 2 |
| Worker 2 (W₂) | Task 1 (T₁) | 6 |
| Worker 3 (W₃) | Task 3 (T₃) | 1 |
| Worker 4 (W₄) | Task 4 (T₄) | 4 |
Optimal Minimal Cost Result
Total Cost Z* = 2 + 6 + 1 + 4 = 13. (Every worker is assigned to a distinct task with global cost minimized, perfectly matching the calculator's Hungarian solver).
4. Common Pitfalls in Assignment Problems
Maximization Objectives Without Inversion
If the objective is maximizing profit or productivity instead of minimizing cost, convert the matrix by subtracting every cell value from the global maximum element, or multiply all entries by -1.
Unbalanced Dimensions (Rectangular Matrices)
The Hungarian algorithm requires a square n × n matrix. If workers ≠ tasks, add dummy rows or dummy columns with 0 cost entries to establish balance before reduction.
Adding Instead of Subtracting During Step 4 Shifts
In Step 4, subtract k from uncovered cells and add k only to intersection cells. Do not modify cells covered by a single line.