| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.3 This is a standard textbook application of the Hungarian algorithm for maximisation. While it requires multiple systematic steps (subtracting from maximum, row/column reductions, covering zeros, adjustments), the procedure is entirely algorithmic with no problem-solving insight needed. The 4×4 size keeps it manageable. Slightly easier than average due to its purely mechanical nature. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | \(A _ { 1 }\) | \(A _ { 2 }\) | \(A _ { 3 }\) | \(A _ { 4 }\) |
| \(R _ { 1 }\) | 37 | 29 | 44 | 51 |
| \(R _ { 2 }\) | 45 | 30 | 43 | 41 |
| \(R _ { 3 }\) | 32 | 27 | 39 | 50 |
| \(R _ { 4 }\) | 43 | 25 | 51 | 55 |
| Answer | Marks |
|---|---|
| Part 1: need to maximise so subtract all values from 55 giving row min. | M1 |
| Answer | Marks |
|---|---|
| 18 26 11 4 | 4 |
| 10 25 12 14 | 10 |
| 23 28 16 5 | 5 |
| 12 30 4 0 | 0 |
| Answer | Marks |
|---|---|
| M1 A1 |
| Answer | Marks |
|---|---|
| A1 |
| Answer | Marks |
|---|---|
| M1 A1 | (N.B. a different choice of lines will lead to the same final assignment) |
| Answer | Marks |
|---|---|
| A1 |
| Answer | Marks |
|---|---|
| A1 | (10) |
**Part 1:** need to maximise so subtract all values from 55 giving row min. | M1 |
```
18 26 11 4 | 4
10 25 12 14 | 10
23 28 16 5 | 5
12 30 4 0 | 0
```
reducing rows gives:
```
14 22 7 0
0 15 2 4
18 23 11 0
12 30 4 0
```
| M1 A1 |
col min. 0 15 2 0
reducing columns gives:
```
14 7 5 0
0 0 0 -4
18 8 9 0
12 15 2 0
```
| A1 |
2 lines required to cover all zeros, apply algorithm
```
12 5 3 0
0 0 0 6
16 6 7 0
10 13 0 0
```
| M1 A1 | (N.B. a different choice of lines will lead to the same final assignment) |
3 lines required to cover all zeros, apply algorithm
```
7 0 3 0
0 0 5 11
11 1 7 0
5 8 0 0
```
| A1 |
4 lines required to cover all zeros so allocation is possible
- $R_1$ goes to $A_2$
- $R_2$ goes to $A_1$
- $R_3$ goes to $A_4$
- $R_4$ goes to $A_3$
| A1 | **(10)** |
---\begin{enumerate}
\item Four sales representatives ( $R _ { 1 } , R _ { 2 } , R _ { 3 }$ and $R _ { 4 }$ ) are to be sent to four areas ( $A _ { 1 } , A _ { 2 } , A _ { 3 }$ and $A _ { 4 }$ ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below.
\end{enumerate}
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & $A _ { 1 }$ & $A _ { 2 }$ & $A _ { 3 }$ & $A _ { 4 }$ \\
\hline
$R _ { 1 }$ & 37 & 29 & 44 & 51 \\
\hline
$R _ { 2 }$ & 45 & 30 & 43 & 41 \\
\hline
$R _ { 3 }$ & 32 & 27 & 39 & 50 \\
\hline
$R _ { 4 }$ & 43 & 25 & 51 & 55 \\
\hline
\end{tabular}
\end{center}
Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.\\
\hfill \mbox{\textit{OCR D2 Q3 [10]}}