| Exam Board | Edexcel |
|---|---|
| Module | FD2 AS (Further Decision 2 AS) |
| Year | 2024 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with restrictions |
| Difficulty | Standard +0.8 This is a standard Hungarian algorithm application with forbidden assignments, requiring students to convert maximization to minimization, handle restrictions, perform row/column reductions, and find optimal allocation. While methodical, it's routine for FD2 students who've practiced the algorithm, involving more computation than conceptual insight. |
| Spec | 7.03k Sorting: quick sort |
| \cline { 2 - 6 } \multicolumn{1}{c|}{} | \(\mathbf { P }\) | \(\mathbf { Q }\) | \(\mathbf { R }\) | \(\mathbf { S }\) | \(\mathbf { T }\) |
| \(\mathbf { A }\) | 32 | 40 | 35 | 41 | 37 |
| \(\mathbf { B }\) | 38 | - | 40 | 27 | 33 |
| \(\mathbf { C }\) | 41 | 28 | 37 | 36 | 35 |
| \(\mathbf { D }\) | 35 | 33 | 38 | 36 | - |
| \(\mathbf { E }\) | 40 | 38 | - | 39 | 34 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Subtract each entry from a constant (e.g. 50) to convert from maximisation problem to minimisation | B1 | Valid statement regarding converting maximisation to minimisation |
| Add a large value (e.g. 100) to cells BQ, DT and ER so that they cannot be selected | B1 | Must be clear which order the changes are applied |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Initial matrix with subtraction from constant and addition of large values applied correctly, e.g. \(A\): 18,10,15,9,13; \(B\): 12,100,10,23,17; \(C\): 9,22,13,14,15; \(D\): 15,17,12,14,100; \(E\): 10,12,100,11,16 | B1 | Mark awarded when both steps complete; accept one slip in values |
| Reducing rows then columns to give reduced matrix | M1 | Simplifying the initial matrix by reducing rows then columns; accept one additional slip |
| 3 lines required (Row A, Columns P, R) so augment by 1 to give improved matrix | M1 | Need to see one double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 3 lines needed to 4 lines |
| 4 lines required (e.g. Row A, E, Column P, R) so augment by 1 to give optimal matrix | M1 | Need to see one double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 4 lines to 5 lines |
| Allocation \(A-T\), \(B-R\), \(C-P\), \(D-S\), \(E-Q\) | A1 | CSO on final table; note there are different fully correct tables |
| Maximum Score: 192 | B1 | Maximum score stated |
# Question 2:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Subtract each entry from a constant (e.g. 50) to convert from maximisation problem to minimisation | B1 | Valid statement regarding converting maximisation to minimisation |
| Add a large value (e.g. 100) to cells BQ, DT and ER so that they cannot be selected | B1 | Must be clear which order the changes are applied |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Initial matrix with subtraction from constant and addition of large values applied correctly, e.g. $A$: 18,10,15,9,13; $B$: 12,100,10,23,17; $C$: 9,22,13,14,15; $D$: 15,17,12,14,100; $E$: 10,12,100,11,16 | B1 | Mark awarded when both steps complete; accept one slip in values |
| Reducing rows then columns to give reduced matrix | M1 | Simplifying the initial matrix by reducing rows then columns; accept one additional slip |
| 3 lines required (Row A, Columns P, R) so augment by 1 to give improved matrix | M1 | Need to see one double covered $+e$; one uncovered $-e$; one single covered unchanged. 3 lines needed to 4 lines |
| 4 lines required (e.g. Row A, E, Column P, R) so augment by 1 to give optimal matrix | M1 | Need to see one double covered $+e$; one uncovered $-e$; one single covered unchanged. 4 lines to 5 lines |
| Allocation $A-T$, $B-R$, $C-P$, $D-S$, $E-Q$ | A1 | CSO on final table; note there are different fully correct tables |
| Maximum Score: 192 | B1 | Maximum score stated |
---2. A team of 5 players, A, B, C, D and E, competes in a quiz. Each player must answer one of 5 rounds, $\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }$ and T .
Each player must be assigned to exactly one round, and each round must be answered by exactly one player.
Player B cannot answer round Q, player D cannot answer round T, and player E cannot answer round R.
The number of points that each player is expected to earn in each round is shown in the table.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & $\mathbf { P }$ & $\mathbf { Q }$ & $\mathbf { R }$ & $\mathbf { S }$ & $\mathbf { T }$ \\
\hline
$\mathbf { A }$ & 32 & 40 & 35 & 41 & 37 \\
\hline
$\mathbf { B }$ & 38 & - & 40 & 27 & 33 \\
\hline
$\mathbf { C }$ & 41 & 28 & 37 & 36 & 35 \\
\hline
$\mathbf { D }$ & 35 & 33 & 38 & 36 & - \\
\hline
$\mathbf { E }$ & 40 & 38 & - & 39 & 34 \\
\hline
\end{tabular}
\end{center}
The team wants to maximise its total expected score.\\
The Hungarian algorithm is to be used to find the maximum total expected score that can be earned by the 5 players.
\begin{enumerate}[label=(\alph*)]
\item Explain how the table should be modified.
\item \begin{enumerate}[label=(\roman*)]
\item Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total expected score.
\item Calculate the maximum total expected score.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 AS 2024 Q2 [8]}}