D2 June 2012 Q1

EdexcelOld spec9 marksAllocation

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

The cost, in pounds, of assigning each person to each task is shown in the table below. The cost is to be minimised.

	1	2	3	4	5
A	129	127	122	134	135
B	127	125	123	131	132
C	142	131	121	140	139
D	127	127	122	131	136
E	141	134	129	144	143

(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 cost. (1)

Mark scheme (a)

Scheme	Marks
\(\begin{bmatrix}129 & 127 & 122 & 134 & 135 \\ 127 & 125 & 123 & 131 & 132 \\ 142 & 131 & 121 & 140 & 139 \\ 127 & 127 & 122 & 131 & 136 \\ 141 & 134 & 129 & 144 & 143\end{bmatrix}\) Reducing rows then columns \(\begin{bmatrix}7 & 5 & 0 & 12 & 13 \\ 4 & 2 & 0 & 8 & 9 \\ 21 & 10 & 0 & 19 & 18 \\ 5 & 5 & 0 & 9 & 14 \\ 12 & 5 & 0 & 15 & 14\end{bmatrix}\rightarrow\begin{bmatrix}3 & 3 & 0 & 4 & 4 \\ 0 & 0 & 0 & 0 & 0 \\ 17 & 8 & 0 & 11 & 9 \\ 1 & 3 & 0 & 1 & 5 \\ 8 & 3 & 0 & 7 & 5\end{bmatrix}\)	1M1 1A1
\(\begin{bmatrix}2 & 2 & 0 & 3 & 3 \\ 0 & 0 & 1 & 0 & 0 \\ 16 & 7 & 0 & 10 & 8 \\ 0 & 2 & 0 & 0 & 4 \\ 7 & 2 & 0 & 6 & 4\end{bmatrix}\)	2M1 2A1ft
\(\begin{bmatrix}0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 3 & 0 & 0 \\ 14 & 5 & 0 & 8 & 6 \\ 0 & 2 & 2 & 0 & 4 \\ 5 & 0 & 0 & 4 & 2\end{bmatrix}\)	3M1 3A1ft 4A1 cso
Allocation: A – 1, B – 5, C – 3, D – 4, E – 2.	5A1= B1
	(8)

Notes

a1M1 Reducing rows and then columns – See special case

a1A1 CAO

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

a2A1ft ft on their previous table.

a3M1 Double covered +e; one uncovered – e; and one single covered unchanged. 3 lines needed to 5 lines needed. Watch out for ‘slow Hungarian’ (e.g. 2 ‘iterations’ each subtracting 1), give M0 if seen.

a3A1ft ft on their previous table. Condone one ‘new’ error in table here.

a4A1 CSO on final table

a5A1= B1 CAO

Scheme	Marks
Cost is £ 647	B1
	(1)
	(9 marks)