| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm for maximisation with clear scaffolding. Part (i) tests conceptual understanding of dummy columns (routine for D2), part (ii) is mechanical verification of row/column reduction, and part (iii) completes the algorithm. While multi-step, it requires only procedural execution of a well-practiced algorithm with no novel problem-solving or insight. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.03m Packing extensions: 2D/3D packing and knapsack problems |
| \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 | |
| 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 |
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]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Family member}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
\multirow{9}{*}{Postcard} & \multicolumn{2}{|c|}{} & Adam & Barbara & Charlie & Donna & Edward & Fiona \\
\hline
& Painted barges & $P$ & 2 & 4 & 2 & 6 & 0 & 4 \\
\hline
& Quaint houses & $Q$ & 3 & 5 & 3 & 5 & 3 & 4 \\
\hline
& Reichsmuseum & $R$ & 6 & 7 & 6 & 6 & 6 & 8 \\
\hline
& Scenic view & $S$ & 4 & 6 & 4 & 4 & 0 & 4 \\
\hline
& Tulips & $T$ & 1 & 0 & 1 & 4 & 0 & 5 \\
\hline
& University & $U$ & 3 & 4 & 4 & 4 & 3 & 3 \\
\hline
& View from air & $V$ & 7 & 5 & 7 & 6 & 7 & 5 \\
\hline
& Windmills & $W$ & 4 & 6 & 5 & 4 & 5 & 5 \\
\hline
\end{tabular}
\end{center}
\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.\\
(i) Explain why the dummy columns were needed, why they should not have positive scores and how the resulting table was modified.\\
(ii) Show that, after reducing rows and columns, Granny gets this reduced cost matrix.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & $C$ & D & $E$ & $F$ & $G$ & $H$ \\
\hline
$P$ & 4 & 2 & 4 & 0 & 6 & 2 & 2 & 2 \\
\hline
$Q$ & 2 & 0 & 2 & 0 & 2 & 1 & 1 & 1 \\
\hline
$R$ & 2 & 1 & 2 & 2 & 2 & 0 & 4 & 4 \\
\hline
$S$ & 2 & 0 & 2 & 2 & 6 & 2 & 2 & 2 \\
\hline
$T$ & 4 & 5 & 4 & 1 & 5 & 0 & 1 & 1 \\
\hline
$U$ & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
\hline
$V$ & 0 & 2 & 0 & 1 & 0 & 2 & 3 & 3 \\
\hline
$W$ & 2 & 0 & 1 & 2 & 1 & 1 & 2 & 2 \\
\hline
\end{tabular}
\end{center}
(iii) 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.
\hfill \mbox{\textit{OCR D2 2011 Q2 [12]}}