| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Standard +0.3 This is a straightforward application of the Hungarian algorithm for maximisation on a 4×4 matrix. While it requires multiple mechanical steps (subtracting from maximum, row/column reduction, covering zeros, augmentation), the algorithm is entirely procedural with no problem-solving insight needed. The question is slightly easier than average because it's a standard textbook exercise testing recall of a taught algorithm, though the multiple stages required prevent it from being trivial. |
| Spec | 7.03m Packing extensions: 2D/3D packing and knapsack problems |
| \multirow{2}{*}{} | Stage | |||
| 1 | 2 | 3 | 4 | |
| A | 7 | 8 | 5 | 6 |
| \(B\) | 6 | 9 | 6 | 5 |
| C | 9 | 8 | 5 | 7 |
| \(D\) | 7 | 7 | 6 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Need to maximise so subtract all values from 9 | M1 | |
| Row minimum identified: 1, 0, 0, 2 | ||
| Reducing rows gives matrix with rows: (1,0,3,2), (3,0,3,4), (0,1,4,2), (0,0,1,1) | M1 A1 | |
| Column minimums: 0, 0, 1, 1 | ||
| Reducing columns gives matrix with rows: (1,0,2,1), (3,0,2,3), (0,1,3,1), (0,0,0,0) | A1 | N.B. a different choice of lines will lead to the same final assignment |
| 3 lines required to cover all zeros, apply algorithm | B1 | |
| Augmented matrix with rows: (1,0,1,0*), (3,0*,1,2), (0*,1,2,0), (1,1,0*,0) | M1 A1 | |
| 4 lines required to cover all zeros so allocation is possible | B1 | |
| Stage 1 – \(C\), Stage 2 – \(B\), Stage 3 – \(D\), Stage 4 – \(A\) | A1 | |
| Total number of days \(= 9 + 9 + 6 + 6 = 30\) days | A1 | (10) |
# Question 3:
| Answer/Working | Mark | Guidance |
|---|---|---|
| Need to maximise so subtract all values from 9 | M1 | |
| Row minimum identified: 1, 0, 0, 2 | | |
| Reducing rows gives matrix with rows: (1,0,3,2), (3,0,3,4), (0,1,4,2), (0,0,1,1) | M1 A1 | |
| Column minimums: 0, 0, 1, 1 | | |
| Reducing columns gives matrix with rows: (1,0,2,1), (3,0,2,3), (0,1,3,1), (0,0,0,0) | A1 | N.B. a different choice of lines will lead to the same final assignment |
| 3 lines required to cover all zeros, apply algorithm | B1 | |
| Augmented matrix with rows: (1,0,1,0*), (3,0*,1,2), (0*,1,2,0), (1,1,0*,0) | M1 A1 | |
| 4 lines required to cover all zeros so allocation is possible | B1 | |
| Stage 1 – $C$, Stage 2 – $B$, Stage 3 – $D$, Stage 4 – $A$ | A1 | |
| Total number of days $= 9 + 9 + 6 + 6 = 30$ days | A1 | **(10)** |
---3. A travel company offers a touring holiday which stops at four locations, $A , B , C$ and $D$. The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multirow{2}{*}{} & \multicolumn{4}{|c|}{Stage} \\
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & 7 & 8 & 5 & 6 \\
\hline
$B$ & 6 & 9 & 6 & 5 \\
\hline
C & 9 & 8 & 5 & 7 \\
\hline
$D$ & 7 & 7 & 6 & 6 \\
\hline
\end{tabular}
\end{center}
Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.\\
\hfill \mbox{\textit{OCR D2 Q3 [10]}}