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 n.

What do you do if fewer than n lines are needed?

Subtract the smallest uncovered entry from uncovered entries, add it to entries covered twice, then re-test.

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 0) 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 M 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.

The Hungarian algorithmEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What does the Hungarian algorithm find?

Tap or press Space to reveal

Tap card or press Space to flip

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 $n$ .
What do you do if fewer than $n$ 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 $0$ ) 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 $M$ 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.

Exam questions on The Hungarian algorithm

A firm has three engineers, Ana, Ben and Cleo, and three tasks: wiring (W), testing (T) and installing (I). Each engineer must do exactly one task and each task is done by exactly one engineer. The cost, in £, of each engineer doing each task is given by the matrix $\begin{pmatrix} 8 & 12 & 8 \\ 10 & 7 & 11 \\ 12 & 3 & 9 \end{pmatrix}$ , where the rows are Ana, Ben, Cleo and the columns are W, T, I. The firm wants the total cost to be as small as possible.
Complete the Hungarian algorithm to find the allocation with the least total cost, and state that cost.2 marks
A company has three sales representatives, Dev, Eli and Fay, to send to three regions: North, South and East. Each representative goes to a different region. The expected monthly profit, in £ thousand, of each representative in each region is given by the matrix $\begin{pmatrix} 5 & 13 & 11 \\ 10 & 11 & 14 \\ 5 & 12 & 5 \end{pmatrix}$ , where the rows are Dev, Eli, Fay and the columns are North, South, East. The company wants the total profit to be as large as possible and uses the Hungarian algorithm.
A trainee applies the Hungarian algorithm directly to the original profit matrix, with no conversion. Explain why the allocation found would not be the one the company wants.2 marks
A courier firm has four drivers, P, Q, R and S, and three deliveries, X, Y and Z. Each delivery is made by exactly one driver and each driver makes at most one delivery. The cost, in £, of each driver making each delivery is given by the matrix $\begin{pmatrix} 21 & 27 & 12 \\ 33 & 14 & 26 \\ 32 & 20 & 25 \\ 29 & 38 & 14 \end{pmatrix}$ , where the rows are P, Q, R, S and the columns are X, Y, Z. The firm wants the total cost to be as small as possible.
A dummy delivery is added so that the Hungarian algorithm can be used. Explain why this is needed, and state what should be entered in the dummy column.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).