| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.5 This is a standard application of the maximum matching algorithm (alternating path method) from Decision Mathematics D2, followed by a routine allocation problem. While it requires careful execution of the algorithm, it's a textbook procedure with no novel insight needed—slightly easier than average due to its algorithmic nature and small problem size. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02e Bipartite graphs: K_{m,n} notation |
| \multirow{8}{*}{Sub-editor} | \multirow{2}{*}{} | Article | ||||
| \(P\) | \(R\) | \(S\) | \(T\) | \(W\) | ||
| Jeremy ( \(J\) ) | 56 | 56 | 51 | 57 | 58 | |
| Kath ( \(K\) ) | 53 | 52 | 53 | 54 | 54 | |
| Laura ( \(L\) ) | 57 | 55 | 52 | 58 | 60 | |
| Mohammed ( \(M\) ) | 59 | 55 | 53 | 59 | 57 | |
| Natalie ( \(N\) ) | 57 | 57 | 53 | 59 | 60 | |
| Ollie ( \(O\) ) | 58 | 56 | 51 | 56 | 57 | |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Bipartite graph correct | B1 | |
| Incomplete matching correct (clearly shown, or shown on a separate bipartite graph) | B1 | [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(E-P-A-R-B-S\) | M1, A1 | A valid alternating path from \(E\) to \(S\), written out; This path written out (not just shown on diagram) |
| \(A=R\ \ B=S\ \ C=T\ \ D=W\ \ E=P\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Add a dummy column of equal costs of at least 60 minutes | B1 | |
| Substantially correct attempt at reducing rows (at most one error) | M1 | |
| Substantially correct attempt at reducing columns (at most one error) | M1 | Correct reduced cost matrix, with rows reduced first |
| Correct final reduced cost matrix | A1 | cao |
| Follow through their reduced cost matrix for crossing through 0s and augmenting (without errors) | M1 | |
| Augment by 2 in a single augmentation | A1 | cao |
| Follow through their matrix for crossing through 0s and augmenting (correct for theirs) | M1 | |
| (Either) correct final matrix | A1 | cao |
| \(J=S\ \ K=P\ \ L=R\ \ M=W\ \ O=T\) | B1 | |
| Correct method: \(51+53+55+57+56=272\); \(272 \times £0.25 = £68\) | M1, A1 | £68 (cao) with units |
# Question 4:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Bipartite graph correct | B1 | |
| Incomplete matching correct (clearly shown, or shown on a separate bipartite graph) | B1 | [2] |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $E-P-A-R-B-S$ | M1, A1 | A valid alternating path from $E$ to $S$, written out; This path written out (not just shown on diagram) |
| $A=R\ \ B=S\ \ C=T\ \ D=W\ \ E=P$ | B1 | cao | [3] |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Add a dummy column of equal costs of at least 60 minutes | B1 | |
| Substantially correct attempt at reducing rows (at most one error) | M1 | |
| Substantially correct attempt at reducing columns (at most one error) | M1 | Correct reduced cost matrix, with rows reduced first |
| Correct final reduced cost matrix | A1 | cao | [4] |
| Follow through their reduced cost matrix for crossing through 0s and augmenting (without errors) | M1 | |
| Augment by 2 in a single augmentation | A1 | cao |
| Follow through their matrix for crossing through 0s and augmenting (correct for theirs) | M1 | |
| (Either) correct final matrix | A1 | cao | [4] |
| $J=S\ \ K=P\ \ L=R\ \ M=W\ \ O=T$ | B1 | |
| Correct method: $51+53+55+57+56=272$; $272 \times £0.25 = £68$ | M1, A1 | £68 (cao) with units | [3] |
---4 Anya $( A )$, Ben $( B )$, Connie $( C )$, Derek $( D )$ and Emma $( E )$ work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page $( P )$, restaurant review $( R )$, sports news $( S )$, theatre review $( T )$ and weather report $( W )$.
Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review.
Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report.
Emma is only interested in writing the problem page but this has already been given to Anya.\\
(i) Draw a bipartite graph to show the possible pairings between the writers ( $A , B , C , D$ and $E$ ) and the articles ( $P , R , S , T$ and $W$ ). On your bipartite graph, show who has been given which article by the editor.\\
(ii) Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching.
When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each.
The table shows how long, in minutes, each sub-editor would typically take to check each article.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\multirow{8}{*}{Sub-editor} & \multirow{2}{*}{} & \multicolumn{5}{|c|}{Article} \\
\hline
& & $P$ & $R$ & $S$ & $T$ & $W$ \\
\hline
& Jeremy ( $J$ ) & 56 & 56 & 51 & 57 & 58 \\
\hline
& Kath ( $K$ ) & 53 & 52 & 53 & 54 & 54 \\
\hline
& Laura ( $L$ ) & 57 & 55 & 52 & 58 & 60 \\
\hline
& Mohammed ( $M$ ) & 59 & 55 & 53 & 59 & 57 \\
\hline
& Natalie ( $N$ ) & 57 & 57 & 53 & 59 & 60 \\
\hline
& Ollie ( $O$ ) & 58 & 56 & 51 & 56 & 57 \\
\hline
\end{tabular}
\end{center}
The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.\\
(iii) Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs $\pounds 0.25$, calculate the total cost of checking the articles each week.
\hfill \mbox{\textit{OCR D2 2009 Q4 [16]}}