| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2005 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.3 This is a straightforward application of the Hungarian algorithm for maximisation with a small 4×4 matrix. The method is algorithmic and routine once learned, requiring row/column operations and covering lines. Part (c) adds minor complexity by asking for an alternative optimal solution, but this emerges naturally from the algorithm. Easier than average A-level due to its procedural nature with no novel problem-solving required. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | 1 | 2 | 3 | 4 |
| Ann | 26 | 30 | 30 | 30 |
| Brenda | 30 | 23 | 26 | 29 |
| Connor | 30 | 25 | 27 | 24 |
| Dave | 30 | 27 | 25 | 21 |
5. Four salesperson $A , B , C$ and $D$ are to be sent to visit four companies $1,2,3$ and 4 . Each salesperson will visit exactly one company, and all companies will be visited.
Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in $\pounds 10000$ s) are shown in the table below.
\begin{center}
\begin{tabular}{ | l | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & 1 & 2 & 3 & 4 \\
\hline
Ann & 26 & 30 & 30 & 30 \\
\hline
Brenda & 30 & 23 & 26 & 29 \\
\hline
Connor & 30 & 25 & 27 & 24 \\
\hline
Dave & 30 & 27 & 25 & 21 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
\item State the value of the maximum sales.
\item Show that there is a second allocation that maximises the sales.\\
(Total 15 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2005 Q5 [15]}}