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 \(\pounds 10000\) s) are shown in the table below.
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | 1 | 2 | 3 | 4 |
| Ann | 26 | 30 | 30 | 30 |
| Brenda | 30 | 23 | 26 | 29 |
| Connor | 30 | 25 | 27 | 24 |
| Dave | 30 | 27 | 25 | 21 |
- 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.
- State the value of the maximum sales.
- Show that there is a second allocation that maximises the sales.
(Total 15 marks)