| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.3 This is a standard application of the Hungarian algorithm for maximisation with a 4×4 matrix. While it requires multiple systematic steps (subtract from maximum, row/column reductions, covering zeros, adjustments), the algorithm is entirely procedural with no problem-solving or insight required. The 13 marks reflect the length of working rather than conceptual difficulty. Slightly easier than average as it's pure algorithmic execution. |
| Spec | 7.03m Packing extensions: 2D/3D packing and knapsack problems |
| \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 | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Subtract all values from maximum (55): reduce to minimisation | M1 | |
| Reduced matrix obtained | A1 | |
| Row reduction | M1 | |
| Column reduction | A1 | |
| Cover zeros; augment as needed | M1 A1 | |
| Repeat until optimal assignment found | M1 | |
| Optimal assignment: \(R_1 \to A_3\), \(R_2 \to A_1\), \(R_3 \to A_4\), \(R_4 \to A_3\)... | M1 A1 | |
| Final allocation: \(R_1\to A_3(44)\), \(R_2\to A_1(45)\), \(R_3\to A_4(50)\), \(R_4\to A_2\)... | A1 A1 A1 | One mark per correct assignment shown at each stage |
| Maximum profit \(= 44+45+50+43 = £1820\) (or appropriate sum) | A1 |
# Question 6:
| Answer | Marks | Guidance |
|--------|-------|----------|
| Subtract all values from maximum (55): reduce to minimisation | M1 | |
| Reduced matrix obtained | A1 | |
| Row reduction | M1 | |
| Column reduction | A1 | |
| Cover zeros; augment as needed | M1 A1 | |
| Repeat until optimal assignment found | M1 | |
| Optimal assignment: $R_1 \to A_3$, $R_2 \to A_1$, $R_3 \to A_4$, $R_4 \to A_3$... | M1 A1 | |
| Final allocation: $R_1\to A_3(44)$, $R_2\to A_1(45)$, $R_3\to A_4(50)$, $R_4\to A_2$... | A1 A1 A1 | One mark per correct assignment shown at each stage |
| Maximum profit $= 44+45+50+43 = £1820$ (or appropriate sum) | A1 | |
---6. 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.
\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.\\
(13 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q6 [13]}}