Hungarian Algorithm (Allocation) - Decision Maths

Explaining the Hungarian Algorithm used for allocation problems in decision maths.

Enjoy! 

HideShow resource information
  • Created by: Charlotte
  • Created on: 13-04-13 21:01
Preview of Hungarian Algorithm (Allocation) - Decision Maths

First 216 words of the document:

HUNGARIAN ALGORITHM (Allocation) AQA Spec.
Hungarian Algorithm
Used for allocation problems
Usually possible to match any 'person' to any 'task'
There is 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:
1 2 3 4 Row Minimum
A 25 4 15 7 4 Reduce Rows
B 6 3 8 18 3 (subtract Row Min. from each row)
C 13 2 2 4 2
NB. It does not matter whether you
D 1 1 2 1 1 reduce the rows or the columns
first, however exam questions may
specify an order.
21 0 11 3
3 0 5 15 Reduce Columns
11 0 0 2 (subtract Column Min. from each column)
0 0 1 0 [In this case, no reduction is possible]
0 0 0 0 Column Minimum
You now have your first Opportunity Cost Matrix:
21 0 11 3
3 0 5 15
11 0 0 2
0 0 1 0

Other pages in this set

Page 2

Preview of page 2

Here's a taster:

Is It Optimal?
Find the minimum number of lines needed to
21 0 11 3 cover all of the `0's in your opportunity cost
matrix.
3 0 5 15 (There may be different ways of doing this.)
11 0 0 2 We want this number to equal the number of
assignments (the number of rows and columns).
0 0 1 0 i.e.…read more

Comments

daviesg

Excellent presentation for the hungarian allocation (AQA D2)

Similar Mathematics resources:

See all Mathematics resources »See all resources »