D2.2.1 Cost matrix reduction. Students should reduce rows first. Use of…
Section
D2.2 Allocation (assignment) problems
Level
AS & A level
Statement
Cost matrix reduction. Students should reduce rows first. Use of the Hungarian algorithm to find a least cost allocation. Modification of the Hungarian algorithm to deal with a maximum profit allocation.
Guidance
Ideas of a dummy location is required. The adaption of the algorithm to manage incomplete data is required. Students should subtract all the values (in the original matrix) from the largest value (in the original matrix).
June 2025 · AS Paper 2 (Decision 2) · Q1(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
While most learners attempted the explanation required for part (a) of this question, many of the responses were confused and lacking in detail. Learners were also unsure of the order needed to deal with the two modifications required, with some placing large values in the prohibited cells before subtracting all values from the largest in the table. However, most learners were able to carry out the necessary steps and produced a correctly modified table. Most learners then correctly reduced rows and columns, although some failed to add the necessary comment to explain what they were doing. Most learners then applied the algorithm correctly, although a small number used too many lines to cover zeroes (4 instead of 3 or 5 instead of 4) or made errors in their working. A few learners attempted this as a minimise problem instead of maximising. Some learners failed to explain how they knew whether the table was optimal and some failed to state the maximum total profit.
Key points from the mark scheme and examiner's report
first subtract every entry from a constant (e.g. 50), then put a large value (e.g. 100) in the two blank cells CL and DK
the order matters (reversed scores B1 B0)
explanations were often confused
June 2025 · AS Paper 2 (Decision 2) · Q1(b)7 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
While most learners attempted the explanation required for part (a) of this question, many of the responses were confused and lacking in detail. Learners were also unsure of the order needed to deal with the two modifications required, with some placing large values in the prohibited cells before subtracting all values from the largest in the table. However, most learners were able to carry out the necessary steps and produced a correctly modified table. Most learners then correctly reduced rows and columns, although some failed to add the necessary comment to explain what they were doing. Most learners then applied the algorithm correctly, although a small number used too many lines to cover zeroes (4 instead of 3 or 5 instead of 4) or made errors in their working. A few learners attempted this as a minimise problem instead of maximising. Some learners failed to explain how they knew whether the table was optimal and some failed to state the maximum total profit.
Key points from the mark scheme and examiner's report
rows reduced by 10, 23, 17, 9, 18 then columns K by 3, M by 2, N by 4
3 lines, augment by 1
4 lines, augment by 1
5 lines so optimal
maximum profit £161
must explain reductions and the line test
minimising instead scores at most 5
June 2025 · Paper 4D (Decision 2) · Q2(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Most candidates were able to state the two modifications required in part (a) of this question and then carried these out at the start of part (b). Most candidates used a column of zeroes for
Key points from the mark scheme and examiner's report
add a dummy column (e.g. all 0) to make the table square, and a large number (over 43, e.g. 100) in the forbidden cell BR
June 2025 · Paper 4D (Decision 2) · Q2(b)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
and then carried these out at the start of part (b). Most candidates used a column of zeroes for their dummy, but some, instead, used a large number (e.g. 100) in their dummy. Those who opted for the latter were rewarded, as reducing rows and columns then gave the optimum solution directly. Those candidates using zeroes in their dummy, reduced columns and then applied the algorithm once to go from three lines to four lines. At this stage, there were then several possible ways to cover the zeroes and the choice of this, either lead directly to the optimum solution, or required additional iterations of the algorithm to reach this. Candidates should be aware that the most efficient choice of lines leaves the largest possible element to be subtracted for the next iteration. Most candidates who achieved an optimum solution, did so without errors and then stated the allocation and minimum time.
Key points from the mark scheme and examiner's report
rows reduce to zero with a 0 dummy so reduce columns
3 lines to 4 to 5 (two augmentations)
A–P, B–S, C–R, D–Q, E does no task
choosing lines that leave the largest uncovered element is most efficient
a large dummy value gives the optimum directly
June 2025 · Paper 4D (Decision 2) · Q2(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Most candidates were able to state the two modifications required in part (a) of this question and then carried these out at the start of part (b). Most candidates used a column of zeroes for their dummy, but some, instead, used a large number (e.g. 100) in their dummy. Those who opted for the latter were rewarded, as reducing rows and columns then gave the optimum solution directly. Those candidates using zeroes in their dummy, reduced columns and then applied the algorithm once to go from three lines to four lines. At this stage, there were then several possible ways to cover the zeroes and the choice of this, either lead directly to the optimum solution, or required additional iterations of the algorithm to reach this. Candidates should be aware that the most efficient choice of lines leaves the largest possible element to be subtracted for the next iteration. Most candidates who achieved an optimum solution, did so without errors and then stated the allocation and minimum time.
Key points from the mark scheme and examiner's report
least total time 133 minutes
June 2024 · AS Paper 2 (Decision 2) · Q2(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
While most candidates attempted the explanation required for part (a) of this question, many of the responses were confused and lacking in detail. Candidates were also unsure of the order needed to deal with the two modifications required, with some placing large values in the prohibited cells before subtracting all values from the largest in the table. However, most candidates were able to carry out the necessary steps and produced a correctly modified table. Most candidates then correctly reduced rows and columns and applied the algorithm correctly. A relatively small number of candidates made errors in their working or failed to use the correct number of lines to cover all the zeroes in the table. A few candidates attempted this as a minimise problem instead of maximising. A small number failed to state the correct allocation, even though they had the correct final table. Almost all candidates who had the correct table stated the score correctly.
Key points from the mark scheme and examiner's report
subtract every entry from a constant (e.g. 50) to convert to minimising, then put a large value (e.g. 100) in BQ, DT and ER so they cannot be chosen
the order of the two steps must be clear
explanations often confused
June 2024 · AS Paper 2 (Decision 2) · Q2(b)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
While most candidates attempted the explanation required for part (a) of this question, many of the responses were confused and lacking in detail. Candidates were also unsure of the order needed to deal with the two modifications required, with some placing large values in the prohibited cells before subtracting all values from the largest in the table. However, most candidates were able to carry out the necessary steps and produced a correctly modified table. Most candidates then correctly reduced rows and columns and applied the algorithm correctly. A relatively small number of candidates made errors in their working or failed to use the correct number of lines to cover all the zeroes in the table. A few candidates attempted this as a minimise problem instead of maximising. A small number failed to state the correct allocation, even though they had the correct final table. Almost all candidates who had the correct table stated the score correctly.
Key points from the mark scheme and examiner's report
5 × 5 reduced by rows then columns
3 lines, augment by 1
4 lines, augment by 1
5 lines so optimal
A–T, B–R, C–P, D–S, E–Q, maximum score 192
a few minimised instead of maximising
June 2024 · Paper 4D (Decision 2) · Q4(a)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (a), a significant number of candidates failed to state the correct two modifications in the correct order and were penalised. However, many candidates then correctly modified the table. In part (b) most candidates used the correct notation, but a significant number omitted
Key points from the mark scheme and examiner's report
subtract every entry from 77 (the largest value) to convert to minimisation, and put a large number (over 12) in the forbidden cells BQ and DR
both modifications needed
June 2023 · AS Paper 2 (Decision 2) · Q1(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Many candidates scored very well on this question. Almost all could explain how to modify the table correctly in part (a) by saying that an additional dummy column of equal values was required to create a square array, and that a suitable large value needed to be entered into cells BQ and ES. When marks were lost in this first part it was usually down to being imprecise with language or detail (e.g. ‘add a dummy row of equal values’, or ‘add equal values to cells BQ and ES’).
Key points from the mark scheme and examiner's report
add a dummy COLUMN of equal values (e.g. 0) to make the array square
put a large value (> 44, e.g. 100) in cells BQ and ES
'dummy row' or 'add equal values to BQ and ES' lost marks
June 2023 · AS Paper 2 (Decision 2) · Q1(b)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Many candidates scored very well on this question. Almost all could explain how to modify the In part (b), most candidates correctly carried out the corresponding row and column reductions. Accuracy errors at this stage were rare. Most candidates then recognised that three lines were needed to cover the zeros and were well versed in developing an improved solution twice to arrive at the optimal table. Many candidates though failed to clearly explain how they determined, at each stage, whether their solution was optimal. It is essential that candidates refer to the number of lines covering zeros and make it clear the number of such lines that are needed for optimality. However, candidates had no difficulty deducing the optimal allocation and the least total time to complete all four tasks in part (c).
Key points from the mark scheme and examiner's report
5 × 5 array
reducing columns gives 3 lines, augment to 4 then 5 lines so optimal
A–Q, B–R, D–S, E–P, C does no task
must state the number of lines with 'zeros' and 'optimal' at each stage, often omitted
June 2023 · AS Paper 2 (Decision 2) · Q1(c)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Many candidates scored very well on this question. Almost all could explain how to modify the least total time to complete all four tasks in part (c).
Key points from the mark scheme and examiner's report
39 + 39 + 38 + 36 = 152 minutes from the original table
June 2023 · Paper 4D (Decision 2) · Q4(a)7 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was very accessible. Most candidates recognised that this was a maximisation problem and correctly modified the table by subtracting all values from either 52 or a value greater than 52, although a small number simply treated this as a minimisation problem. Most candidates reduced both rows and columns, although a few just reduced rows. Some numerical errors were seen at this stage. Most candidates correctly applied the algorithm twice to go from 2 lines required to three lines and again from three to four lines, again with a small number of arithmetical errors. Most candidates listed the optimum solution, although some just indicated this on their final table and were penalised. Most candidates also stated the correct total score.
Key points from the mark scheme and examiner's report
maximise: subtract all values from 52 (or more), reduce rows then columns
two improvements (2 lines to 3, then 3 to 4)
A3, B4, C1, D2
allocation must be listed, not just marked on the table
June 2023 · Paper 4D (Decision 2) · Q4(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question was very accessible. Most candidates recognised that this was a maximisation problem and correctly modified the table by subtracting all values from either 52 or a value greater than 52, although a small number simply treated this as a minimisation problem. Most candidates reduced both rows and columns, although a few just reduced rows. Some numerical errors were seen at this stage. Most candidates correctly applied the algorithm twice to go from 2 lines required to three lines and again from three to four lines, again with a small number of arithmetical errors. Most candidates listed the optimum solution, although some just indicated this on their final table and were penalised. Most candidates also stated the correct total score.
Key points from the mark scheme and examiner's report
18 + 34 + 48 + 45 = 145
June 2022 · AS Paper 2 (Decision 2) · Q1(a)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Many candidates scored very well on this question. Almost all modified the table correctly in (a) by inserting a large figure in each of the two blank cells; figures ranged from 100 to 1000, though 136 was common. The first mark in (b) proved elusive for many who failed to explain in
Key points from the mark scheme and examiner's report
replace the two blanks (CQ and DS) with a large value, greater than 68 (e.g. 100), so they are never chosen
nearly all did this
June 2022 · AS Paper 2 (Decision 2) · Q1(b)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
though 136 was common. The first mark in (b) proved elusive for many who failed to explain in sufficient numerical detail how the initial row and column reductions were made. However, most candidates did correctly carry out those row and column reductions. Accuracy errors at this stage were rare. Most candidates then recognised that two lines were needed to cover the zeros and were well versed in developing an improved solution twice to arrive at the optimal table. Many candidates though failed to clearly explain how they determined, at each stage, whether their solution was optimal. It is essential that candidates refer to the number of lines covering zeros and make it clear the number of such lines that are needed for optimality. However, candidates had no difficulty deducing the optimal allocation.
Key points from the mark scheme and examiner's report
rows reduced by 48, 51, 52, 63, then columns R by 1 and S by 2
2 lines, augment by 1
3 lines, augment by 1
4 lines so optimal
A–S, B–R, C–P, D–Q
must state the number of lines and use the words 'zeros' and 'optimal' at each stage, which many omitted
June 2022 · Paper 4D (Decision 2) · Q1(a)5 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question proved to be a very accessible, with well over half the candidates earning full marks. Row then column reduction was well done, as was developing an improved solution from three correct zero cover lines to four. A few candidates did fail to cover all the zeros with lines, but otherwise errors were mostly numerical slips. One of the two possible allocations was found by most, with many clearly stating both, though a few candidates lost the mark for failing to distinguish between B’s and D’s allocations. The calculation of the minimum value was almost always correct. A handful of candidates overcomplicated the problem, attempting to maximise the cost rather than minimise it, and consequently lost four marks.
Key points from the mark scheme and examiner's report
reduce rows then columns
3 lines to 4 by adding the smallest uncovered value to double-covered cells
A3, B1, C4, D2 or A3, B2, C4, D1
must distinguish B's and D's allocations
maximising instead loses four marks
June 2022 · Paper 4D (Decision 2) · Q1(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question proved to be a very accessible, with well over half the candidates earning full marks. Row then column reduction was well done, as was developing an improved solution from three correct zero cover lines to four. A few candidates did fail to cover all the zeros with lines, but otherwise errors were mostly numerical slips. One of the two possible allocations was found by most, with many clearly stating both, though a few candidates lost the mark for failing to distinguish between B’s and D’s allocations. The calculation of the minimum value was almost always correct. A handful of candidates overcomplicated the problem, attempting to maximise the cost rather than minimise it, and consequently lost four marks.
Key points from the mark scheme and examiner's report
minimum total cost 158
Nov 2021 · Paper 4D (Decision 2) · Q16 marks
Mark scheme (whole question; this part is marked with the orange bar)
Key points from the mark scheme and examiner's report
add a dummy task 4 (four workers, three tasks) and a large cost (e.g. 100) in A2 and D3
x_ij = 1 if worker i does task j, 0 otherwise, i in {A, B, C, D}, j in {1, 2, 3, 4}
minimise the 12-term cost (dummy column costs 0)
eight constraints, each sum = 1
no dummy column or no large values loses several marks
Oct 2020 · AS Paper 2 (Decision 2) · Q2(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Key points from the mark scheme and examiner's report
subtract every entry from a constant (e.g. 98) to convert to minimising
put a large value in cell CQ (e.g. twice the largest) so it is never chosen
Oct 2020 · AS Paper 2 (Decision 2) · Q2(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Key points from the mark scheme and examiner's report
98 minus each value, CQ given e.g. 78 after subtraction
mark needs both steps
Oct 2020 · AS Paper 2 (Decision 2) · Q2(c)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Key points from the mark scheme and examiner's report
rows reduced by 0, 11, 19, 5 then columns P by 9 and R by 17
2 lines, augment by 1
3 lines, augment by 5
4 lines so optimal
A–Q, B–S, C–R, D–P
reductions and line counts must be explained
Oct 2020 · Paper 4D (Decision 2) · Q1(a)7 marks
Mark scheme (whole question; this part is marked with the orange bar)
Key points from the mark scheme and examiner's report
subtract every entry from 35 (largest value) to convert to minimisation
give the forbidden cells A3 and B4 a large cost (more than 15)
reduce rows then columns, then augment from 3 lines to 4
A1, B2, C3, D4
Oct 2020 · Paper 4D (Decision 2) · Q1(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Key points from the mark scheme and examiner's report
total profit from the original table: £123
June 2019 · AS Paper 2 (Decision 2) · Q1(a)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
and did not adequately explain how the table should be modified in part (a) (by subtracting each entry from a constant and adding a dummy row with equal values) or in part (b) many failed to explain how
Key points from the mark scheme and examiner's report
subtract every entry from a constant (e.g. 42, the largest value) to turn maximising into minimising
add a dummy row of equal values to make the array square
many explanations were inadequate
June 2019 · AS Paper 2 (Decision 2) · Q1(b)7 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
from a constant and adding a dummy row with equal values) or in part (b) many failed to explain how any initial row/column reductions were made and also how to determine if the table was optimal at each stage.
Key points from the mark scheme and examiner's report
reduce rows (A 0, B 1, C 2, dummy 42), no column reduction
2 lines then 3 lines so two augmentations by 1
optimal when 4 lines needed
allocation A–Q, B–S, C–R (dummy–P)
a dummy row of 'infinity' or a non-square array gets only one mark
many failed to explain the reductions and optimality test
June 2019 · Paper 4D (Decision 2) · Q2(a)6 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Candidates were clearly very well prepared for this question and it proved to be a good source of marks for many candidates. A significant proportion were able to produce perfect or near perfect solutions. Candidates who lost marks sometimes did so due to slips in their application of the algorithm however these were not usually too costly due to the follow through marks available. A small proportion failed to convert their initial matrix to a maximisation problem and thus lost a significant number of marks as they had oversimplified the problem. Some candidates did not fully undertake row and column reduction, in some cases prematurely augmenting their tables. Most candidates though subtracted from 203 (or more rarely, numbers greater than 203) and then reduced rows and columns as expected. Augmentation was generally carried out very well. The main way in which candidate lost marks was simply inaccuracy in calculation or due to candidates’ misreading of their own handwriting. Indeed, as already mentioned, candidates’ handwriting was sometimes challenging to read, especially once lines covering zeros had been added onto the tables.
Key points from the mark scheme and examiner's report
maximise: subtract every entry from 203 (largest value) first, then reduce rows then columns
3 lines to 4 lines by augmenting
T2, H1, J3, M4
minimising the original table scores at most 3
June 2019 · Paper 4D (Decision 2) · Q2(b)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Candidates were clearly very well prepared for this question and it proved to be a good source of marks for many candidates. A significant proportion were able to produce perfect or near perfect solutions. Candidates who lost marks sometimes did so due to slips in their application of the algorithm however these were not usually too costly due to the follow through marks available. A small proportion failed to convert their initial matrix to a maximisation problem and thus lost a significant number of marks as they had oversimplified the problem. Some candidates did not fully undertake row and column reduction, in some cases prematurely augmenting their tables. Most candidates though subtracted from 203 (or more rarely, numbers greater than 203) and then reduced rows and columns as expected. Augmentation was generally carried out very well. The main way in which candidate lost marks was simply inaccuracy in calculation or due to candidates’ misreading of their own handwriting. Indeed, as already mentioned, candidates’ handwriting was sometimes challenging to read, especially once lines covering zeros had been added onto the tables.
Key points from the mark scheme and examiner's report
total profit from the original table: £559
June 2018 · AS Paper 2 (Decision 2) · Q15 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This question on applying the Hungarian algorithm to obtain an allocation which minimised the total time proved to be accessible to nearly all students with the majority scoring all 5 marks. When errors were seen these were usually down to numerical slips rather than errors in method as nearly all students correctly applied row and column reduction followed by an augmentation of 2.5. A small number of students failed to deduce the optimal allocation from the location of the zeros in their final table.
Key points from the mark scheme and examiner's report
reduce rows then columns
3 lines cover the zeros so augment by 2.5 (double-covered +e, uncovered −e)
allocation A–Q, B–P, C–R, D–S
most errors were numerical slips or not reading the allocation from the zeros
Find an Edexcel Further Maths tutor
Stuck on this? Book a trial lesson with our Further Maths tutor.