AS June 2023 Q1

EdexcelCurrent spec9 marksAllocation

1. Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.

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

Worker B cannot be assigned to task Q and worker E cannot be assigned to task S.

The time, in minutes, that each worker takes to complete each task is shown in the table below.

	P	Q	R	S
A	38	39	37	37
B	39	–	39	40
C	41	44	40	42
D	40	41	39	38
E	36	39	41	–

The Hungarian algorithm is to be used to find the least total time to complete all four tasks.

(a) Explain how the table should be modified so that the Hungarian algorithm can be applied. (2)

(b)

(i) Use the Hungarian algorithm to obtain an allocation that minimises the total time.

(ii) Explain how you determined if the table was optimal at each stage. (6)

Mark scheme (a)

Scheme	Marks	AO
Add an additional dummy column with equal values (e.g. 0) to create a square array	B1	3.5c
Input a suitable large number (e.g. 100 but > 44) in cells BQ and ES	B1	1.1b
	(2)

Notes

B1: Explain the need to add a dummy column (to create a square array) – must mention that it is a column being added (but ignore any mention of the values being added to this column)

B1: Input a large value in cells BQ and ES (just saying ‘input a large value in the empty (oe) cells’ is sufficient – we do not need to know at this stage what is meant by ‘large’)

Mark scheme (b)

Scheme

Marks

e.g.

	P	Q	R	S
A	38	39	37	37
B	39	100	39	40
C	41	44	40	42
D	40	41	39	38
E	36	39	41	100

1.1b

Reducing (rows and) columns gives

	P	Q	R	S
A	2	0	0	0
B	3	61	2	3
C	5	5	3	5
D	4	2	2	1
E	0	0	4	63

1.1b

Three lines required to cover the zeros hence solution is not optimal

	P	Q	R	S	X
A	2	0	0	0	1
B	2	60	1	2	0
C	4	4	2	4	0
D	3	1	1	0	0
E	0	0	4	63	1

1.1b

Four lines required to cover the zeros hence solution is not optimal

e.g.

	P	Q	R	S	X
A	2	0	0	0	2
B	1	59	0	1	0
C	3	3	1	3	0
D	3	1	1	0	1
E	0	0	4	63	2

	P	Q	R	S	X
A	2	0	0	1	2
B	1	59	0	2	0
C	3	3	1	4	0
D	2	0	0	0	0
E	0	0	4	64	2

1.1b

Five lines required to cover the zeros hence solution is optimal

2.4

Allocation: A to Q, B to R, D to S, and E to P (C does no task)

2.2a

(6)

Notes

B1: Mark awarded when both steps complete (addition of extra column and large values ( > 44) in cells BQ and ES)

M1: Simplifying the initial matrix by reducing (rows and) columns – allow at most 2 slips

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

M1: Develop an improved solution – need to see one double covered +e; one uncovered –e; and one single covered unchanged. 4 lines needed to 5 lines needed (so getting to the optimal table)

B1: Dependent on two augmentations taking place (3 to 4 lines and then 4 to 5 lines). Either a correct statement(s) regarding the minimum number of lines to cover the zeros at each stage or a general statement that covers all augmentations.
In the first case, at each stage, they must state the number of lines (not just shown on the diagram), state whether it is optimal or not (so must use the word ‘optimal’) and mention ‘zeros’ at least once.

In the second case, they must state that until 5 lines cover the zeros then the solution is not optimal (or equivalent e.g. if there are 5 lines covering the zeros then the solution is optimal) – in this case they must show the lines.
Accept a hybrid of the two e.g. at each stage they could say whether it requires five lines or not but they would still have to mention ‘zeros’ at least once and make it clear at each augmentation whether it is optimal or not.
To award this mark we must see mention at least one mention of ‘zeros’ and the word ‘optimal’ being used.

A1: cso on final table + deduction of the correct allocation

Special case in (b) – if dashes are not replaced with larger values (e.g. values \(\leqslant 44\) or leaving dashes in place) then only the M marks are available in (b)

Scheme	Marks	AO
152 (mins)	B1	1.1b
	(1)
	(9 marks)