| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 10 |
| 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 row/column reduction steps. While it requires careful arithmetic and systematic working through the algorithm, it involves no novel problem-solving—students are explicitly told which algorithm to use and how to start (reduce rows first). The context is straightforward and part (ii) is trivial interpretation. Slightly easier than average due to being a direct algorithmic application. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| 1 pm | 2 pm | 3 pm | 4 pm | 5 pm | ||
| Mrs Rowan | \(R\) | 3 | 4 | 2 | 7 | 1 |
| Dr Silverbirch | \(S\) | 5 | 10 | 6 | 6 | 6 |
| Mr Thorn | \(T\) | 4 | 7 | 3 | 5 | 3 |
| Ms Willow | \(W\) | 6 | 8 | 4 | 8 | 3 |
| Sgt Yew | \(Y\) | 8 | 8 | 7 | 4 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Modify table by subtracting each entry from a constant value | M1 | |
| Correct table (i.e. this \(\pm\) a constant throughout, with no negative values) | A1 | [2] |
| Substantially correct attempt to reduce rows (at most 2 independent errors) | M1 | |
| Substantially correct attempt to reduce columns (at most 2 independent errors) | M1 | |
| Their reduced cost matrix | A1 | [3] |
| Cross out 0's using minimum number of lines; substantially correct attempt at augmenting (at most 2 errors) | M1 | |
| Their matrix augmented correctly to reach a complete matching | A1 | [2] |
| First matching, cao: Mrs Rowan \(= 4\) pm or \(= 4\) pm; Dr Silverbirch \(= 2\) pm or \(= 5\) pm; Mr Thorn \(= 5\) pm or \(= 2\) pm; Ms Willow \(= 1\) pm or \(= 1\) pm; Sgt Yew \(= 3\) pm or \(= 3\) pm | B1 | |
| Second matching, cao | B1 | [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Mr Thorn | B1 | Follow through their matchings (but not to S) |
# Question 2:
## Part (i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Modify table by subtracting each entry from a constant value | M1 | |
| Correct table (i.e. this $\pm$ a constant throughout, with no negative values) | A1 | [2] |
| Substantially correct attempt to reduce rows (at most 2 independent errors) | M1 | |
| Substantially correct attempt to reduce columns (at most 2 independent errors) | M1 | |
| Their reduced cost matrix | A1 | [3] |
| Cross out 0's using minimum number of lines; substantially correct attempt at augmenting (at most 2 errors) | M1 | |
| Their matrix augmented correctly to reach a complete matching | A1 | [2] |
| First matching, cao: Mrs Rowan $= 4$ pm or $= 4$ pm; Dr Silverbirch $= 2$ pm or $= 5$ pm; Mr Thorn $= 5$ pm or $= 2$ pm; Ms Willow $= 1$ pm or $= 1$ pm; Sgt Yew $= 3$ pm or $= 3$ pm | B1 | |
| Second matching, cao | B1 | [2] |
## Part (ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Mr Thorn | B1 | Follow through their matchings (but not to S) | [1] |
---2 In an investigation into a burglary, Agatha has five suspects who were all known to have been near the scene of the crime, each at a different time of the day. She collects evidence from witnesses and draws up a table showing the number of witnesses claiming sight of each suspect near the scene of the crime at each possible time.
Suspect
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Time}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& & 1 pm & 2 pm & 3 pm & 4 pm & 5 pm \\
\hline
Mrs Rowan & $R$ & 3 & 4 & 2 & 7 & 1 \\
\hline
Dr Silverbirch & $S$ & 5 & 10 & 6 & 6 & 6 \\
\hline
Mr Thorn & $T$ & 4 & 7 & 3 & 5 & 3 \\
\hline
Ms Willow & $W$ & 6 & 8 & 4 & 8 & 3 \\
\hline
Sgt Yew & $Y$ & 8 & 8 & 7 & 4 & 3 \\
\hline
\end{tabular}
\end{center}
\end{table}
(i) Use the Hungarian algorithm on a suitably modified table, reducing rows first, to find the matchings for which the total number of claimed sightings is maximised. Show your working clearly. Write down the resulting matchings between the suspects and the times.
Further enquiries show that the burglary took place at 5 pm , and that Dr Silverbirch was not the burglar.\\
(ii) Who should Agatha suspect?
\hfill \mbox{\textit{OCR D2 2010 Q2 [10]}}