| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm for minimisation with a 4×4 matrix. The question requires only mechanical execution of a standard algorithm (row reduction, column reduction, covering zeros, adjustment) with no problem-solving insight or complications. It's easier than average because it's purely procedural with clear steps, though it requires careful arithmetic and bookkeeping. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Alice | Bhavin | Carl | Dieter | |
| Strip wallpaper | 5 | 3 | 5 | 4 |
| Paint | 7 | 5 | 6 | 4 |
| Hang wallpaper | 8 | 4 | 7 | 6 |
| Replace fittings | 5 | 3 | 2 | 3 |
\begin{enumerate}
\item Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:
\end{enumerate}
\begin{itemize}
\item strip the wallpaper,
\item paint the woodwork and ceiling,
\item hang the new wallpaper,
\item replace the fittings and tidy up.
\end{itemize}
The table below shows the time, in hours, that each of the friends is likely to take to complete each job.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& Alice & Bhavin & Carl & Dieter \\
\hline
Strip wallpaper & 5 & 3 & 5 & 4 \\
\hline
Paint & 7 & 5 & 6 & 4 \\
\hline
Hang wallpaper & 8 & 4 & 7 & 6 \\
\hline
Replace fittings & 5 & 3 & 2 & 3 \\
\hline
\end{tabular}
\end{center}
As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.\\
(a) Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.\\
(b) Hence find the minimum time in which the friends can redecorate the lounge.\\
\hfill \mbox{\textit{OCR D2 Q1 [8]}}