| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm with a 4×4 matrix requiring routine row/column reductions and covering lines. While it has multiple steps (10 marks), it's a mechanical procedure with no problem-solving insight needed, making it slightly easier than average for A-level. |
| Spec | 7.06f Integer programming: branch-and-bound method |
| Film | Musical | Ballet | Concert | |
| Andrew | 5 | 20 | 12 | 18 |
| Betty | 6 | 18 | 15 | 16 |
| Carlos | 4 | 21 | 9 | 15 |
| Davina | 5 | 16 | 11 | 13 |
| Answer | Marks | Guidance |
|---|---|---|
| Subtract row minima: rows become \((0,15,7,13)\), \((0,12,9,10)\), \((0,17,5,11)\), \((0,11,6,8)\) | M1 A1 | |
| Subtract column minima | M1 A1 | |
| Cover zeros, augment as necessary | M1 A1 | |
| Optimal assignment found | M1 | |
| Andrew–Film, Betty–Concert, Carlos–Ballet, Davina–Musical (or equivalent optimal) | A1 | |
| Total cost = \(5 + 16 + 9 + 16 = 46\) | A1 A1 | A1 assignment, A1 cost |
# Question 3:
| Subtract row minima: rows become $(0,15,7,13)$, $(0,12,9,10)$, $(0,17,5,11)$, $(0,11,6,8)$ | M1 A1 | |
| Subtract column minima | M1 A1 | |
| Cover zeros, augment as necessary | M1 A1 | |
| Optimal assignment found | M1 | |
| Andrew–Film, Betty–Concert, Carlos–Ballet, Davina–Musical (or equivalent optimal) | A1 | |
| Total cost = $5 + 16 + 9 + 16 = 46$ | A1 A1 | A1 assignment, A1 cost |
---3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& Film & Musical & Ballet & Concert \\
\hline
Andrew & 5 & 20 & 12 & 18 \\
\hline
Betty & 6 & 18 & 15 & 16 \\
\hline
Carlos & 4 & 21 & 9 & 15 \\
\hline
Davina & 5 & 16 & 11 & 13 \\
\hline
\end{tabular}
\end{center}
Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.\\
(10 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q3 [10]}}