The Hungarian algorithmEdexcel A-Level Further Maths: Subtopic test

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

   (a)

   The rows are reduced first. What is the entry for Ben doing task W in the row-reduced matrix?

   [1 mark]

   • A$0$
   • B$3$
   • C$7$
   • D$10$

   (b)

   The rows and then the columns are reduced. What is the minimum number of straight lines needed to cover every zero in the reduced matrix?

   [1 mark]

   • A$3$
   • B$4$
   • C$1$
   • D$2$

   (c)

   Complete the Hungarian algorithm to find the allocation with the least total cost, and state that cost.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   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)

   The matrix is converted so that the algorithm can find a minimum. What is the entry for Dev in North in the converted matrix?

   [1 mark]

   • A$9$
   • B$5$
   • C$14$
   • D$19$

   (b)

   What is the maximum total expected profit, in £ thousand?

   [1 mark]

   • A$9$
   • B$32$
   • C$33$
   • D$39$

   (c)

   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]

   Total for question 2: 4 marks

3. 3
   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)

   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]

   (b)

   Use the Hungarian algorithm on the 4 by 4 matrix to find which delivery each driver makes and the least total cost. State which driver makes no delivery.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A garage has four mechanics, Kai, Lou, Mia and Ned, and four repair jobs, J1, J2, J3 and J4. Each mechanic does exactly one job. The cost, in £, of each mechanic doing each job is given below in the order J1, J2, J3, J4, where a dash means the mechanic is not qualified for that job. Kai: 44, 23, –, 40. Lou: 28, 43, 45, 34. Mia: 45, 23, 49, 48. Ned: 26, 39, 47, 30. The garage wants the total cost to be as small as possible.

   (a)

   Use the Hungarian algorithm, dealing with the missing entry, to find an allocation with the least total cost, and state that cost.

   [6 marks]

   (b)

   The garage can train Kai to do J3 at a cost of £$31$ for the job, with the training costing £$15$. Use the Hungarian algorithm to decide whether the training is worthwhile.

   [6 marks]

   Total for question 4: 12 marks

End of questions