D2 June 2008 Q6
6. Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, \(A\), \(B\), \(C\) and \(D\). Each salesperson must attend just one fair and each fair must be attended by just one salesperson.
The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown in the table below.
| \(A\) | \(B\) | \(C\) | \(D\) | |
|---|---|---|---|---|
| Joe | 48 | 49 | 42 | 42 |
| Min-Seong | 53 | 49 | 51 | 50 |
| Olivia | 51 | 53 | 48 | 48 |
| Robert | 47 | 50 | 46 | 43 |
(a) Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the total expected sales from the four salespersons. You must make your method clear and show the table after each stage. (10)
(b) State all possible optimal allocations and the optimal total value. (4)
| Scheme | Marks |
|---|---|
| Since maximising, subtract all elements from some \(n \geqslant 53\) \(\begin{bmatrix}5&4&11&11\\0&4&2&3\\2&0&5&5\\6&3&7&10\end{bmatrix}\) | M1 A1 (2) |
| Reduce rows \(\begin{bmatrix}1&0&7&7\\0&4&2&3\\2&0&5&5\\3&0&4&7\end{bmatrix}\) then columns \(\begin{bmatrix}1&0&5&4\\0&4&0&0\\2&0&3&2\\3&0&2&4\end{bmatrix}\) | M1 A1ft (2) |
| Lines through the Min-Seong row and column B; Minimum element 1 \(\begin{bmatrix}0&0&4&3\\0&5&0&0\\1&0&2&1\\2&0&1&3\end{bmatrix}\) | M1 A1ft A1ft (3) |
| Lines through the Joe and Min-Seong rows and column B, or through columns A and B and the Min-Seong row | M1 A1ft A1ft (3) |
| (10) |
Notes
The scheme shows the covering lines as sketches; they are described in words here.
| Scheme | Marks | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\begin{bmatrix}0&1&4&3\\0&6&0&0\\0&0&1&0\\1&0&0&2\end{bmatrix}\) \(\begin{bmatrix}0&0&3&2\\1&6&0&0\\1&0&1&0\\2&0&0&2\end{bmatrix}\) | M1 A1ft (2) | ||||||||||||
| M1 A1 (2) | ||||||||||||
| (4) | |||||||||||||
| (14 marks) |