A2 October 2020 Q1

EdexcelCurrent spec8 marksAllocation

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

Worker A cannot do task 3 and worker B cannot do task 4

The table below shows the profit, in pounds, that each worker would earn if assigned to each of the tasks.

	1	2	3	4
A	29	20	–	23
B	32	30	28	–
C	35	32	34	25
D	29	31	27	30

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

(b) Determine the resulting total profit. (1)

Mark scheme (a)

Scheme	Marks	AO
Subtracting each entry from a constant value \(\geqslant 35\) to convert from maximisation problem to minimisation	M1	1.1b
Add a sufficiently large number (\(> 15\)) to cells A3 and B4 e.g. \(\begin{bmatrix} 6 & 15 & 100 & 12 \\ 3 & 5 & 7 & 100 \\ 0 & 3 & 1 & 10 \\ 6 & 4 & 8 & 5 \end{bmatrix}\)	B1	1.1b
Reduce rows \(\begin{bmatrix} 0 & 9 & 94 & 6 \\ 0 & 2 & 4 & 97 \\ 0 & 3 & 1 & 10 \\ 2 & 0 & 4 & 1 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 9 & 93 & 5 \\ 0 & 2 & 3 & 96 \\ 0 & 3 & 0 & 9 \\ 2 & 0 & 3 & 0 \end{bmatrix}\)	M1 A1ft	2.1 1.1b
followed by \(\begin{bmatrix} 0 & 7 & 93 & 3 \\ 0 & 0 & 3 & 94 \\ 0 & 1 & 0 & 7 \\ 4 & 0 & 5 & 0 \end{bmatrix}\) or \(\begin{bmatrix} 0 & 7 & 91 & 3 \\ 0 & 0 & 1 & 94 \\ 2 & 3 & 0 & 9 \\ 4 & 0 & 3 & 0 \end{bmatrix}\)	M1 A1ft	2.1 1.1b
A – 1, B – 2, C – 3, D – 4	B1ft	1.1b
	(7)

Notes

M1: convert from maximisation to minimisation (allow at most two errors)

B1: adding a large number (at least 16) to cells A3 and B4

M1: simplifying the initial matrix by reducing rows and then columns

A1ft: cao following on from their earlier subtraction

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

A1ft: cao following on from row and column reduction final table

(b) B1ft: correct allocation ft their optimal table (all previous M marks must have been awarded in (a))

Scheme	Marks	AO
£123	B1	1.1b
	(1)
	(8 marks)