A2 June 2022 Q1

EdexcelCurrent spec6 marksAllocation

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each task must be assigned to just one worker and each worker must do only one task.

The cost of assigning each worker to each task is shown in the table below.

The total cost is to be minimised.

	1	2	3	4
A	32	45	34	48
B	37	39	50	46
C	46	44	40	42
D	43	45	48	52

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

(b) State the minimum total cost. (1)

Mark scheme (a)

Scheme	Marks	AO
Reduce rows \(\begin{bmatrix} 0 & 13 & 2 & 16 \\ 0 & 2 & 13 & 9 \\ 6 & 4 & 0 & 2 \\ 0 & 2 & 5 & 9 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 11 & 2 & 14 \\ 0 & 0 & 13 & 7 \\ 6 & 2 & 0 & 0 \\ 0 & 0 & 5 & 7 \end{bmatrix}\)	M1 A1	2.1 1.1b
Followed by \(\begin{bmatrix} 0 & 11 & 0 & 12 \\ 0 & 0 & 11 & 5 \\ 8 & 4 & 0 & 0 \\ 0 & 0 & 3 & 5 \end{bmatrix}\)	M1 A1ft	2.1 1.1b
A – 3, B – 1, C – 4, D – 2 or A – 3, B – 2, C – 4, D – 1	A1ft	2.2a
	(5)

Notes

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.

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

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 zeros on final matrix).

Scheme	Marks	AO
158	B1	1.1b
	(1)
	(6 marks)