AS June 2019 Q1

EdexcelCurrent spec9 marksAllocation

1. Three workers, A, B and C, are each to be assigned to one of four tasks, P, Q, R and S.

Each worker must be assigned to at most one task, and each task must be done by at most one worker.

The amount, in pounds, that each worker will earn while assigned to each task is shown in the table below.

	P	Q	R	S
A	32	40	37	42
B	29	32	35	41
C	37	33	39	40

The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the three workers.

(a) Explain how the table should be modified. (2)

(b)

(i) Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings.

(ii) Explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage. (7)

Mark scheme (a)

Scheme	Marks	AO
Subtract each entry from a constant (e.g. 42) to covert from maximisation problem to minimisation	B1	1.1a
Add an additional dummy row with equal values (e.g. 42, 0, etc.) to create a square array	B1	3.5c
	(2)

Notes

B1: Valid statement regarding converting a maximisation problem to a minimisation problem – must imply subtracting each entry from a constant (although the value of this constant need not be stated)

B1: Explain the need to add a valid dummy row (to create a square array) e.g. allow mention of adding an additional worker or the need to have a square array

Mark scheme (b)

Scheme

Marks

e.g.

	P	Q	R	S
A	10	2	5	0
B	13	10	7	1
C	5	9	3	2
X	42	42	42	42

1.1b

No reduction for row A, reduce row B by 1, reduce row C by 2 and row X by 42 (or equivalent). No reduction of columns

2.4

Reducing rows and columns gives

	P	Q	R
A	10	2	5
B	12	9	6
C	3	7	1
X	0	0	0

1.1b

Two lines required to cover the zeros hence solution is not optimal (augment by 1)

	P	Q	R	S
A	9	1	4	0
B	11	8	5	0
C	2	6	0	0
X	0	0	0	1

1.1b

Three lines required to cover the zeros hence solution is not optimal (augment by 1)

e.g.

	P	Q	R	S
A	8	0	3	0
B	10	7	4	0
C	2	6	0	1
X	0	0	0	2

	P	Q	R	S
A	8	0	4	0
B	10	7	5	0
C	1	5	0	0
X	0	0	1	2

1.1b

Four lines required to cover the zeros hence solution is optimal

2.4

A – Q, B – S, C – R, (X – P)

2.2a

(7)

(9 marks)

Notes

B1: Mark awarded when both steps complete (a valid subtraction and addition of a correct extra row)

B1: Correct statements regarding row and column reduction – if explicit values not stated then it must be clear that reduction is done by subtracting the least value in each row/column from each element of that row/column

M1: Simplifying the initial matrix by reducing rows and then columns – allow one error

M1: Develop an improved solution – need to see one double covered +e; one uncovered –e; and one single covered unchanged. 2 lines needed to 3 lines needed

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 (so getting to the optimal table)

B1: Correct statement(s) regarding the minimum number of lines to cover zeros at each stage or a general statement that covers all augmentations (e.g. if we have an \(n\) by \(n\) array then if the minimum number of lines required to cover the zeros is less than \(n\) then the solution is not optimal but if the minimum number of lines to cover the zeros is \(n\) then it is optimal – as an absolute minimum allow mention that until there are 4 lines covering the zeros then the solution is not optimal (oe) – however, in all cases, there must have been two augmentations taking place (2 to 3 lines and then 3 to 4))

A1: CSO for the application of the Hungarian algorithm - so correct application of the algorithm from a correct initial matrix (so in (b) candidates must have scored at least B1B0M1M1M1B0) – together with the deduction of the correct allocation

Note that if array is not square or if the additional row is given entries of ‘infinity’ then only the second B mark in (b) can be awarded