How do we allocate workers to tasks for the lowest total cost?
Model an assignment problem as a bipartite graph and solve it with the Hungarian algorithm to minimise total cost.
How to model an allocation as a bipartite matching, apply the Hungarian algorithm of row and column reduction and covering zeros, and read off the optimal minimum-cost assignment.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
You must set up the cost matrix, apply the Hungarian algorithm step by step, and state the optimal allocation and its total cost.
The assignment problem
An assignment problem allocates each of workers to one of tasks so that every worker has exactly one task and the total cost is minimised. It is a bipartite matching: workers on one side, tasks on the other, with a cost on each possible pairing.
The Hungarian algorithm
The Hungarian algorithm works on the cost matrix to create a set of zeros marking an optimal assignment.
When the fewest covering lines equal the number of rows, you can pick one zero in each row and column; those positions are the optimal assignment.
Maximisation problems
If the goal is to maximise (for example total profit), convert to a minimisation first by subtracting every entry from the largest entry, then apply the same algorithm. The resulting assignment maximises the original quantity.