Further Mathematics · Pearson Edexcel 9FM0 · Option D2 · Topic 2

Allocation (assignment) problems

Allocation problems: matching workers to tasks with the Hungarian algorithm.

  • 2 sub-topics
  • Taught in Year 13
  • 26 practice questions
  • 2 animated lessons
Practice questions (26) Lessons Worksheets All Edexcel Further Mathematics topics

What the specification says

Every sub-topic Pearson Edexcel can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

  1. 2.1Allocation and the Hungarian algorithmY13
  2. 2.2Allocation as a linear programY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 26 questions in this topic, free, no account needed.

Allocation (assignment) problems

Not needed for Year 12Easy

Starting the Hungarian algorithm · Year 13 · 1 mark

  1. What is the first step of the Hungarian algorithm on a square cost matrix?
    (1)

Show worked solutionHide worked solution
  1. This gives at least one zero in every row and column.BB: Subtract the smallest entry in each row from every entry in that row, then do the same for the columns

Total1

  • M
  • A
  • B
How did it go?

Report a problem with this question

Allocation (assignment) problems

Not needed for Year 12Medium

Allocation as a linear programme · Year 13 · 5 marks

Three workers are to be assigned to three tasks, one each. The cost matrix (rows workers, columns tasks) is (151023303133393031)\begin{pmatrix} 15 & 10 & 23 \\ 30 & 31 & 33 \\ 39 & 30 & 31 \end{pmatrix}.
  1. Formulate this as a linear programming problem.
    (5)
Show worked solutionHide worked solution
  1. xij=1x_{ij} = 1 if worker i\mathrm{i} does task jj, 0 otherwise.
  2. minimise 15x11\text{minimise } 15x_{11}+10x12{}+ 10x_{12}+23x13{}+ 23x_{13}+30x21{}+ 30x_{21}+31x22{}+ 31x_{22}+33x23{}+ 33x_{23}+39x31{}+ 39x_{31}+30x32{}+ 30x_{32}+31x33{}+ 31x_{33}
  3. ∑jxij\sum_j x_{ij}=1 for each worker i{}= 1 \text{ for each worker i}
  4. ∑ixij\sum_i x_{ij}=1 for each task j{}= 1 \text{ for each task j}
  5. xij≥0x_{ij} \geq 0

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question

Allocation (assignment) problems

Not needed for Year 12Hard

The Hungarian algorithm · Year 13 · 6 marks

Workers P, Q, R, S are to be assigned to jobs 1, 2, 3, 4, one each. The table shows the times, in minutes (rows workers, columns jobs). (34293138392639203334282832393710)\begin{pmatrix} 34 & 29 & 31 & 38 \\ 39 & 26 & 39 & 20 \\ 33 & 34 & 28 & 28 \\ 32 & 39 & 37 & 10 \end{pmatrix}
  1. (a)
    Reduce the rows and then the columns.
    (2)
  2. (b)
    Complete the Hungarian algorithm to find the allocation that minimises the total time, and state that time.
    (4)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)2 marks

  1. Subtract each row minimum, then each column minimum.(002914619006001729270)\begin{pmatrix} 0 & 0 & 2 & 9 \\ 14 & 6 & 19 & 0 \\ 0 & 6 & 0 & 0 \\ 17 & 29 & 27 & 0 \end{pmatrix}

Part (b)4 marks

  1. Cover the zeros with the fewest lines; if fewer than 4 lines, adjust by the smallest uncovered element.
  2. P–1, Q–2, R–3, S–4
  3. 98 minutes98\text{ minutes}

Total6

  • M
  • A
  • B
How did it go?

Report a problem with this question