D2 June 2016 Q3

EdexcelOld spec9 marksAllocation

3. Four pupils, Alexa, Ewan, Faith and Zak, are to be allocated to four rounds, 1, 2, 3 and 4, in a mathematics competition. Each pupil is to be allocated to exactly one round and each round must be allocated to exactly one pupil.

Each pupil has been given a score, based on previous performance, to show how suitable they are for each round. The higher the score the more suitable the pupil is for that round. The scores for each pupil are shown in the table below.

	1	2	3	4
Alexa	61	50	47	23
Ewan	71	62	20	61
Faith	70	49	48	49
Zak	72	68	67	67

(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total score. You must make your method clear and show the table after each stage. (8)

(b) State the maximum total score. (1)

Mark scheme (a)

Scheme	Marks
Since maximising, subtract all elements from some value \(\geqslant 72\) e.g \(\begin{bmatrix}11&22&25&49\\1&10&52&11\\2&23&24&23\\0&4&5&5\end{bmatrix}\)	M1
Reduce rows \(\begin{bmatrix}0&11&14&38\\0&9&51&10\\0&21&22&21\\0&4&5&5\end{bmatrix}\) and then columns \(\begin{bmatrix}0&7&9&33\\0&5&46&5\\0&17&17&16\\0&0&0&0\end{bmatrix}\)	M1 A1
\(\begin{bmatrix}0&2&4&28\\0&0&41&0\\0&12&12&11\\5&0&0&0\end{bmatrix}\) followed by \(\begin{bmatrix}0&0&2&26\\2&0&41&0\\0&10&10&9\\7&0&0&0\end{bmatrix}\)	M1 A1ft M1 A1
Optimal allocation is F = 1, A = 2, Z = 3, E = 4	A1
	(8)

Notes

a1M1: Subtracting from some value which must be \(\geqslant 72\) or all values made negative and then adding a value which must be \(\geqslant 72\). Condone no more than two errors

a2M1: Reducing rows and then columns – candidates may combine the two stages of converting from a maximum to a minimum problem and row reduction which is acceptable

a1A1: CAO

a3M1: Double covered +e; one uncovered –e ; and one single covered unchanged. 2 lines to 3 lines needed

a2A1ft: Follow through on their previous table – no errors

a4M1: One double covered +e; one uncovered –e; and one single covered unchanged. 3 lines needed to 4 lines needed (so getting to the optimal table)

a3A1: CSO on final table (so must have scored all previous marks)

a4A1: CAO – this mark is dependent on all M marks being awarded

SC: Minimising

After row reduction

\(\begin{bmatrix}38&27&24&0\\51&42&0&41\\22&1&0&1\\5&1&0&0\end{bmatrix}\)

and then after column reduction

\(\begin{bmatrix}33&26&24&0\\46&41&0&41\\17&0&0&1\\0&0&0&0\end{bmatrix}\)

scores M0 M1A1 M0A0 M0A0 A0 B0 (so 2 marks max)

Scheme	Marks
(Total score is = ) 248	B1
	(1)
	9 marks