D2 June 2013 (R) Q1

EdexcelOld spec10 marksAllocation

1. Four workers, Chris (C), James (J), Katie (K) and Nicky (N), are to be allocated to four tasks, 1, 2, 3 and 4. Each worker is to be allocated to one task and each task must be allocated to 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
Chris	127	116	111	113
James	225	208	205	208
Katie	130	113	112	114
Nicky	228	212	203	210

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

(b) State which worker should be allocated to each task and the resulting total profit made. (2)

Mark scheme (a)

Scheme

Marks

Subtracting all elements from some \(n \geqslant 228\)

1M1

Reducing rows and then columns to get

2M1

11	16	14
17	20	17
17	18	16
16	25	18

then

0	0	0
6	4	3
6	2	2
5	9	4

1A1

Using two lines and 2 to get

3M1

2	0	0	0
0	4	2	1
0	4	0	0
0	3	7	2

2A1

Using three lines and 1 to get

4M1

3	0*	0	0
0	3	1	0*
1	4	0*	0
0*	2	6	1

3A1ft 4A1

(8)

Notes

a1M1: Subtracting all elements from some \(n \geqslant 228\), condone up to 2 errors

a2M1: Reducing rows and then columns

a1A1: CAO

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

a2A1: CAO

a4M1: One double covered +e; one uncovered – e; and one single covered unchanged. 3 lines needed to 4 lines needed.

a3A1ft: on their previous table.

a4A1: CSO on final table

Mark scheme (b)

Scheme	Marks
So C = 2, J = 4, K = 3 and N = 1	M1
maximum profit of £664	A1
	(2)
	10 marks

Notes

Note ‘minimise’ gives this special case

0	4	0
4	2	1
2	0	0
9	8	4

then

0*	4	1	0
3	1	0	0*
2	0*	1	0
8	7	0*	3

then

C = 1
J = 4
K = 2
N = 3

Profit £651

Gives 5 max: (a) 1M0 2M1 1A1 3M0 2A0 4M1 3A1ft 4A0 (b) M1A0

b1M1: Their optimal allocation (of workers to tasks) and an attempt to calculate the profit – this mark is dependent on all M marks in (a) have been earned.

b1A1: CAO