| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm for maximisation with a 4×4 matrix. The method is algorithmic and procedural—students follow prescribed steps (reduce rows, reduce columns, cover zeros, adjust if needed). No problem-solving insight or novel thinking is required, just careful execution of a learned algorithm. Easier than average A-level questions. |
| 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 |
| 1 | 2 | 3 | 4 | |
| Chris | 127 | 116 | 111 | 113 |
| James | 225 | 208 | 205 | 208 |
| Katie | 130 | 113 | 112 | 114 |
| Nicky | 228 | 212 | 203 | 210 |
| Answer | Marks | Guidance |
|---|---|---|
| Part (a) | ||
| Subtracting all elements from some \(n \geq 228\) | 1M1 | |
| Reducing rows and then columns to get \(\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 6 & 4 & 3 \\ 0 & 6 & 2 & 2 \\ 0 & 5 & 9 & 4 \end{pmatrix}\) | 2M1 | a2M1: Reducing rows and then columns |
| 1A1 | ||
| Using two lines and 2 to get \(\begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 4 & 2 & 1 \\ 0 & 4 & 0 & 0 \\ 0 & 3 & 7 & 2 \end{pmatrix}\) | 3M1 | |
| 2A1 | ||
| Using three lines and 1 to get \(\begin{pmatrix} 3 & 0^* & 0 & 0 \\ 0 & 3 & 1 & 0^* \\ 1 & 4 & 0^* & 0 \\ 0^* & 2 & 6 & 1 \end{pmatrix}\) | 4M1 | |
| 3A1ft, 4A1 | a3A1ft: on their previous table; a4A1: CSO on final table | |
| Part (b) | ||
| \(C = 2, J = 4, K = 3, N = 1\) | M1 | |
| Maximum profit of £664 | A1 | |
| (2) | ||
| Note 'minimise' gives this special case: \(\begin{pmatrix} 0 & 4 & 0 & 0 \\ 4 & 2 & 0 & 1 \\ 2 & 0 & 0 & 0 \\ 9 & 8 & 0 & 4 \end{pmatrix}\) then \(\begin{pmatrix} 0^* & 4 & 1 & 0 \\ 3 & 1 & 0 & 0^* \\ 2 & 0^* & 1 & 0 \\ 8 & 7 & 0^* & 3 \end{pmatrix}\) then \(C = 1, J = 4, K = 2, N = 3\); Profit £651 | ||
| Gives 5 max: (a) 1M0 2M1 1A1 3M0 2A0 4M1 3A1ft 4A0 (b) M1A0 | b1M1: Their optimal allocation (of workers to tasks) and an attempt to calculate the profit – this mark is dependent on all M marks in (a) have been earned. b1A1: CAO |
| **Part (a)** | | |
|---|---|---|
| Subtracting all elements from some $n \geq 228$ | 1M1 | |
| Reducing rows and then columns to get $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 6 & 4 & 3 \\ 0 & 6 & 2 & 2 \\ 0 & 5 & 9 & 4 \end{pmatrix}$ | 2M1 | a2M1: Reducing rows **and then** columns |
| | 1A1 | |
| Using two lines and 2 to get $\begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 4 & 2 & 1 \\ 0 & 4 & 0 & 0 \\ 0 & 3 & 7 & 2 \end{pmatrix}$ | 3M1 | |
| | 2A1 | |
| Using three lines and 1 to get $\begin{pmatrix} 3 & 0^* & 0 & 0 \\ 0 & 3 & 1 & 0^* \\ 1 & 4 & 0^* & 0 \\ 0^* & 2 & 6 & 1 \end{pmatrix}$ | 4M1 | |
| | 3A1ft, 4A1 | a3A1ft: on their previous table; a4A1: CSO on final table |
| **Part (b)** | | |
| $C = 2, J = 4, K = 3, N = 1$ | M1 | |
| Maximum profit of £664 | A1 | |
| | **(2)** | |
| Note 'minimise' gives this special case: $\begin{pmatrix} 0 & 4 & 0 & 0 \\ 4 & 2 & 0 & 1 \\ 2 & 0 & 0 & 0 \\ 9 & 8 & 0 & 4 \end{pmatrix}$ then $\begin{pmatrix} 0^* & 4 & 1 & 0 \\ 3 & 1 & 0 & 0^* \\ 2 & 0^* & 1 & 0 \\ 8 & 7 & 0^* & 3 \end{pmatrix}$ then $C = 1, J = 4, K = 2, N = 3$; Profit £651 | | |
| Gives 5 max: (a) 1M0 2M1 1A1 3M0 2A0 4M1 3A1ft 4A0 (b) M1A0 | | b1M1: Their optimal allocation (of workers to tasks) and an attempt to calculate the profit – this mark is dependent on all M marks in (a) have been earned. b1A1: CAO |
---\begin{enumerate}
\item Four workers, Chris (C), James (J), Katie (K) and Nicky (N), are to be allocated to four tasks, 1, 2, 3 and 4. Each worker is to be allocated to one task and each task must be allocated to one worker.
\end{enumerate}
The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
Chris & 127 & 116 & 111 & 113 \\
\hline
James & 225 & 208 & 205 & 208 \\
\hline
Katie & 130 & 113 & 112 & 114 \\
\hline
Nicky & 228 & 212 & 203 & 210 \\
\hline
\end{tabular}
\end{center}
(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.\\
(b) State which worker should be allocated to each task and the resulting total profit made.\\
\hfill \mbox{\textit{Edexcel D2 2013 Q1 [10]}}