| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for minimisation |
| Difficulty | Moderate -0.3 This is a standard Hungarian algorithm application with straightforward row/column reduction and augmentation. Part (iii) adds mild complexity by requiring identification of alternative optimal solutions after a cost change, but the mechanics remain routine for D2 students who have practiced this algorithm. The question is slightly easier than average A-level due to its algorithmic nature requiring minimal problem-solving insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Plastering | Rewiring | Shelving | Tiling | Upholstery | |
| Gill | 25 | 50 | 34 | 40 | 25 |
| Harry | 36 | 42 | 48 | 44 | 45 |
| Ivy | 27 | 50 | 45 | 42 | 26 |
| James | 40 | 46 | 28 | 45 | 50 |
| Kelly | 34 | 48 | 34 | 50 | 40 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Row reduction (subtract row minima: 25,36,26,28,34): | M1 | Correct row reduction |
| Reduced rows: \(\begin{pmatrix}0&25&9&15&0\\0&6&12&8&9\\1&24&19&16&0\\12&18&0&17&22\\0&14&0&16&6\end{pmatrix}\) | A1 | |
| Column reduction (subtract column minima 0,6,0,8,0): | M1 | Correct column reduction |
| Final reduced matrix with zeros covered by minimum lines | A1 | 4 lines needed — augmentation required |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Augmentation step: find minimum uncovered element, subtract from uncovered, add to doubly covered | M1 | Correct augmentation |
| Optimal allocation found | A1 | |
| Gill–Plastering, Harry–Rewiring, Ivy–Upholstery, James–Shelving, Kelly–Tiling (or equivalent optimal) | A1 | |
| Total cost \(= 25+42+26+28+50 = 171\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Grid showing positions of 0s and 1s in augmented reduced cost matrix | B1 | Correct grid |
| Three alternative allocations each costing £172, with Gill having a different job | M1 A1 A1 A1 | One mark per valid alternative allocation identified |
# Question 3:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Row reduction (subtract row minima: 25,36,26,28,34): | M1 | Correct row reduction |
| Reduced rows: $\begin{pmatrix}0&25&9&15&0\\0&6&12&8&9\\1&24&19&16&0\\12&18&0&17&22\\0&14&0&16&6\end{pmatrix}$ | A1 | |
| Column reduction (subtract column minima 0,6,0,8,0): | M1 | Correct column reduction |
| Final reduced matrix with zeros covered by minimum lines | A1 | 4 lines needed — augmentation required |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Augmentation step: find minimum uncovered element, subtract from uncovered, add to doubly covered | M1 | Correct augmentation |
| Optimal allocation found | A1 | |
| Gill–Plastering, Harry–Rewiring, Ivy–Upholstery, James–Shelving, Kelly–Tiling (or equivalent optimal) | A1 | |
| Total cost $= 25+42+26+28+50 = 171$ | A1 | |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Grid showing positions of 0s and 1s in augmented reduced cost matrix | B1 | Correct grid |
| Three alternative allocations each costing £172, with Gill having a different job | M1 A1 A1 A1 | One mark per valid alternative allocation identified |
---3 Each of five jobs is to be allocated to one of five workers, and each worker will have one job. The table shows the cost, in $\pounds$, of using each worker on each job. It is required to find the allocation for which the total cost is minimised.
Worker
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Job}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Plastering & Rewiring & Shelving & Tiling & Upholstery \\
\hline
Gill & 25 & 50 & 34 & 40 & 25 \\
\hline
Harry & 36 & 42 & 48 & 44 & 45 \\
\hline
Ivy & 27 & 50 & 45 & 42 & 26 \\
\hline
James & 40 & 46 & 28 & 45 & 50 \\
\hline
Kelly & 34 & 48 & 34 & 50 & 40 \\
\hline
\end{tabular}
\end{center}
\end{table}
(i) Construct a reduced cost matrix by first reducing rows and then reducing columns. Cross through the 0's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [Try to ensure that the values in your table can still be read.]\\
(ii) Augment your reduced cost matrix and hence find a minimum cost allocation. Write a list showing which job should be given to which worker for your minimum cost allocation, and calculate the total cost in this case.
Gill decides that she does not like the job she has been allocated and increases her cost for this job by $\pounds 100$. New minimum cost allocations can be found, each allocation costing just $\pounds 1$ more than the minimum cost allocation found in part (ii).\\
(iii) Use the grid in your answer book to show the positions of the 0 's and 1 's in the augmented reduced cost matrix from part (ii). Hence find three allocations, each costing just $\pounds 1$ more than the minimum cost allocation found in part (ii) and with Gill having a different job to the one allocated in part (ii). [5]
\hfill \mbox{\textit{OCR D2 2014 Q3 [13]}}