Hungarian algorithm as a linear programme

Hungarian algorithm as a linear programme Test

Spec 2.2 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Hungarian algorithm as a linear programme

Total 27 marks

Name

Class

Date

  1. 1
    A hospital assigns three nurses, 1, 2 and 3, to three wards, 1, 2 and 3, with one nurse on each ward. Let xij=1x_{ij}=1 if nurse ii is assigned to ward jj, and xij=0x_{ij}=0 otherwise. The cost, in £ hundred, of nurse ii on ward jj is the entry in row ii, column jj of (6978510784)\begin{pmatrix} 6 & 9 & 7 \\ 8 & 5 & 10 \\ 7 & 8 & 4 \end{pmatrix}. The hospital wants the total cost to be as small as possible and formulates the problem as a linear programme.
    (a)
    What does x23=1x_{23}=1 mean?
    [1 mark]
    • ANurse 3 is assigned to ward 2
    • BWard 2 costs £33 hundred
    • CNurse 2 is assigned to ward 3
    • DNurse 2 is not assigned to ward 3
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    What is the total cost, in £ hundred, when x12=x21=x33=1x_{12}=x_{21}=x_{33}=1 and all other variables are 00?
    [1 mark]
    • A2121
    • B1515
    • C1919
    • D2727
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Write down the constraint that ensures nurse 2 is assigned to exactly one ward, and state the values each xijx_{ij} may take.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: x21+x22+x23=1x_{21}+x_{22}+x_{23}=1
    B1: each
    xijx_{ij} is 00 or 11 (binary)
    Accept:
    xij≥0x_{ij}\ge0 and integer, since the constraints then force xij≤1x_{ij}\le1
    Do not accept:
    x21+x22+x23≤1x_{21}+x_{22}+x_{23}\le1

    Total for question 1: 4 marks

  2. 2
    A company has four representatives and four regions. Let pijp_{ij} be the profit, in £ hundred, when representative ii works in region jj, and let xij=1x_{ij}=1 if representative ii is sent to region jj and xij=0x_{ij}=0 otherwise. Each representative goes to exactly one region and each region receives exactly one representative. The company wants to maximise the total profit and formulates the problem as a linear programme.
    (a)
    Which of these is the objective function?
    [1 mark]
    • AMinimise ∑i=14∑j=14pijxij\sum_{i=1}^{4}\sum_{j=1}^{4}p_{ij}x_{ij}
    • BMaximise ∑i=14∑j=14xij\sum_{i=1}^{4}\sum_{j=1}^{4}x_{ij}
    • CMaximise ∑i=14∑j=14pij\sum_{i=1}^{4}\sum_{j=1}^{4}p_{ij}
    • DMaximise ∑i=14∑j=14pijxij\sum_{i=1}^{4}\sum_{j=1}^{4}p_{ij}x_{ij}
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    How many equality constraints (not counting the conditions on the values of xijx_{ij}) does the formulation have?
    [1 mark]
    • A44
    • B88
    • C1616
    • D1212
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    The allocation x11=x22=x33=x44=1x_{11}=x_{22}=x_{33}=x_{44}=1, with all other variables 00, has p11=12p_{11}=12, p22=9p_{22}=9, p33=14p_{33}=14 and p44=11p_{44}=11. Show that this allocation satisfies the constraints for representative 1 and for region 1, and find its total profit.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: representative 1: x11+x12+x13+x14=1+0+0+0=1x_{11}+x_{12}+x_{13}+x_{14}=1+0+0+0=1 and region 1: x11+x21+x31+x41=1+0+0+0=1x_{11}+x_{21}+x_{31}+x_{41}=1+0+0+0=1
    B1: total profit
    12+9+14+11=4612+9+14+11=46, that is £46004600
    Accept:
    4646 with the units £ hundred

    Total for question 2: 4 marks

  3. 3
    A firm has four workers and three tasks. Each task must be done by exactly one worker and each worker does at most one task. The time, in hours, for worker ii to do task jj is the entry in row ii, column jj of (968785697859)\begin{pmatrix} 9 & 6 & 8 \\ 7 & 8 & 5 \\ 6 & 9 & 7 \\ 8 & 5 & 9 \end{pmatrix}. The firm wants the total time to be as small as possible and formulates the problem as a linear programme.
    (a)
    Define suitable variables and write down the objective function.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: xij=1x_{ij}=1 if worker ii does task jj, and 00 otherwise
    M1: minimise the sum of (time
    ×\times variable) over the pairings
    A1: minimise
    9x11+6x12+8x13+7x21+8x22+5x23+6x31+9x32+7x33+8x41+5x42+9x439x_{11}+6x_{12}+8x_{13}+7x_{21}+8x_{22}+5x_{23}+6x_{31}+9x_{32}+7x_{33}+8x_{41}+5x_{42}+9x_{43}
    Do not accept: maximise
    (b)
    Write down the constraints, and explain why the constraints for the workers are not all equalities.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: each task done exactly once: x11+x21+x31+x41=1x_{11}+x_{21}+x_{31}+x_{41}=1, x12+x22+x32+x42=1x_{12}+x_{22}+x_{32}+x_{42}=1, x13+x23+x33+x43=1x_{13}+x_{23}+x_{33}+x_{43}=1
    B1: each worker does at most one task:
    x11+x12+x13≤1x_{11}+x_{12}+x_{13}\le1, x21+x22+x23≤1x_{21}+x_{22}+x_{23}\le1, x31+x32+x33≤1x_{31}+x_{32}+x_{33}\le1, x41+x42+x43≤1x_{41}+x_{42}+x_{43}\le1
    R1: there are four workers but only three tasks, so one worker has no task; equalities for every worker could not all be satisfied

    B1:
    xij∈{0,1}x_{ij}\in\{0,1\}

    Total for question 3: 7 marks

  4. 4
    A theatre has three technicians, Raj, Sam and Tess, and three tasks: lighting (1), sound (2) and staging (3). Each technician does one task and each task is done by one technician. The value, in £ hundred, of each technician on each task is given below in the order lighting, sound, staging. Raj: 14, 11, 9. Sam: 8, 13, – (Sam cannot do staging). Tess: 10, 7, 12. The theatre wants the total value to be as large as possible. Technicians Raj, Sam and Tess are numbered 1, 2 and 3.
    (a)
    Formulate this as a linear programming problem.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: xij=1x_{ij}=1 if technician ii does task jj, and 00 otherwise
    B1: maximise

    B1:
    14x11+11x12+9x13+8x21+13x22+10x31+7x32+12x3314x_{11}+11x_{12}+9x_{13}+8x_{21}+13x_{22}+10x_{31}+7x_{32}+12x_{33} with no x23x_{23} term
    B1: each technician does one task:
    x11+x12+x13=1x_{11}+x_{12}+x_{13}=1, x21+x22=1x_{21}+x_{22}=1, x31+x32+x33=1x_{31}+x_{32}+x_{33}=1
    B1: each task done once:
    x11+x21+x31=1x_{11}+x_{21}+x_{31}=1, x12+x22+x32=1x_{12}+x_{22}+x_{32}=1, x13+x33=1x_{13}+x_{33}=1
    B1:
    xij∈{0,1}x_{ij}\in\{0,1\}
    Accept:
    x23x_{23} kept, with x23=0x_{23}=0 as an extra constraint
    (b)
    The booking system means that Raj on lighting and Tess on staging cannot both be chosen. (i) Write this as a constraint. (ii) Explain why the Hungarian algorithm cannot now be used. (iii) Given that without this condition the maximum total value is £39003900, find the new maximum and the allocation.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) x11+x33≤1x_{11}+x_{33}\le1
    R1: (ii) this is not a one-technician or one-task constraint, so the problem is no longer a pure assignment problem

    M1: (iii) the unrestricted best allocation
    x11=x22=x33=1x_{11}=x_{22}=x_{33}=1 breaks the constraint
    M1: the other feasible allocations have values
    3131, 2424 and 3232 (£31003100, £24002400, £32003200)
    A1: best allocation
    x13=x22=x31=1x_{13}=x_{22}=x_{31}=1: Raj staging, Sam sound, Tess lighting
    A1: maximum value £
    32003200
    Accept: £
    3232 hundred

    Total for question 4: 12 marks

End of questions

Subtopic tests