2 Granny is on holiday in Amsterdam and has bought some postcards. She wants to send one card to each member of her family. She has given each card a score to show how suitable it is for each family member. The higher the score the more suitable the card is.
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Family member}
| \multirow{9}{*}{Postcard} | | Adam | Barbara | Charlie | Donna | Edward | Fiona |
| Painted barges | \(P\) | 2 | 4 | 2 | 6 | 0 | 4 |
| Quaint houses | \(Q\) | 3 | 5 | 3 | 5 | 3 | 4 |
| Reichsmuseum | \(R\) | 6 | 7 | 6 | 6 | 6 | 8 |
| Scenic view | \(S\) | 4 | 6 | 4 | 4 | 0 | 4 |
| Tulips | \(T\) | 1 | 0 | 1 | 4 | 0 | 5 |
| University | \(U\) | 3 | 4 | 4 | 4 | 3 | 3 |
| View from air | \(V\) | 7 | 5 | 7 | 6 | 7 | 5 |
| Windmills | \(W\) | 4 | 6 | 5 | 4 | 5 | 5 |
\end{table}
Granny adds two dummy columns, \(G\) and \(H\), both with score 0 for each postcard. She then modifies the resulting table so that she can use the Hungarian algorithm to find the matching for which the total score is maximised.
- Explain why the dummy columns were needed, why they should not have positive scores and how the resulting table was modified.
- Show that, after reducing rows and columns, Granny gets this reduced cost matrix.
| A | B | \(C\) | D | \(E\) | \(F\) | \(G\) | \(H\) |
| \(P\) | 4 | 2 | 4 | 0 | 6 | 2 | 2 | 2 |
| \(Q\) | 2 | 0 | 2 | 0 | 2 | 1 | 1 | 1 |
| \(R\) | 2 | 1 | 2 | 2 | 2 | 0 | 4 | 4 |
| \(S\) | 2 | 0 | 2 | 2 | 6 | 2 | 2 | 2 |
| \(T\) | 4 | 5 | 4 | 1 | 5 | 0 | 1 | 1 |
| \(U\) | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| \(V\) | 0 | 2 | 0 | 1 | 0 | 2 | 3 | 3 |
| \(W\) | 2 | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
- Complete the application of the Hungarian algorithm, showing your working clearly. Write down which family member is sent each postcard, and which postcards are not used, to maximise the score.