| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2018 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with parameters |
| Difficulty | Standard +0.3 This is a standard Hungarian algorithm application with a straightforward parameter-finding extension. Part (a) is routine algorithmic execution (8 marks of mechanical steps), part (b) is trivial reading from the solution, and part (c) requires simple algebraic reasoning about cost differences after a swap. The parameter x > 38 guides students to the answer. This is slightly easier than average as it's mostly procedural with minimal problem-solving insight required. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| 1 | 2 | 3 | 4 | 5 | |
| A | 25 | 31 | 27 | 29 | 35 |
| B | 29 | 33 | 40 | 35 | 37 |
| C | 28 | 29 | 35 | 36 | 37 |
| D | 34 | 35 | 36 | \(x\) | 41 |
| E | 36 | 35 | 32 | 31 | 33 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Row reduction (subtract row minimum from each row) | M1 | |
| Correct reduced matrix after row reduction | A1 | |
| Column reduction applied | M1 | |
| Correct matrix after column reduction | A1 | |
| Minimum lines to cover zeros found; augmentation step performed if needed | M1M1 | |
| Correct augmented matrix | A1 | |
| Optimal allocation identified: e.g. A→3, B→5, C→2, D→4, E→1 (or similar valid allocation) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Minimum cost \(= 27 + 37 + 29 + x + 36 =\) computed correctly using optimal allocation | B1ft | Follow through from (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| When A and D swap: new cost uses D's original task cost and A's original task cost | M1 | |
| New total \(=\) minimum cost \(+ 5\); set up equation in \(x\) and solve to give \(x = 40\) | A1 | Must show working |
# Question 3:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Row reduction (subtract row minimum from each row) | M1 | |
| Correct reduced matrix after row reduction | A1 | |
| Column reduction applied | M1 | |
| Correct matrix after column reduction | A1 | |
| Minimum lines to cover zeros found; augmentation step performed if needed | M1M1 | |
| Correct augmented matrix | A1 | |
| Optimal allocation identified: e.g. A→3, B→5, C→2, D→4, E→1 (or similar valid allocation) | A1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Minimum cost $= 27 + 37 + 29 + x + 36 =$ computed correctly using optimal allocation | B1ft | Follow through from (a) |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| When A and D swap: new cost uses D's original task cost and A's original task cost | M1 | |
| New total $=$ minimum cost $+ 5$; set up equation in $x$ and solve to give $x = 40$ | A1 | Must show working |
---3. Five workers, A, B, C, D and E, are to be assigned to five tasks, 1, 2, 3, 4 and 5 . Each worker must be assigned to only one task and each task must be done by only one worker.
The cost, in pounds, of assigning each worker to each task is shown in the table below. The cost of assigning worker D to task 4 is $\pounds x$, where $x > 38$
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & 25 & 31 & 27 & 29 & 35 \\
\hline
B & 29 & 33 & 40 & 35 & 37 \\
\hline
C & 28 & 29 & 35 & 36 & 37 \\
\hline
D & 34 & 35 & 36 & $x$ & 41 \\
\hline
E & 36 & 35 & 32 & 31 & 33 \\
\hline
\end{tabular}
\end{center}
The total cost is to be minimised.
\begin{enumerate}[label=(\alph*)]
\item Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.\\
(8)
\item Find the minimum total cost.\\
(1)
Workers A and D decide that they do not like the task they have been allocated and are allowed to swap tasks with each other. The other three allocations are unchanged. The cost now of allocating the five workers to the five tasks is now $\pounds 5$ more than the minimum cost found in (b).
\item Calculate the value of $x$. You must show your working.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2018 Q3 [11]}}