| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.5 This is a straightforward application of the bipartite matching algorithm with a small, manageable problem (4 people, 4 tasks). Part (i) requires drawing a standard bipartite graph and finding one alternating path to improve a given initial matching—a direct application of the textbook algorithm with no conceptual challenges. The constraints are clearly stated and the problem size is small enough to solve by inspection. This is easier than average A-level content because it's purely algorithmic with no problem-solving insight required, though it's not trivial since students must understand the matching improvement process. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | Bipartite graph: A—M, B—P, C—H, D—S | B1 |
| Ignore further working on graph for incomplete matching or alternating path | ||
| Alternating path: \(D - H - C - S - B - M - A - P\) | B1 | This, or in reverse, listed (not just deduced from labelling of diagram) |
| Matching: A-P, B-M, C-S, D-H | B1 | This matching |
| [3] | ||
| (ii) | Network with precedences correct: A(10), B(2), C(1), D(2), E(2), F(4), G(3), H(2) | M1 |
| A1 | A correct network (directions may be implied) | |
| Forwards pass: Early event times correct: A(10), B(2), C(1), D(2), E(2), F(4) | M1 | Forwards pass |
| A1 ft | Early event times correct (need not use boxes) | |
| Backwards pass: Late event times correct: A(10), B(2), C(1), D(2), E(2), F(4) | M1 | Backwards pass |
| A1 ft | Late event times correct (need not use boxes) | |
| [6] | ||
| (iii) | Completion time: 16 hours | B1 |
| Critical activities: \(A\) \(B\) \(F\) | B1 | Correct list |
| [2] | ||
| (iv) | Cascade chart with structure correct, activities may be collected together or on individual rows | M1 |
| Non-critical activities correct, none split across rows (floats not necessary) | A1 ft | Non-critical activities correct, none split across rows (floats not necessary) |
| Critical activities correct | A1 ft | Critical activities correct |
| [3] |
(i) | Bipartite graph: A—M, B—P, C—H, D—S | B1 | Correct bipartite graph seen |
| | | | Ignore further working on graph for incomplete matching or alternating path |
| Alternating path: $D - H - C - S - B - M - A - P$ | B1 | This, or in reverse, listed (not just deduced from labelling of diagram) |
| Matching: A-P, B-M, C-S, D-H | B1 | This matching |
| | | [3] | |
(ii) | Network with precedences correct: A(10), B(2), C(1), D(2), E(2), F(4), G(3), H(2) | M1 | Precedences correct |
| | | A1 | A correct network (directions may be implied) |
| Forwards pass: Early event times correct: A(10), B(2), C(1), D(2), E(2), F(4) | M1 | Forwards pass |
| | | A1 ft | Early event times correct (need not use boxes) |
| Backwards pass: Late event times correct: A(10), B(2), C(1), D(2), E(2), F(4) | M1 | Backwards pass |
| | | A1 ft | Late event times correct (need not use boxes) |
| | | [6] | |
(iii) | Completion time: 16 hours | B1 | 16 with units |
| | Critical activities: $A$ $B$ $F$ | B1 | Correct list |
| | | [2] | |
(iv) | Cascade chart with structure correct, activities may be collected together or on individual rows | M1 | Structure of chart correct, activities may be collected together or on individual rows |
| | Non-critical activities correct, none split across rows (floats not necessary) | A1 ft | Non-critical activities correct, none split across rows (floats not necessary) |
| | Critical activities correct | A1 ft | Critical activities correct |
| | | [3] | |
---7 Annie (A), Brigid (B), Carla (C) and Diane ( $D$ ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( $M$ ), pasting the paper ( $P$ ), hanging and then trimming the top end of the paper ( $H$ ) and smoothing out the air bubbles and then trimming the lower end of the paper ( $S$ ). They will each do one of these tasks.
\begin{itemize}
\item Annie does not like climbing ladders but she is prepared to do tasks $M , P$ or $S$
\item Brigid gets into a mess with paste so she is only able to do tasks $M$ or $S$
\item Carla enjoys hanging the paper so she wants to do task $H$ or task $S$
\item Diane wants to do task $H$
\end{itemize}
Initially Annie chooses task $M$, Brigid task $S$ and Carla task $H$.
\begin{enumerate}[label=(\roman*)]
\item Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path.
Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
\item Maximin value $=$
Route $=$
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2007 Q7 [14]}}