A2 June 2019 Q2

EdexcelCurrent spec7 marksAllocation

2. Four workers, Ted (T), Harold (H), James (J) and Margaret (M), are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

	1	2	3	4
T	103	97	74	80
H	201	155	145	155
J	111	80	77	92
M	203	188	137	184

(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. (6)

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

Mark scheme (a)

Scheme	Marks	AO
Subtracting each entry from a value \(\geqslant 203\) e.g. \(\begin{bmatrix} 100 & 106 & 129 & 123 \\ 2 & 48 & 58 & 48 \\ 92 & 123 & 126 & 111 \\ 0 & 15 & 66 & 19 \end{bmatrix}\)	1B1	1.1b
Reduce rows \(\begin{bmatrix} 0 & 6 & 29 & 23 \\ 0 & 46 & 56 & 46 \\ 0 & 31 & 34 & 19 \\ 0 & 15 & 66 & 19 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 0 & 0 & 4 \\ 0 & 40 & 27 & 27 \\ 0 & 25 & 5 & 0 \\ 0 & 9 & 37 & 0 \end{bmatrix}\)	1M1 1A1ft	2.1 1.1b
followed by \(\begin{bmatrix} 5 & 0 & 0 & 9 \\ 0 & 35 & 22 & 27 \\ 0 & 20 & 0 & 0 \\ 0 & 4 & 32 & 0 \end{bmatrix}\)	2M1 2A1ft	2.1 1.1b
T – 2, H – 1, J – 3, M – 4	3A1	2.2a
	(6)

Notes

1B1: CAO

1M1: simplifying the initial matrix by reducing rows and then columns. Allow no more than a single error in row reduction together with no more than a single error in column reduction. May combine the two stages of converting from maximum to a minimum problem and row reduction which is acceptable.

1A1ft: CAO following on from their earlier conversion to maximising. If 1B1 awarded, the result of row and column reduction must be as in the main scheme. If 1B0 awarded, then row and column reduction must ft correctly from their attempt to convert to maximisation problem.

2M1: develops 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

2A1ft: Improved solution following on from their previous table

3A1: CSO Correct allocation. Must have gained all previous marks in the question.

SC: Minimising

After row reduction \(\begin{bmatrix} 29 & 23 & 0 & 6 \\ 56 & 10 & 0 & 10 \\ 34 & 3 & 0 & 15 \\ 66 & 51 & 0 & 47 \end{bmatrix}\) and then after column reduction \(\begin{bmatrix} 0 & 20 & 0 & 0 \\ 27 & 7 & 0 & 4 \\ 5 & 0 & 0 & 9 \\ 37 & 48 & 0 & 41 \end{bmatrix}\)

After augmentation \(\begin{bmatrix} 0 & 20 & 4 & 0 \\ 23 & 3 & 0 & 0 \\ 5 & 0 & 4 & 9 \\ 33 & 44 & 0 & 37 \end{bmatrix}\) or \(\begin{bmatrix} 0 & 24 & 4 & 0 \\ 23 & 7 & 0 & 0 \\ 1 & 0 & 0 & 5 \\ 33 & 48 & 0 & 37 \end{bmatrix}\)

Scores B0 M1A0 M1A1(ft)A0 B0 (So 3 marks max)

1B0: No Minimisation

1M1: simplifying the initial matrix by reducing rows and then columns – all values ‘correct’

1A0: Must be maximising.

2M1: develops 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

2A1ft: Improved solution following on from their previous table

3A0: CSO

1B0: Must be maximising

Scheme	Marks	AO
(£)559	1B1	1.1b
	(1)
	(7 marks)