AS June 2022 Q1

EdexcelCurrent spec7 marksAllocation

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

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

Worker C cannot be assigned to task Q and worker D 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	54	48	51	52
B	55	51	53	58
C	52	–	53	54
D	67	63	68	–

The Hungarian algorithm is to be used to find the minimum total time for the four workers to complete the tasks.

(a) Modify the table so that the Hungarian algorithm may be used. (1)

(b) Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total time. You should explain how any initial row and column reductions are made and also how you determine if the table is optimal at each stage. (6)

Mark scheme (b)

Scheme

Marks

Reduce row A by 48, reduce row B by 51, reduce row C by 52 and row D by 63 (or equivalent). No reduction for columns P and Q, reduce R by 1 and column S by 2

2.4

Reducing rows and columns gives

e.g.

	P	Q	R	S
A	6	0	3	4
B	4	0	2	7
C	0	48	1	2
D	4	0	5	37

followed by

	P	Q	R	S
A	6	0	2	2
B	4	0	1	5
C	0	48	0	0
D	4	0	4	35

1.1b

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

e.g.

	P	Q	R	S
A	5	0	1	1
B	3	0	0	4
C	0	49	0	0
D	3	0	3	34

1.1b

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

e.g.

	P	Q	R	S
A	4	0	0	0
B	3	1	0	4
C	0	50	0	0
D	2	0	2	33

or e.g.

	P	Q	R	S
A	4	0	1	0
B	2	0	0	3
C	0	50	1	0
D	2	0	3	33

1.1b

Four lines required to cover the zeros hence solution is optimal

2.4

A – S, B – R, C – P, D – Q

2.2a

(6)

(7 marks)

Notes

B1: Correct statements regarding row and column reduction

M1: Simplifying the initial matrix by reducing rows and then columns – allow 2 independent slips

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: Dependent on two augmentations taking place (2 to 3 lines and then 3 to 4). 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 4 lines cover the zeros then the solution is not optimal (or equivalent e.g. if there are 4 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 four 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