| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm to a 4×3 minimization problem with standard tabular data. The algorithm is mechanical (row reduction, column reduction, covering zeros, adjusting), requires no conceptual insight beyond following the procedure, and the unequal sets aspect is handled by a standard dummy column addition. Easier than average as it's pure algorithmic execution with no problem-solving required. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| \cline { 2 - 4 } \multicolumn{1}{c|}{} | Stage | ||
| \cline { 2 - 4 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) |
| Alex | 19 | 69 | 168 |
| Darren | 22 | 64 | 157 |
| Leroy | 20 | 72 | 166 |
| Suraj | 23 | 66 | 171 |
2. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances.
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\cline { 2 - 4 }
\multicolumn{1}{c|}{} & \multicolumn{3}{|c|}{Stage} \\
\cline { 2 - 4 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ \\
\hline
Alex & 19 & 69 & 168 \\
\hline
Darren & 22 & 64 & 157 \\
\hline
Leroy & 20 & 72 & 166 \\
\hline
Suraj & 23 & 66 & 171 \\
\hline
\end{tabular}
\end{center}
Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.\\
\hfill \mbox{\textit{OCR D2 Q2 [9]}}