D2 January 2006 Q1
1. A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.
| Hot dogs and beef burgers (H) | Ice cream (I) | Popcorn, candyfloss and drinks (P) | Snacks and hot drinks (S) | |
|---|---|---|---|---|
| Site A | 267 | 272 | 276 | 261 |
| Site B | 264 | 271 | 278 | 263 |
| Site C | 267 | 273 | 275 | 263 |
| Site D | 261 | 269 | 274 | 257 |
Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage. (13)
| Scheme | Marks |
|---|---|
| To maximise, subtract all entries from \(n \geqslant 278\) | M1 |
| e.g. \(\begin{bmatrix}11&6&2&17\\14&7&0&15\\11&5&3&15\\17&9&4&21\end{bmatrix}\) | A1 (2) |
| Reduce rows \(\begin{bmatrix}9&4&0&15\\14&7&0&15\\8&2&0&12\\13&5&0&17\end{bmatrix}\) then columns \(\begin{bmatrix}1&2&0&3\\6&5&0&3\\0&0&0&0\\5&3&0&5\end{bmatrix}\) | M1 A1ft A1ft (3) |
| Lines through row C and column P; Min element = 1 \(\begin{bmatrix}0&1&0&2\\5&4&0&2\\0&0&1&0\\4&2&0&4\end{bmatrix}\) | M1 A1ft A1 (3) |
| Lines through columns H and P and row C; Min element = 1 \(\begin{bmatrix}0&0&0&1\\5&3&0&1\\1&0&2&0\\4&1&0&3\end{bmatrix}\) or lines through rows A and C and column P; Min element = 2 \(\begin{bmatrix}0&1&2&2\\3&2&0&0\\0&0&3&0\\2&0&0&2\end{bmatrix}\) | M1 A1ft A1ft (3) |
| then lines through rows A and C and column P; min element 1 \(\begin{bmatrix}0&0&1&1\\4&2&0&0\\1&0&3&0\\3&0&0&2\end{bmatrix}\) optimal | |
| So A – H, B – P, C – S, D – I or A – H, B – S, C – I, D – P (both £1077) | M1 A1 (2) |
| (13 marks) |
Notes
The scheme shows the covering lines as small sketches; they are described in words here (rows A–D are the sites, columns H, I, P, S the kiosks).