| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 14 |
| 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 with a small 4×4 matrix. The method is algorithmic and procedural once learned, requiring row reduction, column reduction, and covering zeros. Part (b) adds slight complexity by asking for all optimal solutions, but the question is otherwise routine for D2 students who have practiced this technique. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| \(A\) | \(B\) | \(C\) | \(D\) | |
| Joe | 48 | 49 | 42 | 42 |
| Min-Seong | 53 | 49 | 51 | 50 |
| Olivia | 51 | 53 | 48 | 48 |
| Robert | 47 | 50 | 46 | 43 |
| Answer | Marks | Guidance |
|---|---|---|
| Minimum element 1 | M1A1, M1A1ft, M1, A1ft | 2, 2, |
| (b) | M1A1ft | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| M1A1 | 2 | |
| Joe | A | A |
| Min-Seong | C | D |
| Olivia | D | B |
| Robert | B | C |
| Value £197 000 | [14] |
**(a)** Since maximising, subtract all elements from some $n \geq 53$
$$\begin{bmatrix} 5 & 4 & 11 & 11 \\ 0 & 4 & 2 & 3 \\ 2 & 0 & 5 & 5 \\ 6 & 3 & 7 & 10 \end{bmatrix}$$
Reduce rows then columns:
$$\begin{bmatrix} 1 & 0 & 7 & 7 \\ 0 & 4 & 2 & 3 \\ 2 & 0 & 5 & 5 \\ 3 & 0 & 4 & 7 \end{bmatrix} \quad \text{then} \quad \begin{bmatrix} 1 & 0 & 5 & 4 \\ 0 & 4 & 0 & 0 \\ 2 & 0 & 3 & 2 \\ 3 & 0 & 2 & 4 \end{bmatrix}$$
Minimum element 1 | M1A1, M1A1ft, M1, A1ft | 2, 2, |
**(b)** | M1A1ft | 2 |
$$\begin{bmatrix} 0 & 1 & 4 & 3 \\ 0 & 6 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 2 \end{bmatrix} \quad \begin{bmatrix} 0 & 0 & 3 & 2 \\ 1 & 6 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 2 & 0 & 0 & 2 \end{bmatrix}$$
| M1A1 | 2 |
| Joe | A | A |
|---|---|---|
| Min-Seong | C | D |
| Olivia | D | B |
| Robert | B | C |
Value £197 000 | [14] |6. Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, $A , B , C$ and $D$. Each salesperson must attend just one fair and each fair must be attended by just one salesperson. The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown in the table below.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | }
\hline
& $A$ & $B$ & $C$ & $D$ \\
\hline
Joe & 48 & 49 & 42 & 42 \\
\hline
Min-Seong & 53 & 49 & 51 & 50 \\
\hline
Olivia & 51 & 53 & 48 & 48 \\
\hline
Robert & 47 & 50 & 46 & 43 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the total expected sales from the four salespersons. You must make your method clear and show the table after each stage.
\item State all possible optimal allocations and the optimal total value.\\
(4)(Total 14 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2008 Q6 [14]}}