D2 June 2018 Q3

EdexcelOld spec11 marksAllocation

3. Five workers, A, B, C, D and E, are to be assigned to five tasks, 1, 2, 3, 4 and 5. Each worker must be assigned to only one task and each task must be done by only one worker.

The cost, in pounds, of assigning each worker to each task is shown in the table below. The cost of assigning worker D to task 4 is £\(x\), where \(x \gt 38\)

	1	2	3	4	5
A	25	31	27	29	35
B	29	33	40	35	37
C	28	29	35	36	37
D	34	35	36	\(x\)	41
E	36	35	32	31	33

The total cost is to be minimised.

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

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

Workers A and D decide that they do not like the task they have been allocated and are allowed to swap tasks with each other. The other three allocations are unchanged. The cost now of allocating the five workers to the five tasks is now £5 more than the minimum cost found in (b).

Mark scheme (a)

Scheme	Marks
Reducing rows and columns to get \(\begin{pmatrix} 0 & 6 & 2 & 4 & 10 \\ 0 & 4 & 11 & 6 & 8 \\ 0 & 1 & 7 & 8 & 9 \\ 0 & 1 & 2 & x-34 & 7 \\ 5 & 4 & 1 & 0 & 2 \end{pmatrix}\)	M1
then \(\begin{pmatrix} 0 & 5 & 1 & 4 & 8 \\ 0 & 3 & 10 & 6 & 6 \\ 0 & 0 & 6 & 8 & 7 \\ 0 & 0 & 1 & x-34 & 5 \\ 5 & 3 & 0 & 0 & 0 \end{pmatrix}\)	A1
Using three lines and augment by 1 to get \(\begin{pmatrix} 0 & 5 & 0 & 3 & 7 \\ 0 & 3 & 9 & 5 & 5 \\ 0 & 0 & 5 & 7 & 6 \\ 0 & 0 & 0 & x-35 & 4 \\ 6 & 4 & 0 & 0 & 0 \end{pmatrix}\)	M1 A1
Using four lines and augment by 3 to get \(\begin{pmatrix} 0 & 5 & 0 & 0 & 4 \\ 0 & 3 & 9 & 2 & 2 \\ 0 & 0 & 5 & 4 & 3 \\ 0 & 0 & 0 & x-38 & 1 \\ 9 & 7 & 3 & 0 & 0 \end{pmatrix}\)	M1 A1ft A1
So A = 4, B = 1, C = 2, D = 3, E = 5	A1
	(8)

Notes

a1M1: Reducing rows and then columns (allow errors)

a1A1: CAO

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

a2A2: CAO

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

a3A1ft: Follow through on their previous table

a4A1: CSO on final table

a5A1: Correct allocation – dependent on all previous M marks – need not be stated but must be clear – allow if stated in (b)

In (b) if a candidate replaces the \(x\) with ‘> 38’ (or an equivalent general correct statement – but not a specific value greater than 38) and then after row reduction has ‘> 4’ etc. then this can possibly score full marks (as this is equivalent to \(x - 38\)). See below SC2 and SC3 for when \(x\) is replaced by a specific value

SC1: If attempt to maximise this can score M1A0M1A0M1A0A0A0 (3 out of 8 max. in (a)) mark (b) and (c) according to main scheme

SC2: If \(x\) given a value greater than 38 this can score M1A0M1A0M1A1ftA0A1 (5 out of 8 max. in (a)) mark (b) and (c) according to main scheme

SC3: If \(x\) given a value less than or equal to 38 then M1A0M1A0M0A0A0A0 (2 max.)

Scheme	Marks
(£)156	B1
	(1)

Mark scheme (c)

Scheme	Marks
\(29 + 29 + 27 + x + 33 = 156 + 5\)	M1
\(x = 43\)	A1
	(2)
	11 marks

Notes

c1M1: Their allocation with A and D interchanged = their (b) + 5 (oe) - not dependent on any previous mark

c1A1: CAO