| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with restrictions |
| Difficulty | Moderate -0.3 This is a standard Hungarian algorithm application with one simple restriction (Jess cannot do task 4). The algorithm is mechanical and well-practiced in D2, requiring row/column reduction and covering zeros. The restriction is trivial to handle (treating as impossible). While multi-step, it's a routine textbook exercise with no problem-solving insight needed, making it slightly easier than average. |
| Spec | 7.07a Simplex tableau: initial setup in standard format |
| 1 | 2 | 3 | 4 | |
| Harry | 18 | 24 | 22 | 17 |
| Jess | 20 | 25 | 19 | - |
| Louis | 25 | 24 | 27 | 22 |
| Saul | 19 | 26 | 23 | 14 |
| Answer | Marks |
|---|---|
| Subtracting from some \(n \geq 27\), condone up to two errors | M1 |
| Dealing with (Jess, 4) entry | M1 |
| Reducing rows then columns | M1 |
| cao (pick up (J,4) value here) | A1 |
| Double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 2 lines needed to 3 lines needed | M1 |
| ft correct – no errors | A1ft |
| Double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 3 line to 4 line solution | M1 |
| correct – no errors | A1 |
| Answer | Marks |
|---|---|
| Row reduction shown | M1 |
| \[\begin{bmatrix}1&7&5&0\\1&6&0&41\\3&2&5&0\\5&12&9&0\end{bmatrix}\] |
| Answer | Marks | Guidance |
|---|---|---|
| \[\begin{bmatrix}0^*&5&5&0\\0&4&0^*&41\\2&0^*&5&0\\4&10&9&0^*\end{bmatrix}\] | M1, A1 | |
| Solution: Harry \(-1\), Jess \(-3\), Louis \(-2\), Saul \(-4\) | M1 | |
| Total £75 | A1 | Maximum 5 marks |
| Answer | Marks |
|---|---|
| A complete, correct solution | M1 |
| cao | A1 |
# Question 2:
## Part (a)
Subtracting from some $n \geq 27$, condone up to two errors | M1 |
Dealing with (Jess, 4) entry | M1 |
Reducing rows then columns | M1 |
cao (pick up (J,4) value here) | A1 |
Double covered $+e$; one uncovered $-e$; one single covered unchanged. 2 lines needed to 3 lines needed | M1 |
ft correct – no errors | A1ft |
Double covered $+e$; one uncovered $-e$; one single covered unchanged. 3 line to 4 line solution | M1 |
correct – no errors | A1 |
## Part (a) Special case (Minimises):
Row reduction shown | M1 |
$$\begin{bmatrix}1&7&5&0\\1&6&0&41\\3&2&5&0\\5&12&9&0\end{bmatrix}$$ | |
Column reductions giving:
$$\begin{bmatrix}0^*&5&5&0\\0&4&0^*&41\\2&0^*&5&0\\4&10&9&0^*\end{bmatrix}$$ | M1, A1 |
Solution: Harry $-1$, Jess $-3$, Louis $-2$, Saul $-4$ | M1 |
Total £75 | A1 | **Maximum 5 marks**
## Part (b)
A complete, correct solution | M1 |
cao | A1 |
---2. A team of four workers, Harry, Jess, Louis and Saul, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to one task and each task must be done by just one worker.
Jess cannot be assigned to task 4.\\
The amount, in pounds, that each person would earn while assigned to each task is shown in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
Harry & 18 & 24 & 22 & 17 \\
\hline
Jess & 20 & 25 & 19 & - \\
\hline
Louis & 25 & 24 & 27 & 22 \\
\hline
Saul & 19 & 26 & 23 & 14 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total amount earned by the team. You must make your method clear and show the table after each stage.
\item State who should be assigned to each task and the total amount earned by the team.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2010 Q2 [10]}}