: Edexcel past-paper questions pack
Back to the topic page

Allocation (assignment) problems and the Hungarian algorithm

Past-paper questions pack

Name
Class
Date set
Date due
Score/ 109

Questions are numbered; the mark schemes (the answer key) follow on separate pages so the question pages can be handed out alone. www.alevelfurthermathstutor.com

Edexcel AS and A-level Further Maths past-paper questions since June 2018 · 29 parts, 109 marks · mark schemes follow the questions · www.alevelfurthermathstutor.com · Questions and mark schemes © Pearson Education Ltd

1. June 2025 · AS Paper 2 (Decision 2) · Q1(a) · 2 marks
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 B C – – E 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)
2. June 2025 · AS Paper 2 (Decision 2) · Q1(b) · 7 marks
(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)
3. June 2025 · Paper 4D (Decision 2) · Q2(a) · 2 marks
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 B – C E 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)
4. June 2025 · Paper 4D (Decision 2) · Q2(b) · 6 marks
(b) Use the Hungarian algorithm to obtain an allocation that minimises the total time. (6)
5. June 2025 · Paper 4D (Decision 2) · Q2(c) · 1 marks
(c) Calculate the least total time to complete all four tasks. (1)
6. June 2024 · AS Paper 2 (Decision 2) · Q2(a) · 2 marks
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 B – C – E – 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)
7. June 2024 · AS Paper 2 (Decision 2) · Q2(b) · 6 marks
(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)
8. June 2024 · Paper 4D (Decision 2) · Q4(a) · 3 marks
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 B – C – 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)
9. June 2024 · Paper 4D (Decision 2) · Q4(b) · 6 marks
(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)
10. June 2023 · AS Paper 2 (Decision 2) · Q1(a) · 2 marks
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 B – C E – 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)
11. June 2023 · AS Paper 2 (Decision 2) · Q1(b) · 6 marks
(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)
12. June 2023 · AS Paper 2 (Decision 2) · Q1(c) · 1 marks
(c) Calculate the least total time to complete all four tasks. (1)
13. June 2023 · Paper 4D (Decision 2) · Q4(a) · 7 marks
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. A B C (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)
14. June 2023 · Paper 4D (Decision 2) · Q4(b) · 1 marks
(b) Find this total estimated score. (1)
15. June 2022 · AS Paper 2 (Decision 2) · Q1(a) · 1 marks
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 B C – – 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)
16. June 2022 · AS Paper 2 (Decision 2) · Q1(b) · 6 marks
(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)
17. June 2022 · Paper 4D (Decision 2) · Q1(a) · 5 marks
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. A B C (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)
18. June 2022 · Paper 4D (Decision 2) · Q1(b) · 1 marks
(b) State the minimum total cost. (1)
19. Nov 2021 · Paper 4D (Decision 2) · Q1 · 6 marks
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. A – B C – Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. (6)
20. Oct 2020 · AS Paper 2 (Decision 2) · Q2(a) · 2 marks
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 B C – 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)
21. Oct 2020 · AS Paper 2 (Decision 2) · Q2(b) · 1 marks
(b) Modify the table so that the Hungarian algorithm may be applied. (1)
22. Oct 2020 · AS Paper 2 (Decision 2) · Q2(c) · 6 marks
(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)
23. Oct 2020 · Paper 4D (Decision 2) · Q1(a) · 7 marks
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. A – B – C (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)
24. Oct 2020 · Paper 4D (Decision 2) · Q1(b) · 1 marks
(b) Determine the resulting total profit. (1)
25. June 2019 · AS Paper 2 (Decision 2) · Q1(a) · 2 marks
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 B C 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)
26. June 2019 · AS Paper 2 (Decision 2) · Q1(b) · 7 marks
(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)
27. June 2019 · Paper 4D (Decision 2) · Q2(a) · 6 marks
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. T H J M (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)
28. June 2019 · Paper 4D (Decision 2) · Q2(b) · 1 marks
(b) Determine the resulting total profit. (1)
29. June 2018 · AS Paper 2 (Decision 2) · Q1 · 5 marks
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 9.5 B 7.5 C 3.5 3.5 3.5 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.

Mark schemes

Each mark scheme shows the whole question; the parts on this topic are the ones listed above.

June 2025 · AS Paper 2 (Decision 2) · Q1
Mark scheme June 2025 Paper 2 (Decision 2) Q1(b)
June 2025 · Paper 4D (Decision 2) · Q2
Mark scheme June 2025 Paper 4D (Decision 2) Q2(c)
June 2024 · AS Paper 2 (Decision 2) · Q2
Mark scheme June 2024 Paper 2 (Decision 2) Q2(b)
June 2024 · Paper 4D (Decision 2) · Q4
Mark scheme June 2024 Paper 4D (Decision 2) Q4(b)
June 2023 · AS Paper 2 (Decision 2) · Q1
Mark scheme June 2023 Paper 2 (Decision 2) Q1(c)
June 2023 · Paper 4D (Decision 2) · Q4
Mark scheme June 2023 Paper 4D (Decision 2) Q4(b)
June 2022 · AS Paper 2 (Decision 2) · Q1
Mark scheme June 2022 Paper 2 (Decision 2) Q1(b)
June 2022 · Paper 4D (Decision 2) · Q1
Mark scheme June 2022 Paper 4D (Decision 2) Q1(b)
Nov 2021 · Paper 4D (Decision 2) · Q1
Mark scheme Nov 2021 Paper 4D (Decision 2) Q1
Oct 2020 · AS Paper 2 (Decision 2) · Q2
Mark scheme Oct 2020 Paper 2 (Decision 2) Q2(c)
Oct 2020 · Paper 4D (Decision 2) · Q1
Mark scheme Oct 2020 Paper 4D (Decision 2) Q1(b)
June 2019 · AS Paper 2 (Decision 2) · Q1
Mark scheme June 2019 Paper 2 (Decision 2) Q1(b)
June 2019 · Paper 4D (Decision 2) · Q2
Mark scheme June 2019 Paper 4D (Decision 2) Q2(b)
June 2018 · AS Paper 2 (Decision 2) · Q1
Mark scheme June 2018 Paper 2 (Decision 2) Q1