Hungarian algorithm as a linear programme
Studying this course? Keep your progress in one place.
Key facts
- Let if worker does task and 0 otherwise: first subscript worker, second task.
- Minimise cost , or maximise profit directly.
- Each worker does exactly one task and each task is done by exactly one worker: equalities, variables.
- More workers than tasks: each worker does at most one task.
- An LP can add conditions the Hungarian algorithm cannot.
Turning it into an LP
Use a binary variable for each worker and task pairing: 1 if worker does task , 0 otherwise.
For workers and tasks define a binary variable for every pairing:
The first subscript is the worker (row of the matrix) and the second is the task (column).
A complete allocation is a choice of values of , and the cost is read from the cost matrix.
- worker does task
- First subscriptworker (row)
- Second subscripttask (column)
What does mean?
The objective function
Only chosen pairings add their cost, so the total is . Minimise it, or maximise profit directly.
Only chosen pairings () add their cost, so the total cost is
To minimise cost, minimise this. For maximum profit use profits and maximise . No conversion is needed in an LP.
- Minimise cost
- Maximise profit
Worked example
Write the objective function for the costs .
- 1
Row 1 gives .
- 2
Row 2 gives .
For a profit matrix, what do you do to the objective function?
The constraints
Each worker does exactly one task and each task is done by exactly one worker, with .
Each worker does exactly one task and each task is done by exactly one worker.
- For each worker : ( constraints).
- For each task : ( constraints).
Also . That is equality constraints and variables.
For : worker 2 gives , and task 3 gives .
| Each worker | Each task | |
|---|---|---|
| Constraint | ||
| How many | constraints | constraints |
Each worker
- Constraint:
- How many:
- constraints
Each task
- Constraint:
- How many:
- constraints
How many equality constraints and variables does a allocation problem have?
Unequal numbers and impossible pairings
More workers than tasks means each worker does at most one task. An impossible pairing is left out or set to 0.
Unequal numbers. With more workers than tasks, every task is done exactly once, but each worker does at most one: . Equalities for every worker would be impossible. This does the same job as a dummy task.
Impossible pairing. If worker cannot do task , leave out, or add . This does the same job as the large number .
Maximising. Keep the profit matrix and maximise .
| More workers than tasks | Impossible pairing | Maximising | |
|---|---|---|---|
| In the LP | Workers: at most one task | Leave out or set it 0 | Maximise profits directly |
| In the algorithm | Dummy task | Large number | Subtract from largest |
More workers than tasks
- In the LP:
- Workers: at most one task
- In the algorithm:
- Dummy task
Impossible pairing
- In the LP:
- Leave out or set it 0
- In the algorithm:
- Large number
Maximising
- In the LP:
- Maximise profits directly
- In the algorithm:
- Subtract from largest
There are 4 workers and 3 tasks. What is the constraint for worker ?
A worked example
An LP can add any linear condition, such as , which is not a row or column condition.
Three technicians and three tasks have profits as shown (a dash means impossible).
The best choice is with profit .
A condition such as (the two pairings cannot both be used) is not a row or column condition, so the Hungarian algorithm cannot handle it, but it can be added to the LP.
It rules out the best allocation. The best remaining is with profit .
| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Technician 1 | 14 | 11 | 9 |
| Technician 2 | 8 | 13 | – |
| Technician 3 | 10 | 7 | 12 |
Task 1
- Technician 1:
- 14
- Technician 2:
- 8
- Technician 3:
- 10
Task 2
- Technician 1:
- 11
- Technician 2:
- 13
- Technician 3:
- 7
Task 3
- Technician 1:
- 9
- Technician 2:
- –
- Technician 3:
- 12
Worked example
Formulate the profit matrix as an LP.
- 1
Objective: maximise , with no term.
- 2
Workers: , , .
- 3
Tasks: , , .
The extra condition is added. What is the new maximum profit?
Try an exam question
A allocation problem has cost matrix entries for worker doing task . Formulate the minimum-cost allocation as a linear programme, defining your variables.
[4 marks]
- [1] if worker does task , and 0 otherwise.
- [1]Minimise .
- [1]Each worker does exactly one task: for .
- [1]Each task is done by exactly one worker: for .
That's the notes covered.
Carry on to the next subtopic.
Try a question
What does mean?
1 mark, marked against the mark scheme
What does mean?
1 mark, marked against the mark scheme