| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with restrictions |
| Difficulty | Standard +0.3 This is a standard Hungarian algorithm application with a straightforward constraint (one forbidden assignment). The method is algorithmic and well-practiced in D2, requiring careful bookkeeping but no problem-solving insight. Part (b) tests basic understanding of uniqueness. Slightly easier than average due to the mechanical nature of the algorithm. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Cost | \(H\) | \(P\) | \(R\) | \(W\) |
| \(A\) | 3 | 5 | 11 | 9 |
| \(B\) | 3 | 7 | 8 | -- |
| \(C\) | 2 | 5 | 10 | 7 |
| \(D\) | 8 | 3 | 7 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| H | P | R |
| A | 3 | 5 |
| B | 3 | 7 |
| C | 2 | 5 |
| D | 8 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| A | – | H |
| B | – | R or R |
| C | – | W |
| D | – | P |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Not unique – gives the other solution | M1 A1ft | 2 |
## Part (a)
**Answer:** Adding $n \geq 20$ to table to give:
| | H | P | R | W |
|---|---|---|---|---|
| A | 3 | 5 | 11 | 9 |
| B | 3 | 7 | 8 | N |
| C | 2 | 5 | 10 | 7 |
| D | 8 | 3 | 7 | 6 |
Reducing rows first then columns
Either: $\begin{bmatrix} 0 & 1 & 3 & 2 \\ -0 & -3 & -0 & n-7 & \cdots \\ 0 & 2 & 3 & 1 \\ -6 & -0 & -0 & 0 & \cdots \end{bmatrix}$ or $\begin{bmatrix} 0 & 1 & 3 & 2 \\ 0 & 3 & 0 & n-7 \\ 0 & 2 & 3 & 1 \\ -6 & -0 & -0 & 0 & \cdots \end{bmatrix}$
Final tables:
$\begin{bmatrix} 0 & 0 & 2 & 1 \\ 1 & 3 & 0 & n-7 \\ 0 & 1 & 2 & 0 \\ 7 & 0 & 0 & 0 \end{bmatrix}$ or $\begin{bmatrix} 0 & 0 & 3 & 1 \\ 0 & 2 & 0 & n-8 \\ 0 & 1 & 3 & 0 \\ 7 & 0 & 1 & 0 \end{bmatrix}$
| | | | |
|---|---|---|---|
| A | – | H | P | A1 | 3
| B | – | R or R | | cost £21 000 | M1 A1ft | 4
| C | – | W | H | | A1 |
| D | – | P | W | | A1 | 2
## Part (b)
**Answer:** Not unique – gives the other solution | M1 A1ft | 2
---During the school holidays four building tasks, rebuilding a wall ($W$), repairing the roof ($R$), repainting the hall ($H$) and relaying the playground ($P$), need to be carried out at a Junior School.
Four builders, $A$, $B$, $C$ and $D$ will be hired for these tasks. Each builder must be assigned to one task. Builder $B$ is not able to rebuild the wall and therefore cannot be assigned to this task.
The cost, in thousands of pounds, of using each builder for each task is given in the table below.
\begin{tabular}{|c|c|c|c|c|}
\hline
Cost & $H$ & $P$ & $R$ & $W$ \\
\hline
$A$ & 3 & 5 & 11 & 9 \\
\hline
$B$ & 3 & 7 & 8 & -- \\
\hline
$C$ & 2 & 5 & 10 & 7 \\
\hline
$D$ & 8 & 3 & 7 & 6 \\
\hline
\end{tabular}
\begin{enumerate}[label=(\alph*)]
\item Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the total cost. State the allocation and its total cost. You must make your method clear and show the table after each stage. [9]
\item State, with a reason, whether this allocation is unique. [2]
\end{enumerate}
(Total 11 marks)
\hfill \mbox{\textit{Edexcel D2 2006 Q4 [11]}}