AS June 2025 Q1

EdexcelCurrent spec9 marksAllocation

1. Five workers, A, B, C, D and E, are each to be assigned to one of five tasks, J, K, L, M and N. Each task must be assigned to exactly one worker and each worker must do exactly one task.

Worker C cannot do task L and worker D cannot do task K.

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

	J	K	L	M	N
A	38	33	40	35	32
B	26	24	27	25	23
C	33	29	–	30	27
D	36	–	41	37	33
E	32	27	31	29	25

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

(a) Explain how the contents of the table must be modified to allow the algorithm to be used. (2)

(b) Reducing rows first, use the Hungarian algorithm to obtain the maximum total profit. 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. (7)

Mark scheme (a)

Scheme	Marks	AO
Subtract each entry from a constant, e.g. 50. Replace the two empty cells with a large number. e.g. 100.	B1 B1	1.1a 3.5c
	(2)

Notes

a1B1: Correct statement.

a2B1: Correct statement. (Note the statements must be in the correct order so subtraction followed by large values – if order reversed B1 B0)

Mark scheme (b)

Scheme

Marks

e.g.

	J	K	L	M	N
A	12	17	10	15	18
B	24	26	23	25	27
C	17	21	100	20	23
D	14	100	9	13	17
E	18	23	19	21	25

1.1b

Reduce each row by its minimum element and then in the revised matrix reduce each column by its minimum element.

2.4

Reducing rows and columns gives

e.g.

	J	K	L	M	N
A	2	4	0	3	4
B	1	0	0	0	0
C	0	1	83	1	2
D	5	88	0	2	4
E	0	2	1	1	3

1.1b

Minimum of 3 lines required to cover zeros, hence solution is not optimal (augment by 1).

e.g.

	J	K	L	M	N
A	2	3	0	2	3
B	2	0	1	0	0
C	0	0	83	0	1
D	5	87	0	1	3
E	0	1	1	0	2

Minimum of 4 lines required to cover zeros, hence solution is not optimal (augment by 1).

1.1b

e.g.

	J	K	L	M	N
A	1	2	0	1	2
B	2	0	2	0	0
C	0	0	84	0	1
D	4	86	0	0	2
E	0	1	2	0	2

1.1b

5 lines required to cover zeros, hence solution is optimal.

dB1

2.4

Maximum profit is £161

2.2a

(7)

(9 marks)

Notes

b1B1: Mark awarded when both steps complete (subtraction, replace blank cells with values > 41).

b2B1: Correct statement regarding row and column reduction. (If given in detail:
Reduce row A by 10, reduce row B by 23,
reduce row C by 17, reduce row D by 9,
reduce row E by 18. No reduction in column J,
reduce column K by 3. No reduction in column L,
reduce column M by 2, reduce column N by 4.)

b1M1: Simplifying the initial matrix by reducing rows and then columns (condone one slip/error)

b2M1: 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.

b3M1: 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 (so getting optimal table).

b3dB1: Correct statement regarding the minimum number of lines to cover zeros. (dependent on previous M mark)

b1A1: CSO on final table (so must have all previous marks in this part) + deduction of the correct total profit.

Special Case: Minimisation Max a) B1 B0 b) B0 B1 M1 M0 M1 B1 A0 5/9

	J	K	L	M	N
A	38	33	40	35	32
B	26	24	27	25	23
C	33	29	100	30	27
D	36	100	41	37	33
E	32	27	31	29	25

	J	K	L	M
A	6	1	8	3
B	3	1	4	2
C	6	2	73	3
D	3	67	8	4
E	7	2	6	4

e.g. (shaded in the printed scheme: columns J, K and N and row B)

	J	K	L	M
A	3	0	4	1
B	0	0	0	0
C	3	1	69	1
D	0	66	4	2
E	4	1	2	2

e.g.

	J	K	L	M	N
A	3	0	3	0	0
B	1	1	0	0	1
C	3	1	68	0	0
D	0	66	3	1	0
E	4	1	1	1	0