Let's learn about Hungarian Algorithm in A-Level Maths, which is:
- Used for allocation problems
- Usually possible to match any 'person' to any 'task'
- with a 'cost' associated with each matching
The Algorithm:
1. Find the opportunity cost matrix
2. Test for an optimal assignment
3. Revise the opportunity cost matrix and return to step 2. [IF OPTIMAL THEN STOP]
e.g. Q) 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.
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 min from each row)
NB. It does not matter whether you reduce the rows or the columns first, however exam questions may specify an order.
Reduce columns (subtract column min from each column)
[In this case, no reduction is possible]
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)
Minimum number of lines needed = 3
3 < 4 ∴ not optimal
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.
Second Opportunity Cost Matrix : Minimum number of lines needed = 4
4 = 4 ∴ optimal
Returning to the original cost matrix:
Making the final assignment:
- 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
NB. 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.
Drafted by Eunice (Maths)