| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm for maximisation |
| Difficulty | Moderate -0.8 This is a standard textbook application of the Hungarian algorithm with clear step-by-step instructions. The question guides students through the conversion to minimisation (part a), provides the intermediate table (part b(i)), and requires only mechanical application of the algorithm. While it involves multiple steps, each is routine for D2 students who have learned this topic, requiring no problem-solving insight or novel approaches. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Field A | Field B | Field C | Field D | Field E | |
| Crop 1 | 16 | 12 | 8 | 18 | 14 |
| Crop 2 | 20 | 15 | 8 | 16 | 12 |
| Crop 3 | 9 | 10 | 12 | 17 | 12 |
| Crop 4 | 18 | 11 | 17 | 15 | 19 |
| 2 | 6 | 10 | 0 | \(p\) |
| 0 | 5 | 12 | 4 | 8 |
| 8 | 7 | 5 | 0 | \(q\) |
| 1 | 8 | 2 | 4 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Subtract each value from 20, then add extra row of zeros | B1 | Extra row of equal values (zeros) added to make \(5\times5\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Hungarian algorithm minimises | B1 | |
| Subtracting from 20 converts maximisation to minimisation | B1 | |
| Extra row needed as 5 fields but only 4 crops (need square matrix) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(p = 6\) | B1 | |
| \(q = 3\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Zeros covered by one horizontal and three vertical lines shown correctly | B1 | |
| Augmentation step performed correctly (subtract minimum uncovered, add to doubly covered) | M1 | |
| Further iteration leading to valid assignment | M1 | |
| Crop 1 \(\to\) Field D, Crop 2 \(\to\) Field A, Crop 3 \(\to\) Field C, Crop 4 \(\to\) Field E, dummy \(\to\) Field B | A1 | Allow equivalent valid optimal assignment |
| Correct verification shown | B1 | |
| Correct complete allocation stated | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(18 + 20 + 12 + 19 = 69\) | B1 ft | Follow through from their allocation |
# Question 2:
## Part (a)(i) - Modified table
| Answer | Mark | Guidance |
|--------|------|----------|
| Subtract each value from 20, then add extra row of zeros | B1 | Extra row of equal values (zeros) added to make $5\times5$ |
## Part (a)(ii) - Explanation
| Answer | Mark | Guidance |
|--------|------|----------|
| Hungarian algorithm minimises | B1 | |
| Subtracting from 20 converts maximisation to minimisation | B1 | |
| Extra row needed as 5 fields but only 4 crops (need square matrix) | B1 | |
## Part (b)(i) - Values of p and q
| Answer | Mark | Guidance |
|--------|------|----------|
| $p = 6$ | B1 | |
| $q = 3$ | B1 | |
## Part (b)(ii) - Hungarian Algorithm
| Answer | Mark | Guidance |
|--------|------|----------|
| Zeros covered by one horizontal and three vertical lines shown correctly | B1 | |
| Augmentation step performed correctly (subtract minimum uncovered, add to doubly covered) | M1 | |
| Further iteration leading to valid assignment | M1 | |
| Crop 1 $\to$ Field D, Crop 2 $\to$ Field A, Crop 3 $\to$ Field C, Crop 4 $\to$ Field E, dummy $\to$ Field B | A1 | Allow equivalent valid optimal assignment |
| Correct verification shown | B1 | |
| Correct complete allocation stated | A1 | |
## Part (b)(iii) - Maximum total score
| Answer | Mark | Guidance |
|--------|------|----------|
| $18 + 20 + 12 + 19 = 69$ | B1 ft | Follow through from their allocation |2 A farmer has five fields. He intends to grow a different crop in each of four fields and to leave one of the fields unused. The farmer tests the soil in each field and calculates a score for growing each of the four crops. The scores are given in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Field A & Field B & Field C & Field D & Field E \\
\hline
Crop 1 & 16 & 12 & 8 & 18 & 14 \\
\hline
Crop 2 & 20 & 15 & 8 & 16 & 12 \\
\hline
Crop 3 & 9 & 10 & 12 & 17 & 12 \\
\hline
Crop 4 & 18 & 11 & 17 & 15 & 19 \\
\hline
\end{tabular}
\end{center}
The farmer's aim is to maximise the total score for the four crops.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Modify the table of values by first subtracting each value in the table above from 20 and then adding an extra row of equal values.
\item Explain why the Hungarian algorithm can now be applied to the new table of values to maximise the total score for the four crops.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item By reducing rows first, show that the table from part (a)(i) becomes
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
2 & 6 & 10 & 0 & $p$ \\
\hline
0 & 5 & 12 & 4 & 8 \\
\hline
8 & 7 & 5 & 0 & $q$ \\
\hline
1 & 8 & 2 & 4 & 0 \\
\hline
0 & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
State the values of the constants $p$ and $q$.
\item Show that the zeros in the table from part (b)(i) can be covered by one horizontal and three vertical lines, and use the Hungarian algorithm to decide how the four crops should be allocated to the fields.
\item Hence find the maximum possible total score for the four crops.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D2 2011 Q2 [13]}}