The Hungarian algorithm

The Hungarian algorithm Flashcards

Spec 2.1 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
What does the Hungarian algorithm find?
A complete one-to-one allocation of workers to tasks with the least total cost.
In which order are matrix reductions done?
Rows first (subtract each row minimum), then columns.
How do you test whether an allocation is ready?
Cover all zeros with the fewest straight lines; ready if the number of lines equals nn.
What do you do if fewer than nn lines are needed?
Subtract the smallest uncovered entry from uncovered entries, add it to entries covered twice, then re-test.
What happens to entries covered by exactly one line when augmenting?
They are unchanged.
From which matrix is the final cost found?
The original cost matrix, not the reduced one.
What is a dummy location?
An extra row or column of equal entries (normally 00) that makes the matrix square when numbers are unequal.
What does being matched with the dummy mean?
The worker or task does not take part in the allocation, and adds no cost.
How do you handle a pairing that is impossible?
Put a very large number MM in that cell.
How is a maximum profit problem converted?
Subtract every entry from the largest entry in the original matrix, then minimise.
After converting, how is the maximum profit found?
From the original profit matrix, using the allocation found.
Why does subtracting a constant from a row not change the best allocation?
Every complete allocation uses exactly one entry from that row, so all totals fall by the same amount.

Flashcards