| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Session | Specimen |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Hungarian algorithm for maximisation with a small 4×4 matrix. The method is algorithmic and routine once learned, requiring matrix reduction and covering lines. Part (c) adds minor complexity by asking students to identify an alternative optimal solution, but this is still procedural. Easier than average A-level maths due to its algorithmic nature with no conceptual problem-solving required. |
| Spec | 7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods7.06d Graphical solution: feasible region, two variables |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | 1 | 2 | 3 | 4 |
| Ann | 26 | 30 | 30 | 30 |
| Brenda | 30 | 23 | 26 | 29 |
| Connor | 30 | 25 | 27 | 24 |
| Dave | 30 | 27 | 25 | 21 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Notes |
| To maximise, subtract all entries from \(n \geq 30\) | M1 | |
| Reduced matrix e.g. \(\begin{bmatrix}4&0&0&0\\0&7&4&1\\0&5&3&6\\0&3&5&9\end{bmatrix}\) | ||
| Minimum uncovered element is 1, giving \(\begin{bmatrix}5&0&0&0\\0&6&3&0\\0&4&2&5\\0&2&4&8\end{bmatrix}\) | M1 A2 ft 1 ft 0 | |
| Further reductions with min. el \(= 2\): \(\begin{bmatrix}7&0&0&2\\0&4&1&0\\0&2&0&5\\0&0&2&8\end{bmatrix}\) then \(\begin{bmatrix}7&0&0&0\\2&6&3&0\\0&2&0&3\\0&0&2&6\end{bmatrix}\) | M1, A2 ft 1 ft 0 | |
| Assignment \(A-2,\ B-4,\ C-3,\ D-1\) then \(A-3,\ B-4,\ C-1,\ D-2\) | M1 A1 ft | (2 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Notes |
| £1 160 000 | B2, 1, 0 | (2 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Notes |
| Gives other solution | M1 A1 ft | (2 marks) |
# Question 7:
## Part (a)
| Answer/Working | Marks | Notes |
|---|---|---|
| To maximise, subtract all entries from $n \geq 30$ | M1 | |
| Reduced matrix e.g. $\begin{bmatrix}4&0&0&0\\0&7&4&1\\0&5&3&6\\0&3&5&9\end{bmatrix}$ | | |
| Minimum uncovered element is 1, giving $\begin{bmatrix}5&0&0&0\\0&6&3&0\\0&4&2&5\\0&2&4&8\end{bmatrix}$ | M1 A2 ft 1 ft 0 | |
| Further reductions with min. el $= 2$: $\begin{bmatrix}7&0&0&2\\0&4&1&0\\0&2&0&5\\0&0&2&8\end{bmatrix}$ then $\begin{bmatrix}7&0&0&0\\2&6&3&0\\0&2&0&3\\0&0&2&6\end{bmatrix}$ | M1, A2 ft 1 ft 0 | |
| Assignment $A-2,\ B-4,\ C-3,\ D-1$ then $A-3,\ B-4,\ C-1,\ D-2$ | M1 A1 ft | (2 marks) |
## Part (b)
| Answer/Working | Marks | Notes |
|---|---|---|
| £1 160 000 | B2, 1, 0 | (2 marks) |
## Part (c)
| Answer/Working | Marks | Notes |
|---|---|---|
| Gives other solution | M1 A1 ft | (2 marks) |
**Total: 15 marks**
---7. Four salespersons $A , B , C$ and $D$ are to be sent to visit four companies 1,2,3 and 4. Each salesperson will visit exactly one company, and all companies will be visited.\\
Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in $\pounds 10000$ s) are shown in the table below.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & 1 & 2 & 3 & 4 \\
\hline
Ann & 26 & 30 & 30 & 30 \\
\hline
Brenda & 30 & 23 & 26 & 29 \\
\hline
Connor & 30 & 25 & 27 & 24 \\
\hline
Dave & 30 & 27 & 25 & 21 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
\item State the value of the maximum sales.
\item Show that there is a second allocation that maximises the sales.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q7 [15]}}