D2 June 2019 Q3
3. Five friends have rented a house that has five bedrooms. They each require their own bedroom. The table below shows how each friend rated the five bedrooms, A, B, C, D and E, where 0 is low and 10 is high.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| Frank | 5 | 0 | 7 | 3 | 4 |
| Gill | 5 | 3 | 8 | 10 | 1 |
| Harry | 4 | 3 | 7 | 9 | 0 |
| Imogen | 6 | 3 | 6 | 5 | 4 |
| Jiao | 0 | 2 | 7 | 3 | 2 |
Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total of all the ratings. You must make your method clear and show the table after each stage.
| Scheme | Marks |
|---|---|
| Since maximising, subtract all elements from some value \(\geqslant 10\) | |
| e.g. \(\begin{bmatrix} 5 & 10 & 3 & 7 & 6 \\ 5 & 7 & 2 & 0 & 9 \\ 6 & 7 & 3 & 1 & 10 \\ 4 & 7 & 4 & 5 & 6 \\ 10 & 8 & 3 & 7 & 8 \end{bmatrix}\) | M1 |
| Reduce rows \(\begin{bmatrix} 2 & 7 & 0 & 4 & 3 \\ 5 & 7 & 2 & 0 & 9 \\ 5 & 6 & 2 & 0 & 9 \\ 0 & 3 & 0 & 1 & 2 \\ 7 & 5 & 0 & 4 & 5 \end{bmatrix}\) and then columns \(\begin{bmatrix} 2 & 4 & 0 & 4 & 1 \\ 5 & 4 & 2 & 0 & 7 \\ 5 & 3 & 2 & 0 & 7 \\ 0 & 0 & 0 & 1 & 0 \\ 7 & 2 & 0 & 4 & 3 \end{bmatrix}\) | M1 A1 |
| \(\begin{bmatrix} 1 & 3 & 0 & 4 & 0 \\ 4 & 3 & 2 & 0 & 6 \\ 4 & 2 & 2 & 0 & 6 \\ 0 & 0 & 1 & 2 & 0 \\ 6 & 1 & 0 & 4 & 2 \end{bmatrix}\) followed by (eg) \(\begin{bmatrix} 1 & 3 & 0 & 6 & 0 \\ 2 & 1 & 0 & 0 & 4 \\ 2 & 0 & 0 & 0 & 4 \\ 0 & 0 & 1 & 4 & 0 \\ 6 & 1 & 0 & 6 & 2 \end{bmatrix}\) | M1 A1ft M1 A1 |
| Optimal allocation is F = E, G = D, H = B, I = A, J = C | A1 |
| 8 marks |
Notes
1M1: Subtracting from some value which must be \(\geqslant 10\) or all values made negative and then adding a value which must be \(\geqslant 10\). Condone no more than two errors
2M1: Reducing rows and then columns – candidates may combine the two stages of converting from a maximum to a minimum problem and row reduction which is acceptable. (Condone two errors).
1A1: CAO
3M1: Double covered +e; one uncovered –e ; and one single covered unchanged. 3 lines to 4 lines needed
2A1ft: Follow through on their previous table – no errors
4M1: One double covered +e; one uncovered –e; and one single covered unchanged. 4 lines needed to 5 lines needed (so getting to an optimal table)
3A1: CSO on final table (so must have scored all previous marks)
4A1: CAO – this mark is dependent on all M marks being awarded. Allocation must be written clearly. Just labelling zeros in their table scores A0.
Special case: Minimising can score at most M0 M1 A1 (Row and column reduction) M0 A0 (Simplification: no 3 zero cover lines to 4). M1 A0 A0 (4 lines to 5). 3/8 marks