The Hungarian algorithmEdexcel A-Level Further Maths: Mind map

Exam questions on The Hungarian algorithm

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.
   Complete the Hungarian algorithm to find the allocation with the least total cost, and state that cost.2 marks
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 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
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 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