| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Moderate -0.8 This is a standard textbook application of the Hungarian algorithm with a straightforward dummy row addition. The algorithm is mechanical once learned, requiring only systematic row/column reduction and covering zeros—no problem-solving insight or novel reasoning needed. The unequal sets aspect is explicitly prompted in part (a), making it easier than discovering this independently. |
| Spec | 7.07a Simplex tableau: initial setup in standard format |
| \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | |
| Jess | 15 | 11 | 14 | 12 |
| Matt | 13 | 8 | 17 | 13 |
| Rachel | 14 | 9 | 13 | 15 |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | There are more tasks than people. | B1 (1) |
| (b) | Adds a row of zeros | B1 (1) |
| (c) | Either \(\begin{bmatrix} 3 & 3 & 2 & 0 \\ 1 & 0 & 5 & 1 \\ 1 & 0 & 0 & 2 \\ 0 & 4 & 0 & 0 \end{bmatrix}\) or \(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 6 & 4 \\ 2 & 0 & 1 & 5 \\ 0 & 3 & 0 & 2 \end{bmatrix} \to \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 5 & 3 \\ 1 & 0 & 0 & 4 \\ 0 & 4 & 0 & 2 \end{bmatrix}\) | B1;M1A1 |
| (d) | \(J - 4, M - 2, R - 3, (D - 1)\) | A1 (6) |
| Minimum cost is (£)33. | B1 (1) |
(a) | There are more tasks than people. | B1 (1) | Generous, on the right lines bod gets B1 |
(b) | Adds a row of zeros | B1 (1) | |
(c) | Either $\begin{bmatrix} 3 & 3 & 2 & 0 \\ 1 & 0 & 5 & 1 \\ 1 & 0 & 0 & 2 \\ 0 & 4 & 0 & 0 \end{bmatrix}$ or $\begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 6 & 4 \\ 2 & 0 & 1 & 5 \\ 0 & 3 & 0 & 2 \end{bmatrix} \to \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 5 & 3 \\ 1 & 0 & 0 & 4 \\ 0 & 4 & 0 & 2 \end{bmatrix}$ | B1;M1A1 | Nearest Neighbour each vertex visited once (condone lack of return to start); Correct route cao – must return to start. |
(d) | $J - 4, M - 2, R - 3, (D - 1)$ | A1 (6) | |
| Minimum cost is (£)33. | B1 (1) | |
**Total [9]**
---\begin{enumerate}
\item A company, Kleenitquick, has developed a new stain remover. To promote sales, three salespersons, Jess, Matt and Rachel, will be assigned to three of four department stores $1,2,3$ and 4 , to demonstrate the stain remover. Each salesperson can only be assigned to one department store.
\end{enumerate}
The table below shows the cost, in pounds, of assigning each salesperson to each department store.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | }
\hline
& $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ \\
\hline
Jess & 15 & 11 & 14 & 12 \\
\hline
Matt & 13 & 8 & 17 & 13 \\
\hline
Rachel & 14 & 9 & 13 & 15 \\
\hline
\end{tabular}
\end{center}
(a) Explain why a dummy row needs to be added to the table.\\
(b) Complete Table 1 in the answer book.\\
(c) Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost of assigning salespersons to department stores. You must make your method clear and show the table after each iteration.\\
(d) Find the minimum cost.\\
\hfill \mbox{\textit{Edexcel D2 2009 Q1 [9]}}