# Hungarian Algorithm (Allocation) - Decision Maths

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

Enjoy!

Teacher recommended

- Created by: Charlotte
- Created on: 13-04-13 21:01

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

## Comments