A2 June 2023 Q4

EdexcelCurrent spec8 marksAllocation

4. Four students, A, B, C and D, are to be allocated to four rounds, 1, 2, 3 and 4, in a competition. Each student is to take part in exactly one round and no two students may play in the same round.

Each student has been given an estimated score for each round. The estimated scores for each student are shown in the table below.

	1	2	3	4
A	34	20	18	15
B	49	31	12	34
C	48	27	23	26
D	52	45	42	42

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

(b) Find this total estimated score. (1)

Mark scheme (a)

Scheme	Marks	AO
Since maximising, subtract all elements from some value \(\geqslant 52\) e.g. \(\begin{bmatrix} 18 & 32 & 34 & 37 \\ 3 & 21 & 40 & 18 \\ 4 & 25 & 29 & 26 \\ 0 & 7 & 10 & 10 \end{bmatrix}\)	B1	1.1b
Reduce rows \(\begin{bmatrix} 0 & 14 & 16 & 19 \\ 0 & 18 & 37 & 15 \\ 0 & 21 & 25 & 22 \\ 0 & 7 & 10 & 10 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 7 & 6 & 9 \\ 0 & 11 & 27 & 5 \\ 0 & 14 & 15 & 12 \\ 0 & 0 & 0 & 0 \end{bmatrix}\)	M1 A1	2.1 1.1b
\(\begin{bmatrix} 0 & 2 & 1 & 4 \\ 0 & 6 & 22 & 0 \\ 0 & 9 & 10 & 7 \\ 5 & 0 & 0 & 0 \end{bmatrix}\) followed by \(\begin{bmatrix} 0 & 1 & 0 & 3 \\ 1 & 6 & 22 & 0 \\ 0 & 8 & 9 & 6 \\ 6 & 0 & 0 & 0 \end{bmatrix}\) or \(\begin{bmatrix} 0 & 1 & 0 & 4 \\ 0 & 5 & 21 & 0 \\ 0 & 8 & 9 & 7 \\ 6 & 0 & 0 & 1 \end{bmatrix}\)	M1 A1ft A1	2.1 1.1b 1.1b
Optimal allocation is A = 3, B = 4, C = 1, D = 2	A1ft	2.2a
	(7)

Notes

B1: converting correctly from a minimisation to maximisation

M1: simplifying the initial matrix by reducing rows and then columns (allow up to 2 independent slips)

A1: CAO

M1: develop an improved solution – need to see one double covered +e; one uncovered –e; and one single covered unchanged. 2 lines needed to 3 lines needed (lines may be implied). If lines are drawn they must be correct.

A1ft: CAO following on from row and column reduction from previous table (f/t from previous table with no further slips)

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

A1ft: correct allocation ft their optimal table (both previous M marks must have been awarded in (a)) (Must be fully written. Do not accept just indicated on zeroes on final matrix)

Special Case – minimisation – max 4/8

Scheme	Marks	AO
Special Case – minimisation – max 4/8	B0
Reduce rows \(\begin{bmatrix} 19 & 5 & 3 & 0 \\ 37 & 19 & 0 & 22 \\ 25 & 4 & 0 & 3 \\ 10 & 3 & 0 & 0 \end{bmatrix}\) and then columns \(\begin{bmatrix} 9 & 2 & 3 & 0 \\ 27 & 16 & 0 & 22 \\ 15 & 1 & 0 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix}\)	M1 A1
followed by \(\begin{bmatrix} 8 & 1 & 3 & 0 \\ 26 & 15 & 0 & 22 \\ 14 & 0 & 0 & 3 \\ 0 & 0 & 1 & 1 \end{bmatrix}\) or \(\begin{bmatrix} 9 & 2 & 4 & 0 \\ 26 & 15 & 0 & 21 \\ 14 & 0 & 0 & 2 \\ 0 & 0 & 1 & 0 \end{bmatrix}\)	M1 A1 A0
Optimal allocation is	A0
	(7)
(b) Total score	B0
	(1)
	(8 marks)

B0: no conversion

M1: simplifying the initial matrix by reducing rows and then columns (allow up to 2 independent slips)

A1: CAO

M1: develop an improved solution – need to see one double covered +e; one uncovered –e; and one single covered unchanged. 3 lines needed to 4 lines needed (lines may be implied). If lines are drawn they must be correct.

A1: CAO No further marks awarded