| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | June |
| Marks | 9 |
| 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 taught procedure (row/column reduction, line covering, augmentation). While it has multiple parts and requires careful arithmetic, it involves no novel problem-solving or insight—students follow the algorithm mechanically. The modification question in part (e) is routine recall. Slightly easier than average due to its procedural nature. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | |
| Puzzle 1 | 16 | 13 | 15 | 16 | 15 |
| Puzzle 2 | 14 | 16 | 16 | 14 | 18 |
| Puzzle 3 | 14 | 12 | 18 | 13 | 16 |
| Puzzle 4 | 15 | 15 | 17 | 12 | 14 |
| Puzzle 5 | 13 | 17 | 16 | 14 | 15 |
| 3 | 1 | 0 | 4 | 1 |
| 0 | \(k\) | 0 | 1 | 3 |
| 1 | 0 | 3 | 1 | 2 |
| 2 | 3 | 2 | 0 | 0 |
| 0 | 5 | 1 | 2 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Column reduction then row reduction shown correctly | M1 | Method for reducing columns first |
| \(k = 4\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| One horizontal line and three vertical lines covering all zeros shown | B1 | Must show the four lines clearly |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct augmented table produced (subtract smallest uncovered element, add to doubly covered elements) | M1 | Correct method of augmentation |
| Correct table requiring 5 lines to cover zeros | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| All possible optimal allocations stated | M1 A1 A1 | M1 for systematic approach; A1 for each correct allocation up to 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Minimum total time stated correctly | B1 | Must be consistent with allocations in (c) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Subtract all values from the largest value in the table (or replace each entry \(x\) with \(M-x\) where \(M\) is the maximum value) | B1 |
# Question 2:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Column reduction then row reduction shown correctly | M1 | Method for reducing columns first |
| $k = 4$ | A1 | |
## Part (b)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| One horizontal line and three vertical lines covering all zeros shown | B1 | Must show the four lines clearly |
## Part (b)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct augmented table produced (subtract smallest uncovered element, add to doubly covered elements) | M1 | Correct method of augmentation |
| Correct table requiring 5 lines to cover zeros | A1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| All possible optimal allocations stated | M1 A1 A1 | M1 for systematic approach; A1 for each correct allocation up to 2 |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Minimum total time stated correctly | B1 | Must be consistent with allocations in (c) |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Subtract all values from the largest value in the table (or replace each entry $x$ with $M-x$ where $M$ is the maximum value) | B1 | |2 The times taken, in minutes, for five people, $A , B , C , D$ and $E$, to complete each of five different puzzles are recorded in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { E }$ \\
\hline
Puzzle 1 & 16 & 13 & 15 & 16 & 15 \\
\hline
Puzzle 2 & 14 & 16 & 16 & 14 & 18 \\
\hline
Puzzle 3 & 14 & 12 & 18 & 13 & 16 \\
\hline
Puzzle 4 & 15 & 15 & 17 & 12 & 14 \\
\hline
Puzzle 5 & 13 & 17 & 16 & 14 & 15 \\
\hline
\end{tabular}
\end{center}
Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.
\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
3 & 1 & 0 & 4 & 1 \\
\hline
0 & $k$ & 0 & 1 & 3 \\
\hline
1 & 0 & 3 & 1 & 2 \\
\hline
2 & 3 & 2 & 0 & 0 \\
\hline
0 & 5 & 1 & 2 & 1 \\
\hline
\end{tabular}
\end{center}
State the value of the constant $k$.
\item \begin{enumerate}[label=(\roman*)]
\item Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
\item Use augmentation to produce a table where five lines are required to cover the zeros.
\end{enumerate}\item Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
\item Find the minimum total time for completing the five puzzles.
\item Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2011 Q2 [9]}}