D2 June 2005 Q5
5. Four salesperson \(A\), \(B\), \(C\) and \(D\) are to be sent to visit four companies 1, 2, 3 and 4. Each salesperson will visit exactly one company, and all companies will be visited.
Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in £10 000s) are shown in the table below.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| Ann | 26 | 30 | 30 | 30 |
| Brenda | 30 | 23 | 26 | 29 |
| Connor | 30 | 25 | 27 | 24 |
| Dave | 30 | 27 | 25 | 21 |
(a) Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage. (11)
(b) State the value of the maximum sales. (2)
(c) Show that there is a second allocation that maximises the sales. (2)
| Scheme | Marks |
|---|---|
| To maximise, subtract all entries from \(n \geqslant 30\) | M1 |
| e.g. \(\begin{bmatrix}4&0&0&0\\0&7&4&1\\0&5&3&6\\0&3&5&9\end{bmatrix}\) | A2, 1, 0 (3) |
| Lines through row \(A\) and column 1; minimum uncovered element is 1: so \(\begin{bmatrix}5&0&0&0\\0&6&3&0\\0&4&2&5\\0&2&4&8\end{bmatrix}\) | M1 A2ft1ft0 (3) |
| Lines through row \(A\), column 1 and column 4, min. el. = 2: \(\begin{bmatrix}7&0&0&2\\0&4&1&0\\0&2&0&5\\0&0&2&8\end{bmatrix}\) or lines through rows \(A\) and \(B\) and column 1, min. el. = 2: \(\begin{bmatrix}7&0&0&0\\2&6&3&0\\0&2&0&3\\0&0&2&6\end{bmatrix}\) | M1 A2ft1ft0 (3) |
| \(A - 2\quad B - 4\quad C - 3\quad D - 1\) \(A - 3\quad B - 4\quad C - 1\quad D - 2\) | M1 A1ft (2) |
| (11) |
Notes
The scheme shows the covering lines as small sketches; they are described in words here.
| Scheme | Marks |
|---|---|
| £1160 000 | B2, 1, 0 |
| (2) |
| Scheme | Marks |
|---|---|
| Gives other solution | M1 A1ft |
| (2) | |
| (15 marks) |