| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Standard +0.3 This is a standard textbook application of the Hungarian algorithm for maximisation. Students must convert to minimisation (subtract from maximum), perform row/column reductions, and find optimal assignment. While it requires careful arithmetic and multiple steps, it follows a completely algorithmic procedure with no problem-solving insight needed. The 11 marks reflect the length of working rather than conceptual difficulty. |
| Spec | 7.06f Integer programming: branch-and-bound method |
| \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 | Marks | Guidance |
| Convert to minimisation by subtracting from max (9): reduced matrix formed | M1A1 | |
| Row reduction correct | M1A1 | |
| Column reduction correct | A1 | |
| Lines to cover zeros, augmentation if needed | M1A1 | |
| Optimal assignment identified | A1 | |
| Maximum days stated | A1A1 |
# Question 5:
| Answer | Marks | Guidance |
|--------|-------|----------|
| Convert to minimisation by subtracting from max (9): reduced matrix formed | M1A1 | |
| Row reduction correct | M1A1 | |
| Column reduction correct | A1 | |
| Lines to cover zeros, augmentation if needed | M1A1 | |
| Optimal assignment identified | A1 | |
| Maximum days stated | A1A1 | |
---5. 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.\\
(11 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q5 [11]}}