Allocation (assignment) problems and the Hungarian algorithm Decision 2

Papers
A level Paper 4D; AS Paper 2 (option 28)
Level
AS and A level
Spec
D2.2.1, D2.2.2
Booklet
Nothing is given.
Since 2018
29 question parts, 109 marks

Notes, worked examples and practice for this topic are being written by our tutors. The past-paper questions below are ready now: work each one on paper, then open the mark scheme and the examiner's comment.

Past-paper questions

Print this topic as a pack questions first, then the mark schemes

Tap a question to zoom it. Mark scheme and examiner's comment open under each question.
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)
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)
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)
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)
June 2025 · Paper 4D (Decision 2) · Q2(c) 1 mark
(c) Calculate the least total time to complete all four tasks. (1)
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)
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)
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)
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)
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)
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)
June 2023 · AS Paper 2 (Decision 2) · Q1(c) 1 mark
(c) Calculate the least total time to complete all four tasks. (1)
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)
June 2023 · Paper 4D (Decision 2) · Q4(b) 1 mark
(b) Find this total estimated score. (1)
June 2022 · AS Paper 2 (Decision 2) · Q1(a) 1 mark
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)
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)
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)
June 2022 · Paper 4D (Decision 2) · Q1(b) 1 mark
(b) State the minimum total cost. (1)
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)
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)
Oct 2020 · AS Paper 2 (Decision 2) · Q2(b) 1 mark
(b) Modify the table so that the Hungarian algorithm may be applied. (1)
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)
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)
Oct 2020 · Paper 4D (Decision 2) · Q1(b) 1 mark
(b) Determine the resulting total profit. (1)
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)
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)
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)
June 2019 · Paper 4D (Decision 2) · Q2(b) 1 mark
(b) Determine the resulting total profit. (1)
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.

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.