Hungarian Algorithm
- In IB Mathematics, it used for allocation problems
- usually possible to match any 'person' to any 'task'
- There is a 'cost' associated with each matching
The Algorithm:
- Find the opportunity cost matrix
- Test for an optimal assignment
- Revise the opportunity cost matrix and return to step 2. [IF OPTIMAL THEN STOP]
Example question
Four workers A, B, C & D are assigned to tasks 1, 2, 3 & 4. The values in the matrix show the completion time in days for each worker when assigned to each task. Minimise the total time taken to complete all four tasks.
In IB Mathematics, we want to assign each worker to a task, and achieve the shortest time to complete all of the tasks.
Starting with the given cost matrix:
- Reduce rows (subtract Row Minimum from each row)
- It does not matter whether you reduce rows or columns first, however exam questions may specify an order.
- Reduce columns (subtract Column Minimum from each column)
- In this case, no reduction is possible.
In IB Mathematics, you now have your first Opportunity Cost Matrix:
Is It Optimal?
Find the minimum number of lines needed to cover all of the ‘0’s in your opportunity cost matrix.
(There may be different ways of doing this.)
We want this number to equal the number of assignments (the number of rows and columns).
i.e. in this case 4 (there are 4 rows and 4 columns)
Therefore we need to revise the opportunity cost matrix:
- Find the smallest number not covered by a line.
- Smallest uncovered number = 3
- Subtract this number from all the numbers not covered by a straight line.
- Add this number to all numbers at an intersection of two straight lines
Again, find the minimum number of lines needed to cover all of the ‘0’s in your opportunity cost matrix.
Optimal assignment so STOP.
Making the final assignment:
In IB Mathematics, we make the final assignment using the ‘0’s in the matrix.
Row 3 has only one ‘0’ so we must use it.
Choose the other ‘0’s, so there is one in each row and column.
(There may be several different possibilities; however they will all give the same optimal allocation.)
Optimal Allocation:
A --> 2
B --> 1
C --> 3
D --> 4
Note: In IB Mathematics, you may be asked to find more than one optimal allocation. In this case, find the other possibilities of having a '0' in each row and column.
This is the end of this topic.