| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with restrictions |
| Difficulty | Moderate -0.8 This is a standard textbook application of the Hungarian algorithm with straightforward restrictions. The question explicitly tells students to reduce rows first and follow the algorithm step-by-step, requiring only mechanical execution of a learned procedure with no problem-solving insight or novel thinking required. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| 1 | 2 | 3 | 4 | |
| A | 19 | 16 | 23 | - |
| B | 24 | - | 30 | 23 |
| C | 18 | 17 | 25 | 18 |
| D | 24 | 24 | 26 | 24 |
| Answer | Marks | Guidance |
|---|---|---|
| Scheme | Marks | Guidance |
| Subtracting from some \(n \geq 30\), condone up to 2 errors. Dealing with the A4 and B2 entries. | M1 M1 | 1M1: Subtracting from some \(n \geq 30\), condone up to 2 errors. 2M1: Dealing with the A4 and B2 entries. |
| Reducing rows and then columns. | M1 A1 | 3M1: Reducing rows and then columns. 1A1: CAO |
| Follow through on their previous table - no errors | M1 A1 ft | 4M1: Double covered + e; one uncovered – e; and one single covered unchanged. 2 lines needed to 3 lines needed. 2A1ft: Follow through on their previous table - no errors |
| Follow through on their previous table - no errors | M1 A1 ft A1 | 5M1: One double covered + e; one uncovered – e; and one single covered unchanged. 3 lines needed to 4 lines needed (so getting to optimal table). 3A1ft: Follow through on their previous table - no errors. 4A1: CSO on final table. 5A1: CAO – either one – this mark is dependent on all M marks being awarded. |
| Two optimal allocations: \(\begin{array}{c | cc} & A & \\ \hline B & 3 & 4 \\ C & 4 & 3 \\ D & 2 & 2 \end{array}\) | A1 |
| 10 marks |
| Scheme | Marks | Guidance |
|--------|-------|----------|
| Subtracting from some $n \geq 30$, condone up to 2 errors. Dealing with the A4 and B2 entries. | M1 M1 | 1M1: Subtracting from some $n \geq 30$, condone up to 2 errors. 2M1: Dealing with the A4 and B2 entries. |
| Reducing rows and then columns. | M1 A1 | 3M1: Reducing rows and then columns. 1A1: CAO |
| Follow through on their previous table - no errors | M1 A1 ft | 4M1: Double covered + e; one uncovered – e; and one single covered unchanged. 2 lines needed to 3 lines needed. 2A1ft: Follow through on their previous table - no errors |
| Follow through on their previous table - no errors | M1 A1 ft A1 | 5M1: One double covered + e; one uncovered – e; and one single covered unchanged. 3 lines needed to 4 lines needed (so getting to optimal table). 3A1ft: Follow through on their previous table - no errors. 4A1: CSO on final table. 5A1: CAO – either one – this mark is dependent on all M marks being awarded. |
| Two optimal allocations: $\begin{array}{c|cc} & A & \\ \hline B & 3 & 4 \\ C & 4 & 3 \\ D & 2 & 2 \end{array}$ | A1 | |
| | **10 marks** | |
---\begin{enumerate}
\item Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.
\end{enumerate}
Worker A cannot do task 4 and worker B cannot do task 2.
The amount, in pounds, that each worker would earn if assigned to the tasks, is shown in the table below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & 19 & 16 & 23 & - \\
\hline
B & 24 & - & 30 & 23 \\
\hline
C & 18 & 17 & 25 & 18 \\
\hline
D & 24 & 24 & 26 & 24 \\
\hline
\end{tabular}
\end{center}
Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.\\
\hfill \mbox{\textit{Edexcel D2 2014 Q1 [10]}}