Edexcel A-level Further Maths revision notes

Allocation (assignment) problems

Section 2

Years 1 and 2

2 specification points

Notes and three levels of exam-style practice for each registered specification point in this section.

Checked against Edexcel 9FM0 section 2

Checked against Edexcel 9FM0 section 2. Review basis: the qualification registry sourced from the Pearson Edexcel Level 3 Advanced GCE in Further Mathematics (9FM0) specification; registry verification recorded 17 July 2026.

How this checking works

In the exam: Formulae booklet provided · calculator allowed in every paper

Open the printable pack

2.1

Year 1

Cost matrix reduction. Use of the Hungarian algorithm to find a least cost allocation. Modification of the Hungarian algorithm to deal with a maximum profit allocation.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

An allocation problem matches $n$ workers to $n$ tasks, one each, at least total cost. The Hungarian algorithm works because subtracting a constant from a whole row, or from a whole column, changes every complete allocation by the same amount and therefore cannot change which allocation is cheapest.
The specification says "Students should reduce rows first": subtract each row's minimum, then reduce columns the same way, leaving at least one zero in every row and column. Now find the minimum number of horizontal and vertical lines needed to cover all the zeros. If that number equals $n$ , a complete allocation of zeros exists and it is optimal;
read it off, starting from any row or column with only one zero. If the number is less than $n$ , let $e$ be the smallest uncovered entry, subtract $e$ from every uncovered entry, add $e$ to every entry covered twice, leave the singly covered entries alone, and test the lines again.
For a maximum profit problem, subtract every entry of the original matrix from the largest entry of that matrix and then run the algorithm unchanged; the profit of the allocation is read from the original matrix.
Unequal numbers of workers and tasks are balanced with a dummy row or column of zeros, and a pairing that is not allowed is blocked by an entry so large that the algorithm never selects it.

Worked example

Three engineers $A$ , $B$ , $C$ must each take one of the jobs $X$ , $Y$ , $Z$ . The costs are $A$ : $30, 20, 21$ ; $B$ : $10, 26, 28$ ; $C$ : $14, 29, 16$ . Find the least cost allocation.

1.Row reduction subtracts $20$ , $10$ and $14$ , giving rows $(10,0,1)$ , $(0,16,18)$ and $(0,15,2)$ .
2.Column reduction subtracts $0$ , $0$ and $1$ , giving rows $(10,0,0)$ , $(0,16,17)$ and $(0,15,1)$ .
3.The zeros are covered by row $A$ and column $X$ , only $2$ lines, so the algorithm continues.
4.The smallest uncovered entry is $e=1$ at $CZ$ ; subtracting it from the uncovered entries and adding it to $AX$ , which is covered twice, gives rows $(11,0,0)$ , $(0,15,16)$ and $(0,14,0)$ .
5.Three lines are now needed, and the only complete allocation of zeros is $AY$ , $BX$ , $CZ$ .

Answer: $A\to Y$ , $B\to X$ , $C\to Z$ , read from the original matrix at a cost of $20+10+16=46$ .

Common mistakes

Don't fall into the trap of ignoring the order the question sets out; Edexcel questions normally require each row reduced by its smallest entry first, and marks follow that order even though column-first reaches the same optimum.
Don't fall into the trap of adding $e$ to the singly covered entries as well as the doubly covered ones.
Don't fall into the trap of reading the final cost from the reduced matrix instead of the original one.
Don't fall into the trap of converting a profit problem by subtracting the largest value of each row from that row, rather than subtracting every entry from the largest value in the whole matrix.

Exam tip

Write the lines you used on the diagram; a mark is available for showing that the minimum number of covering lines is fewer than $n$ , and a bald "not optimal" earns nothing.

Tier 1 · Easy

ORIGINAL

The cost of assigning workers

A

B

C

to tasks

X

Y

Z

is given by

A

20, 25, 22

;

B

15, 18, 23

;

C

19, 17, 21

. Carry out row reduction followed by column reduction, and state the least cost allocation.

(5)

(Total for Question 1 is 5 marks)

Tier 2 · Standard

ORIGINAL

Apply the Hungarian algorithm to the cost matrix with rows

A

14, 10, 12

;

B

9, 15, 11

;

C

13, 8, 16

for tasks

X

Y

Z

, and state the minimum cost and the allocation.

(5)

(Total for Question 1 is 5 marks)

Tier 3 · Hard

ORIGINAL

Apply the Hungarian algorithm to the cost matrix with rows

A

18, 10, 17

;

B

18, 8, 21

;

C

11, 12, 15

for tasks

X

Y

Z

. Show the covering lines at each stage, state the value of

e

used and give the least cost allocation.

(7)

(Total for Question 1 is 7 marks)

Your progress and exam materials

This section: Evidence from your answers: 0/2 secureYour confidence: 0 self-rated secureTracker status: 0/2 secure, 0 shaky, 2 unseen

Overall: Evidence from your answers: 0/158 secureYour confidence: 0 self-rated secureTracker status: 0/158 secure, 0 shaky, 158 unseen

Progress is saved on this device for guests and accounts right now; cross-device account sync is not live yet.

2.2

Year 2

Formulation of the Hungarian algorithm as a linear programming problem.

Notes

Evidence from your answers: none yet

Your confidence:

Explanation

An allocation problem is a linear program in $n^2$ variables. Let $x_{ij}=1$ if worker $i$ is given task $j$ and $x_{ij}=0$ otherwise.
The objective is to minimise $\sum_i\sum_j C_{ij}x_{ij}$ , the total cost of the pairs chosen. Each worker must be given exactly one task, so $\sum_j x_{ij}=1$ for every $i$ ; each task must be given to exactly one worker, so $\sum_i x_{ij}=1$ for every $j$ .
Together with $x_{ij}\geqslant0$ that is $2n$ equality constraints on $n^2$ variables. Although the variables are described as $0$ or $1$ , the integrality does not have to be imposed: the constraint matrix has the special structure that forces every vertex of the feasible region to have integer coordinates, so solving the linear program automatically returns a genuine allocation.
The formulation is also a transportation problem in which every supply and every demand is $1$ , which is why the same shadow-cost ideas underlie both.
For a maximum profit problem the objective is maximised instead, or minimised after replacing each entry by its distance below the largest entry.

Worked example

Two workers $A$ and $B$ must take one each of tasks $X$ and $Y$ , at costs $AX=5$ , $AY=8$ , $BX=7$ , $BY=6$ . Formulate this as a linear program.

1.Let $x_{ij}=1$ if worker $i$ does task $j$ , and $x_{ij}=0$ otherwise, for $i\in\{A,B\}$ and $j\in\{X,Y\}$ .
2.Minimise $C=5x_{AX}+8x_{AY}+7x_{BX}+6x_{BY}$ .
3.Worker constraints: $x_{AX}+x_{AY}=1$ and $x_{BX}+x_{BY}=1$ .
4.Task constraints: $x_{AX}+x_{BX}=1$ and $x_{AY}+x_{BY}=1$ .
5.Non-negativity: $x_{ij}\geqslant0$ for all $i$ and $j$ .

Answer: Minimise $C=5x_{AX}+8x_{AY}+7x_{BX}+6x_{BY}$ subject to those four equations and $x_{ij}\geqslant0$ .

Common mistakes

Don't fall into the trap of writing the worker or task constraints with $\leqslant$ , which allows a worker to be left idle in a square problem.
Don't fall into the trap of defining $x_{ij}$ as a cost or a task rather than as an indicator of whether the pairing is used.
Don't fall into the trap of claiming that integer constraints must be added; they are implied by the structure of the constraints.

Exam tip

State the meaning of $x_{ij}=1$ and of $x_{ij}=0$ separately; a definition that names only one of the two values usually loses the formulation mark.

Tier 1 · Easy

ORIGINAL

An allocation problem matches five workers to five tasks. State the number of decision variables and the number of equality constraints in its linear programming formulation, excluding the non-negativity conditions.

(3)

(Total for Question 1 is 3 marks)

Tier 2 · Standard

ORIGINAL

Workers

A

B

C

must take one each of tasks

X

Y

Z

at costs

A

14, 10, 12

;

B

9, 15, 11

;

C

13, 8, 16

. Formulate the problem completely as a linear program, defining your variables carefully.

(6)

(Total for Question 1 is 6 marks)

Tier 3 · Hard

ORIGINAL

Explain why the linear programming formulation of an allocation problem does not need explicit constraints of the form

x_{ij}\in\{0,1\}

, and state what would be true instead if such constraints were needed.

(6)

(Total for Question 1 is 6 marks)

See everything due today — your streak and what to revise next, kept on this device.

Want help turning these notes into marks?

Bring a tricky specification point or a recent answer, and we can work through the method and exam wording together.

Book a free intro call