| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 12 |
| 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 question requiring systematic application of a learned procedure (row/column reduction, line covering, augmentation) with clear steps. While it involves multiple parts and careful arithmetic, it requires no novel insight or problem-solving—just methodical execution of the algorithm taught in D2. The procedure is more mechanical than conceptually demanding, making it slightly easier than average A-level maths questions. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | |
| Task \(\boldsymbol { V }\) | 100 | 110 | 112 | 102 | 95 |
| Task \(\boldsymbol { W }\) | 125 | 130 | 110 | 120 | 115 |
| Task \(\boldsymbol { X }\) | 105 | 110 | 101 | 108 | 120 |
| Task \(\boldsymbol { Y }\) | 115 | 115 | 120 | 135 | 110 |
| Task \(\boldsymbol { Z }\) | 100 | 98 | 99 | 100 | 102 |
| 0 | 12 | 13 | 2 | 0 |
| 14 | 21 | 0 | \(k\) | 9 |
| 3 | 10 | 0 | 6 | 23 |
| 0 | 2 | 6 | 20 | 0 |
| 0 | 0 | 0 | 0 | 7 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Column reduction shown correctly | M1 | Subtract column minima |
| Row reduction applied after column reduction | M1 | Subtract row minima |
| Correct table obtained and \(k = 5\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Zeros covered by 4 lines correctly shown | M1 | |
| First augmentation correct | M1 | |
| Second augmentation correct | M1 | |
| Table requiring 5 lines shown | A1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Valid allocation(s) identified from final table | M1 | |
| All possible optimal allocations stated | A1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Minimum total time stated correctly | B1 |
# Question 3:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Column reduction shown correctly | M1 | Subtract column minima |
| Row reduction applied after column reduction | M1 | Subtract row minima |
| Correct table obtained and $k = 5$ | A1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Zeros covered by 4 lines correctly shown | M1 | |
| First augmentation correct | M1 | |
| Second augmentation correct | M1 | |
| Table requiring 5 lines shown | A1 A1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Valid allocation(s) identified from final table | M1 | |
| All possible optimal allocations stated | A1 A1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Minimum total time stated correctly | B1 | |3 The table shows the times taken, in minutes, by five people, $A , B , C , D$ and $E$, to carry out the tasks $V , W , X , Y$ and $Z$.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { E }$ \\
\hline
Task $\boldsymbol { V }$ & 100 & 110 & 112 & 102 & 95 \\
\hline
Task $\boldsymbol { W }$ & 125 & 130 & 110 & 120 & 115 \\
\hline
Task $\boldsymbol { X }$ & 105 & 110 & 101 & 108 & 120 \\
\hline
Task $\boldsymbol { Y }$ & 115 & 115 & 120 & 135 & 110 \\
\hline
Task $\boldsymbol { Z }$ & 100 & 98 & 99 & 100 & 102 \\
\hline
\end{tabular}
\end{center}
Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.
\begin{enumerate}[label=(\alph*)]
\item By reducing the columns first, and then the rows, show that the new table of values is
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
0 & 12 & 13 & 2 & 0 \\
\hline
14 & 21 & 0 & $k$ & 9 \\
\hline
3 & 10 & 0 & 6 & 23 \\
\hline
0 & 2 & 6 & 20 & 0 \\
\hline
0 & 0 & 0 & 0 & 7 \\
\hline
\end{tabular}
\end{center}
and state the value of the constant $k$.
\item Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
\item Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
\item Find the minimum total time.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2013 Q3 [12]}}