| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Standard +0.3 This is a standard textbook application of the Hungarian algorithm with clear step-by-step instructions. Part (i) tests recall of the maximisation modification (subtract from maximum), part (ii) is routine arithmetic verification, and part (iii) follows the standard algorithm procedure. The question requires no problem-solving insight—just methodical application of a learned algorithm. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.03m Packing extensions: 2D/3D packing and knapsack problems |
| \multirow{6}{*}{Cadet} | \multirow[b]{3}{*}{
| 2330 | 0130 | 0330 | 0530 | 0730 | |||
| \(G\) | 8 | 0 | 7 | 1 | 1 | ||||
| H | 9 | 2 | 7 | 0 | 2 | ||||
| Ieuan | I | 10 | 4 | 9 | 3 | 5 | |||
| Jenni | \(J\) | 7 | 2 | 6 | 1 | 2 | |||
| Ken | \(K\) | 10 | 8 | 9 | 6 | 7 | |||
| 2330 | 0130 | 0330 | 0530 | 0730 | |
| \(G\) | 0 | 6 | 0 | 3 | 4 |
| \(H\) | 0 | 5 | 1 | 5 | 4 |
| \(I\) | 0 | 4 | 0 | 3 | 2 |
| \(J\) | 0 | 3 | 0 | 2 | 2 |
| \(K\) | 0 | 0 | 0 | 0 | 0 |
2 The cadets in Blue Team have been set a task that requires them to get inside a guarded building. Every two hours one of them will attempt to get inside the building. Each cadet will have one attempt.
The table shows a score for each cadet attempting to get inside the building at each time. The higher the score the more likely the cadet is to succeed.
Time
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
\multirow{6}{*}{Cadet} & \multirow[b]{3}{*}{\begin{tabular}{l}
Gary \\
Hilary \\
\end{tabular}} & \multicolumn{2}{|r|}{2330} & 0130 & 0330 & 0530 & 0730 \\
\hline
& & $G$ & 8 & 0 & 7 & 1 & 1 \\
\hline
& & H & 9 & 2 & 7 & 0 & 2 \\
\hline
& Ieuan & I & 10 & 4 & 9 & 3 & 5 \\
\hline
& Jenni & $J$ & 7 & 2 & 6 & 1 & 2 \\
\hline
& Ken & $K$ & 10 & 8 & 9 & 6 & 7 \\
\hline
\end{tabular}
\end{center}
(i) Explain how to modify the table so that the Hungarian algorithm can be used to find the matching for which the total score is maximised.\\
(ii) Show that, after modifying the table and then reducing rows and then columns, the reduced cost matrix becomes:
\begin{center}
\begin{tabular}{ c | c | c | c | c | c }
& 2330 & 0130 & 0330 & 0530 & 0730 \\
\hline
$G$ & 0 & 6 & 0 & 3 & 4 \\
\hline
$H$ & 0 & 5 & 1 & 5 & 4 \\
\hline
$I$ & 0 & 4 & 0 & 3 & 2 \\
\hline
$J$ & 0 & 3 & 0 & 2 & 2 \\
\hline
$K$ & 0 & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
(iii) Complete the application of the Hungarian algorithm, stating how each table was formed. Write down the order in which the cadets should attempt to get into the building to maximise the total score. If the cadets use this solution, which one is least likely to succeed?
\hfill \mbox{\textit{OCR D2 2012 Q2 [8]}}