Assignment problem
Assigning n agents to n tasks at the lowest cost: cost matrix, bipartite model, the Hungarian method (row then column reduction, covering the zeros, adjustment) and reading off the optimal assignment.
- 26 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Assignment: what is it?
Show the answer
A choice of one task per agent, such that every agent has a task and every task is taken by a single agent.
With n agents and n tasks there are n! possible assignments. The aim is the one with the lowest total cost.
What does this program print?
```python
from itertools import permutations
cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
print(min(sum(cost[i][p[i]] for i in range(3)) for p in permutations(range(3))))`9101411
Show the answer
9The program tries all 3! = 6 assignments. The best: agent 0 on task 1 (2), agent 1 on task 0 (6), agent 2 on task 2 (1), which makes 9. Taking, row after row, the cheapest cell whose task is still free would give 2 + 3 + 5 = 10, and the diagonal 14.
The Hungarian method starts by subtracting its … from each row, then its minimum from each ….
Show the answer
The Hungarian method starts by subtracting its minimum from each row, then its minimum from each column.
Each row and each column then contains at least one zero, and no cost is negative. The optimal assignment has not changed.
Cost matrix: what is it?
Show the answer
A square table whose cell (i, j) gives the price of having agent i do task j: one row per agent, one column per task.
An assignment reads as picking one cell per row and per column; its cost is the sum of the chosen cells.