A2 June 2025 Q2

EdexcelCurrent spec9 marksAllocation

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

Each worker can 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 R.

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

	P	Q	R	S
A	25	32	43	28
B	41	37	–	38
C	43	35	37	39
D	40	33	37	41
E	37	38	43	40

The Hungarian algorithm is to be used to find an allocation that minimises the 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) Use the Hungarian algorithm to obtain an allocation that minimises the total time. (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 > 43) in cell BR	B1	1.1b
	(2)

Notes

B1: Explain the need to add a dummy column to create a square array

B1: Input a large value in cell BR

Mark scheme (b)

Scheme

Marks

e.g.

	P	Q	R	S
A	25	32	43	28
B	41	37	100	38
C	43	35	37	39
D	40	33	37	41
E	37	38	43	40

1.1b

Reducing (rows and) columns gives

	P	Q	R	S
A	0	0	6	0
B	16	5	63	10
C	18	3	0	11
D	15	1	0	13
E	12	6	6	12

1.1b

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

	P	Q	R	S	X
A	0	0	7	0	1
B	15	4	63	9	0
C	17	2	0	10	0
D	14	0	0	12	0
E	11	5	6	11	0

1.1b

Four lines (e.g. A, Q, R and X) required to cover the zeros hence solution is not optimal (augment by 9)

e.g.

	P	Q	R	S	X
A	0	9	16	0	10
B	6	4	63	0	0
C	8	2	0	1	0
D	5	0	0	3	0
E	2	5	6	2	0

M1
A1

1.1b
1.1b

Five lines required to cover the zeros hence solution is optimal

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

A1ft

2.2a

(6)

Notes

(b) See Example for large number in dummy

B1: Mark awarded when both steps complete (addition of extra column with 0s in every cell and large value in cell BR) (Note may be implied by sight of table with (rows and) columns reduced)

M1: Simplifying the initial matrix by reducing columns

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

A1: CSO on final table (so must have scored all previous marks in this part with no errors)

A1ft: Deduction of the correct allocations following through their 5 line final table (must have scored all previous M marks)

Alternatives for (b) – after 4 lines may possibly see another 4 lines before 5 lines or two further 4 lines before 5 lines

The 3^rd M mark in this case is only awarded when 5 lines are needed

e.g. (shaded in the printed scheme: rows A, C and D and column X)

	P	Q	R	S	X
A	0	0	7	0	1
B	15	4	63	9	0
C	17	2	0	10	0
D	14	0	0	12	0
E	11	5	6	11	0

(shaded in the printed scheme: row A and columns Q, R and X)

	P	Q	R	S	X
A	0	0	7	0	5
B	11	0	59	5	0
C	17	2	0	10	4
D	14	0	0	12	4
E	7	1	2	7	0

	P	Q	R	S	X
A	0	5	12	0	10
B	6	0	59	0	0
C	12	2	0	5	4
D	9	0	0	7	4
E	2	1	2	2	0

or e.g. (shaded in the printed scheme: rows A and D and columns R and X)

	P	Q	R	S	X
A	0	0	7	0	1
B	15	4	63	9	0
C	17	2	0	10	0
D	14	0	0	12	0
E	11	5	6	11	0

(shaded in the printed scheme: rows A, C and D and column X)

	P	Q	R	S	X
A	0	0	9	0	3
B	13	2	63	7	0
C	15	0	0	8	0
D	14	0	2	12	2
E	9	3	6	9	0

(shaded in the printed scheme: row A and columns Q, R and X)

	P	Q	R	S	X
A	0	0	9	0	5
B	11	0	61	5	0
C	15	0	0	8	2
D	14	0	2	12	4
E	7	1	4	7	0

	P	Q	R	S	X
A	0	5	14	0	10
B	6	0	61	0	0
C	10	0	0	3	2
D	9	0	2	7	4
E	2	1	4	2	0

Example – Large Number in Dummy – (b) B1 M1 M1 M1 A1 A1

	P	Q	R	S	X
A	25	32	43	28	100
B	41	37	100	38	100
C	43	35	37	39	100
D	40	33	37	41	100
E	37	38	43	40	100

	P	Q	R	S	X
A	0	7	18	3	75
B	4	0	63	1	63
C	8	0	2	4	65
D	7	0	4	8	67
E	0	1	6	3	63

(shaded in the printed scheme: AP, BS, CR, DQ and EX)

	P	Q	R	S	X
A	0	7	16	2	12
B	4	0	61	0	0
C	8	0	0	3	2
D	7	0	2	7	4
E	0	1	4	2	0

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