Allocation

Topic

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)

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

A2 June 2024 Q4

EdexcelCurrent spec9 marksAllocation

4. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S.

Each task must be assigned to just one worker and each worker can do only one task.

Worker B cannot be assigned to task Q and worker D cannot be assigned to task R.

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

	P	Q	R	S
A	65	72	69	75
B	71	–	68	65
C	70	69	73	77
D	73	70	–	71

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

(a)

(i) Explain how to modify the table so that the Hungarian algorithm could be applied.

(ii) Modify the table as described in (a)(i). (3)

(b) Formulate the above situation as a linear programming problem. You must define the decision variables and make the objective function and constraints clear. (6)

Mark scheme (a)

Scheme	Marks	AO
(i) Subtracting each entry from a constant value e.g. \(\geqslant 77\) to convert from maximisation problem to minimisation	B1	3.5c
Add a sufficiently large number (\(> 12\)) to cells BQ and DR	B1	1.1b
(ii) e.g. \(\begin{bmatrix} 12 & 5 & 8 & 2 \\ 6 & 100 & 9 & 12 \\ 7 & 8 & 4 & 0 \\ 4 & 7 & 100 & 6 \end{bmatrix}\)	B1	1.1b
	(3)

Notes

B1: correct reasoning for how to convert from maximisation to minimisation

B1: adding a large number (at least 13) to cells BQ and DR

B1: CAO

Mark scheme (b)

Scheme	Marks	AO
Let \(x_{ij}\) be 0 or 1 \(\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}\)	B1	3.3
where \(i \in \{\text{A, B, C, D}\}\) and \(j \in \{\text{P, Q, R, S}\}\)	B1	2.5
minimise \(12x_{\text{AP}} + 5x_{\text{AQ}} + 8x_{\text{AR}} + 2x_{\text{AS}} + 6x_{\text{BP}} + \text{‘100’}x_{\text{BQ}} + 9x_{\text{BR}} + 12x_{\text{BS}}\) \(\quad + 7x_{\text{CP}} + 8x_{\text{CQ}} + 4x_{\text{CR}} + 4x_{\text{DP}} + 7x_{\text{DQ}} + \text{‘100’}x_{\text{DR}} + 6x_{\text{DS}}\)	M1 A1	3.3 1.1b
Subject to \(\sum x_{\text{A}j} = 1,\ \sum x_{\text{B}j} = 1,\ \sum x_{\text{C}j} = 1,\ \sum x_{\text{D}j} = 1\) \(\sum x_{i\text{P}} = 1,\ \sum x_{i\text{Q}} = 1,\ \sum x_{i\text{R}} = 1,\ \sum x_{i\text{S}} = 1\)	M1 A1	3.3 1.1b
	(6)
	(9 marks)

Notes

B1: defining \(x_{ij}\) correctly

B1: correct definition of the values that \(i\) and \(j\) can take

M1: Attempt at a 15 (or 16) term expression in terms of \(x\) (or their defined variable), coefficients ‘correct’, 2 ‘large’ values included, condone 2 slips. If more than 2 errors in (a) ft exactly their table for this mark only.

A1: CAO including ‘minimise’ (or equivalent 14 term expression with ‘maximise’)

M1: At least four equations, each in three or four variables, unit coefficients, equal to 1 Do not accept inequalities

A1: CAO (all eight equations)

Maximise \(65x_{AP} + 72x_{AQ} + 69x_{AR} + 75x_{AS}\)
\(\qquad + 71x_{BP} + 68x_{BR} + 65x_{BS}\)
\(\qquad + 70x_{CP} + 69x_{CQ} + 73x_{CR} + 77x_{CS}\)
\(\qquad + 73x_{DP} + 70x_{DQ} + 71x_{DS}\)

Note: if maximising they must not include a large number for BQ and DR, so only 14 terms

AS June 2024 Q2

EdexcelCurrent spec8 marksAllocation

2. A team of 5 players, A, B, C, D and E, competes in a quiz. Each player must answer one of 5 rounds, P, Q, R, S and T.

Each player must be assigned to exactly one round, and each round must be answered by exactly one player.

Player B cannot answer round Q, player D cannot answer round T, and player E cannot answer round R.

The number of points that each player is expected to earn in each round is shown in the table.

	P	Q	R	S	T
A	32	40	35	41	37
B	38	–	40	27	33
C	41	28	37	36	35
D	35	33	38	36	–
E	40	38	–	39	34

The team wants to maximise its total expected score.

The Hungarian algorithm is to be used to find the maximum total expected score that can be earned by the 5 players.

(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 expected score.

(ii) Calculate the maximum total expected score. (6)

Mark scheme (a)

Scheme	Marks	AO
Subtract each entry from a constant (e.g. 50) to convert from maximisation problem to minimisation	B1	1.1b
Add a large value (e.g. 100) to cells BQ, DT and ER so that they cannot be selected	B1	2.4
	(2)

Notes

B1: Valid statement regarding converting a maximisation problem to a minimisation problem

B1: Explain the need to add a large value to avoid cells being selected – it must be clear which order the changes are applied

	P	Q	R	S	T
A	9	1	6	0	4
B	3	100	1	14	8
C	0	13	4	5	6
D	6	8	3	5	100
E	1	3	100	2	7

A2 June 2023 Q4

EdexcelCurrent spec8 marksAllocation

4. Four students, A, B, C and D, are to be allocated to four rounds, 1, 2, 3 and 4, in a competition. Each student is to take part in exactly one round and no two students may play in the same round.

Each student has been given an estimated score for each round. The estimated scores for each student are shown in the table below.

	1	2	3	4
A	34	20	18	15
B	49	31	12	34
C	48	27	23	26
D	52	45	42	42

(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total estimated score. You must make your method clear and show the table after each stage. (7)

(b) Find this total estimated score. (1)

Mark scheme (a)

Scheme	Marks	AO
Since maximising, subtract all elements from some value \(\geqslant 52\) e.g. \(\begin{bmatrix} 18 & 32 & 34 & 37 \\ 3 & 21 & 40 & 18 \\ 4 & 25 & 29 & 26 \\ 0 & 7 & 10 & 10 \end{bmatrix}\)	B1	1.1b
Reduce rows \(\begin{bmatrix} 0 & 14 & 16 & 19 \\ 0 & 18 & 37 & 15 \\ 0 & 21 & 25 & 22 \\ 0 & 7 & 10 & 10 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 7 & 6 & 9 \\ 0 & 11 & 27 & 5 \\ 0 & 14 & 15 & 12 \\ 0 & 0 & 0 & 0 \end{bmatrix}\)	M1 A1	2.1 1.1b
\(\begin{bmatrix} 0 & 2 & 1 & 4 \\ 0 & 6 & 22 & 0 \\ 0 & 9 & 10 & 7 \\ 5 & 0 & 0 & 0 \end{bmatrix}\) followed by \(\begin{bmatrix} 0 & 1 & 0 & 3 \\ 1 & 6 & 22 & 0 \\ 0 & 8 & 9 & 6 \\ 6 & 0 & 0 & 0 \end{bmatrix}\) or \(\begin{bmatrix} 0 & 1 & 0 & 4 \\ 0 & 5 & 21 & 0 \\ 0 & 8 & 9 & 7 \\ 6 & 0 & 0 & 1 \end{bmatrix}\)	M1 A1ft A1	2.1 1.1b 1.1b
Optimal allocation is A = 3, B = 4, C = 1, D = 2	A1ft	2.2a
	(7)

Notes

B1: converting correctly from a minimisation to maximisation

M1: simplifying the initial matrix by reducing rows and then columns (allow up to 2 independent slips)

A1: CAO

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 (lines may be implied). If lines are drawn they must be correct.

A1ft: CAO following on from row and column reduction from previous table (f/t from previous table with no further slips)

A1: CSO on final table (so must have scored all previous marks)

A1ft: correct allocation ft their optimal table (both previous M marks must have been awarded in (a)) (Must be fully written. Do not accept just indicated on zeroes on final matrix)

Special Case – minimisation – max 4/8

Scheme	Marks	AO
Special Case – minimisation – max 4/8	B0
Reduce rows \(\begin{bmatrix} 19 & 5 & 3 & 0 \\ 37 & 19 & 0 & 22 \\ 25 & 4 & 0 & 3 \\ 10 & 3 & 0 & 0 \end{bmatrix}\) and then columns \(\begin{bmatrix} 9 & 2 & 3 & 0 \\ 27 & 16 & 0 & 22 \\ 15 & 1 & 0 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix}\)	M1 A1
followed by \(\begin{bmatrix} 8 & 1 & 3 & 0 \\ 26 & 15 & 0 & 22 \\ 14 & 0 & 0 & 3 \\ 0 & 0 & 1 & 1 \end{bmatrix}\) or \(\begin{bmatrix} 9 & 2 & 4 & 0 \\ 26 & 15 & 0 & 21 \\ 14 & 0 & 0 & 2 \\ 0 & 0 & 1 & 0 \end{bmatrix}\)	M1 A1 A0
Optimal allocation is	A0
	(7)
(b) Total score	B0
	(1)
	(8 marks)

B0: no conversion

M1: simplifying the initial matrix by reducing rows and then columns (allow up to 2 independent slips)

A1: CAO

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 (lines may be implied). If lines are drawn they must be correct.

A1: CAO No further marks awarded

Scheme	Marks	AO
Total score = 18 + 34 + 48 + 45 = 145	B1	2.2a
	(1)
	(8 marks)

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)

A2 June 2022 Q1

EdexcelCurrent spec6 marksAllocation

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each task must be assigned to just one worker and each worker must do only one task.

The cost of assigning each worker to each task is shown in the table below.

The total cost is to be minimised.

	1	2	3	4
A	32	45	34	48
B	37	39	50	46
C	46	44	40	42
D	43	45	48	52

(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total cost. You must make your method clear and show the table after each stage. (5)

(b) State the minimum total cost. (1)

Mark scheme (a)

Scheme	Marks	AO
Reduce rows \(\begin{bmatrix} 0 & 13 & 2 & 16 \\ 0 & 2 & 13 & 9 \\ 6 & 4 & 0 & 2 \\ 0 & 2 & 5 & 9 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 11 & 2 & 14 \\ 0 & 0 & 13 & 7 \\ 6 & 2 & 0 & 0 \\ 0 & 0 & 5 & 7 \end{bmatrix}\)	M1 A1	2.1 1.1b
Followed by \(\begin{bmatrix} 0 & 11 & 0 & 12 \\ 0 & 0 & 11 & 5 \\ 8 & 4 & 0 & 0 \\ 0 & 0 & 3 & 5 \end{bmatrix}\)	M1 A1ft	2.1 1.1b
A – 3, B – 1, C – 4, D – 2 or A – 3, B – 2, C – 4, D – 1	A1ft	2.2a
	(5)

Notes

M1: simplifying the initial matrix by reducing rows and then columns. (Allow up to 2 independent slips).

A1: CAO

A1ft: CAO following on from row and column reduction final table. (f/t from previous table with no further slips).

A1ft: correct allocation ft their optimal table (both previous M marks must have been awarded in (a)) (Must be fully written. Do not accept just indicated on zeros on final matrix).

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

A2 October 2021 Q1

EdexcelCurrent spec6 marksAllocation

1. Four workers, A, B, C and D, are to be assigned to three tasks, 1, 2 and 3. Each task must be assigned to just one worker and each worker can do one task only.

Worker A cannot do task 2 and worker D cannot do task 3

The cost of assigning each worker to each task is shown in the table below.

The total cost is to be minimised.

	1	2	3
A	53	–	62
B	48	57	59
C	55	63	58
D	69	49	–

Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. (6)

Mark scheme

Scheme	Marks	AO
Let \(x_{ij}\) be 0 or 1 \(\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}\)	B1	3.3
where \(i \in \{\text{A, B, C, D}\}\) and \(j \in \{1, 2, 3, 4\}\)	B1	2.5
minimise \(C = 53x_{\text{A1}} + \text{‘100’}x_{\text{A2}} + 62x_{\text{A3}} + 48x_{\text{B1}} + 57x_{\text{B2}} + 59x_{\text{B3}}\) \(\qquad + 55x_{\text{C1}} + 63x_{\text{C2}} + 58x_{\text{C3}} + 69x_{\text{D1}} + 49x_{\text{D2}} + \text{‘100’}x_{\text{D3}}\)	M1 A1	3.3 1.1b
Subject to \(\sum x_{\text{A}j} = 1,\ \sum x_{\text{B}j} = 1,\ \sum x_{\text{C}j} = 1,\ \sum x_{\text{D}j} = 1\) \(\sum x_{i1} = 1,\ \sum x_{i2} = 1,\ \sum x_{i3} = 1,\ \sum x_{i4} = 1\)	M1 A1	3.3 1.1b
	(6)
	(6 marks)

Notes

B1: Defining \(x_{ij}\) correctly

B1: Correct definition of the values that \(i\) and \(j\) can take

M1: Attempt at 12 term expression, coefficients ‘correct’, 2 ‘large’ values included, condone 2 slips.

A1: cao including ‘minimise’

M1: At least four correct equations, each in three or four variables, unit coefficients, equal to 1

A1: cao (all eight equations)

No dummy column can score a maximum of B1B0M1A1M0A0
No ‘large’ values in A2 and D3 can score a maximum B1B1M0A0M1A1
No ‘large’ values or dummy column can score a maximum of B1B0M0A0M0A0

AS October 2020 Q2

EdexcelCurrent spec9 marksAllocation

2. 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.

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

	P	Q	R	S
A	72	98	59	84
B	67	87	68	86
C	70	–	62	79
D	78	93	64	81

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

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

(b) Modify the table so that the Hungarian algorithm may be applied. (1)

(c) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You should explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage. (6)

Mark scheme (a)

Scheme	Marks	AO
Subtract each entry from a constant (e.g. 98) to convert from maximisation problem to minimisation	B1	1.1a
Add an appropriate large value to cell CQ (e.g. twice the largest value) to make CQ unattractive	B1	3.5c
	(2)

Notes

B1: Valid statement regarding converting a maximisation problem to a minimisation problem

B1: Explain the need to add an unattractive value to cell CQ

(note that candidates may first assign a negative value to the CQ entry and then subtract)

Mark scheme (c)

Scheme

Marks

No reduction for row A, reduce row B by 11, reduce row C by 19 and row D by 5 (or equivalent). Reduce column P by 9 and column R by 17, no reduction in columns Q and S.

2.4

Reducing rows and columns gives

	P	Q	R	S
A	26	0	39	14
B	20	0	19	1
C	9	59	17	0
D	15	0	29	12

followed by

	P	Q	R	S
A	17	0	22	14
B	11	0	2	1
C	0	59	0	0
D	6	0	12	12

1.1b

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

	P	Q	R	S
A	16	0	21	13
B	10	0	1	0
C	0	60	0	0
D	5	0	11	11

1.1b

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

e.g.

	P	Q	R	S
A	11	0	16	8
B	10	5	1	0
C	0	65	0	0
D	0	0	6	6

1.1b

Four lines required to cover the zeros hence solution is optimal

2.4

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

2.2a

(6)

(9 marks)

Notes

B1: Correct statements regarding row and column reduction

M1: Simplifying the initial matrix by reducing rows and then columns

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 statements regarding the minimum number of lines to cover zeros

A1: CSO on final table (so must have scored all previous M (but not necessarily the B) marks in this part) + deduction of the correct allocation

A2 October 2020 Q1

EdexcelCurrent spec8 marksAllocation

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to exactly one task and each task must be done by exactly one worker.

Worker A cannot do task 3 and worker B cannot do task 4

The table below shows the profit, in pounds, that each worker would earn if assigned to each of the tasks.

	1	2	3	4
A	29	20	–	23
B	32	30	28	–
C	35	32	34	25
D	29	31	27	30

(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage. (7)

(b) Determine the resulting total profit. (1)

Mark scheme (a)

Scheme	Marks	AO
Subtracting each entry from a constant value \(\geqslant 35\) to convert from maximisation problem to minimisation	M1	1.1b
Add a sufficiently large number (\(> 15\)) to cells A3 and B4 e.g. \(\begin{bmatrix} 6 & 15 & 100 & 12 \\ 3 & 5 & 7 & 100 \\ 0 & 3 & 1 & 10 \\ 6 & 4 & 8 & 5 \end{bmatrix}\)	B1	1.1b
Reduce rows \(\begin{bmatrix} 0 & 9 & 94 & 6 \\ 0 & 2 & 4 & 97 \\ 0 & 3 & 1 & 10 \\ 2 & 0 & 4 & 1 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 9 & 93 & 5 \\ 0 & 2 & 3 & 96 \\ 0 & 3 & 0 & 9 \\ 2 & 0 & 3 & 0 \end{bmatrix}\)	M1 A1ft	2.1 1.1b
followed by \(\begin{bmatrix} 0 & 7 & 93 & 3 \\ 0 & 0 & 3 & 94 \\ 0 & 1 & 0 & 7 \\ 4 & 0 & 5 & 0 \end{bmatrix}\) or \(\begin{bmatrix} 0 & 7 & 91 & 3 \\ 0 & 0 & 1 & 94 \\ 2 & 3 & 0 & 9 \\ 4 & 0 & 3 & 0 \end{bmatrix}\)	M1 A1ft	2.1 1.1b
A – 1, B – 2, C – 3, D – 4	B1ft	1.1b
	(7)

Notes

M1: convert from maximisation to minimisation (allow at most two errors)

B1: adding a large number (at least 16) to cells A3 and B4

M1: simplifying the initial matrix by reducing rows and then columns

A1ft: cao following on from their earlier subtraction

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

A1ft: cao following on from row and column reduction final table

(b) B1ft: correct allocation ft their optimal table (all previous M marks must have been awarded in (a))

A2 June 2019 Q2

EdexcelCurrent spec7 marksAllocation

2. Four workers, Ted (T), Harold (H), James (J) and Margaret (M), are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised.

	1	2	3	4
T	103	97	74	80
H	201	155	145	155
J	111	80	77	92
M	203	188	137	184

(a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage. (6)

(b) Determine the resulting total profit. (1)

Mark scheme (a)

Scheme	Marks	AO
Subtracting each entry from a value \(\geqslant 203\) e.g. \(\begin{bmatrix} 100 & 106 & 129 & 123 \\ 2 & 48 & 58 & 48 \\ 92 & 123 & 126 & 111 \\ 0 & 15 & 66 & 19 \end{bmatrix}\)	1B1	1.1b
Reduce rows \(\begin{bmatrix} 0 & 6 & 29 & 23 \\ 0 & 46 & 56 & 46 \\ 0 & 31 & 34 & 19 \\ 0 & 15 & 66 & 19 \end{bmatrix}\) and then columns \(\begin{bmatrix} 0 & 0 & 0 & 4 \\ 0 & 40 & 27 & 27 \\ 0 & 25 & 5 & 0 \\ 0 & 9 & 37 & 0 \end{bmatrix}\)	1M1 1A1ft	2.1 1.1b
followed by \(\begin{bmatrix} 5 & 0 & 0 & 9 \\ 0 & 35 & 22 & 27 \\ 0 & 20 & 0 & 0 \\ 0 & 4 & 32 & 0 \end{bmatrix}\)	2M1 2A1ft	2.1 1.1b
T – 2, H – 1, J – 3, M – 4	3A1	2.2a
	(6)

Notes

1B1: CAO

1M1: simplifying the initial matrix by reducing rows and then columns. Allow no more than a single error in row reduction together with no more than a single error in column reduction. May combine the two stages of converting from maximum to a minimum problem and row reduction which is acceptable.

1A1ft: CAO following on from their earlier conversion to maximising. If 1B1 awarded, the result of row and column reduction must be as in the main scheme. If 1B0 awarded, then row and column reduction must ft correctly from their attempt to convert to maximisation problem.

2M1: develops 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

2A1ft: Improved solution following on from their previous table

3A1: CSO Correct allocation. Must have gained all previous marks in the question.

SC: Minimising

After row reduction \(\begin{bmatrix} 29 & 23 & 0 & 6 \\ 56 & 10 & 0 & 10 \\ 34 & 3 & 0 & 15 \\ 66 & 51 & 0 & 47 \end{bmatrix}\) and then after column reduction \(\begin{bmatrix} 0 & 20 & 0 & 0 \\ 27 & 7 & 0 & 4 \\ 5 & 0 & 0 & 9 \\ 37 & 48 & 0 & 41 \end{bmatrix}\)

After augmentation \(\begin{bmatrix} 0 & 20 & 4 & 0 \\ 23 & 3 & 0 & 0 \\ 5 & 0 & 4 & 9 \\ 33 & 44 & 0 & 37 \end{bmatrix}\) or \(\begin{bmatrix} 0 & 24 & 4 & 0 \\ 23 & 7 & 0 & 0 \\ 1 & 0 & 0 & 5 \\ 33 & 48 & 0 & 37 \end{bmatrix}\)

Scores B0 M1A0 M1A1(ft)A0 B0 (So 3 marks max)

1B0: No Minimisation

1M1: simplifying the initial matrix by reducing rows and then columns – all values ‘correct’

1A0: Must be maximising.

2M1: develops 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

2A1ft: Improved solution following on from their previous table

3A0: CSO

1B0: Must be maximising

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

AS June 2018 Q1

EdexcelCurrent spec5 marksAllocation

1. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker must be assigned to exactly one task and each task must be done by only one worker. The time, in hours, that each worker takes to complete each task is shown in the table below.

	P	Q	R	S
A	7.5	3.5	8	9.5
B	5	2	7	7.5
C	4	3.5	3.5	8
D	6	5	3.5	4

Reducing rows first, use the Hungarian algorithm to obtain an allocation which minimises the total time. You must explain your method and show the table after each stage. (5)