The Hungarian algorithm

The Hungarian algorithm Test

Spec 2.1 · 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

The Hungarian algorithm

Total 27 marks

Name

Class

Date

  1. 1
    A firm has three engineers, Ana, Ben and Cleo, and three tasks: wiring (W), testing (T) and installing (I). Each engineer must do exactly one task and each task is done by exactly one engineer. The cost, in £, of each engineer doing each task is given by the matrix (8128107111239)\begin{pmatrix} 8 & 12 & 8 \\ 10 & 7 & 11 \\ 12 & 3 & 9 \end{pmatrix}, where the rows are Ana, Ben, Cleo and the columns are W, T, I. The firm wants the total cost to be as small as possible.
    (a)
    The rows are reduced first. What is the entry for Ben doing task W in the row-reduced matrix?
    [1 mark]
    • A00
    • B33
    • C77
    • D1010
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    The rows and then the columns are reduced. What is the minimum number of straight lines needed to cover every zero in the reduced matrix?
    [1 mark]
    • A33
    • B44
    • C11
    • D22
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Complete the Hungarian algorithm to find the allocation with the least total cost, and state that cost.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: smallest uncovered entry 33 subtracted from every uncovered entry and added to the entry covered twice, giving (070001603)\begin{pmatrix} 0 & 7 & 0 \\ 0 & 0 & 1 \\ 6 & 0 & 3 \end{pmatrix}
    A1: Ana–I, Ben–W, Cleo–T with total cost £
    2121
    Accept: the cost found from the original matrix,
    8+10+38+10+3
    Do not accept: a total found from the reduced matrix

    Total for question 1: 4 marks

  2. 2
    A company has three sales representatives, Dev, Eli and Fay, to send to three regions: North, South and East. Each representative goes to a different region. The expected monthly profit, in £ thousand, of each representative in each region is given by the matrix (513111011145125)\begin{pmatrix} 5 & 13 & 11 \\ 10 & 11 & 14 \\ 5 & 12 & 5 \end{pmatrix}, where the rows are Dev, Eli, Fay and the columns are North, South, East. The company wants the total profit to be as large as possible and uses the Hungarian algorithm.
    (a)
    The matrix is converted so that the algorithm can find a minimum. What is the entry for Dev in North in the converted matrix?
    [1 mark]
    • A99
    • B55
    • C1414
    • D1919
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    What is the maximum total expected profit, in £ thousand?
    [1 mark]
    • A99
    • B3232
    • C3333
    • D3939
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    A trainee applies the Hungarian algorithm directly to the original profit matrix, with no conversion. Explain why the allocation found would not be the one the company wants.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: the Hungarian algorithm finds the allocation with the least total
    B1: so the trainee would find the allocation with the least total profit, not the greatest

    Do not accept: 'it gives the wrong answer' with no reason

    Total for question 2: 4 marks

  3. 3
    A courier firm has four drivers, P, Q, R and S, and three deliveries, X, Y and Z. Each delivery is made by exactly one driver and each driver makes at most one delivery. The cost, in £, of each driver making each delivery is given by the matrix (212712331426322025293814)\begin{pmatrix} 21 & 27 & 12 \\ 33 & 14 & 26 \\ 32 & 20 & 25 \\ 29 & 38 & 14 \end{pmatrix}, where the rows are P, Q, R, S and the columns are X, Y, Z. The firm wants the total cost to be as small as possible.
    (a)
    A dummy delivery is added so that the Hungarian algorithm can be used. Explain why this is needed, and state what should be entered in the dummy column.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: the algorithm needs a square matrix and there are 4 drivers but only 3 deliveries
    B1: every entry in the dummy column is the same, e.g.
    00
    B1: the driver matched with the dummy delivery makes no real delivery and adds no cost

    Accept: any equal constant in the dummy column

    Do not accept: different values for different drivers
    (b)
    Use the Hungarian algorithm on the 4 by 4 matrix to find which delivery each driver makes and the least total cost. State which driver makes no delivery.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: rows already contain a zero (the dummy), so reduce the columns by 21,14,12,021, 14, 12, 0 to get (0130012014011613082420)\begin{pmatrix} 0 & 13 & 0 & 0 \\ 12 & 0 & 14 & 0 \\ 11 & 6 & 13 & 0 \\ 8 & 24 & 2 & 0 \end{pmatrix}
    A1: three lines (the dummy column and rows P and Q) cover the zeros, fewer than 4, so augment: subtract
    22 from uncovered entries, add 22 to those covered twice, giving (013021201429411062200)\begin{pmatrix} 0 & 13 & 0 & 2 \\ 12 & 0 & 14 & 2 \\ 9 & 4 & 11 & 0 \\ 6 & 22 & 0 & 0 \end{pmatrix}
    M1: allocation from the zeros: P–X, Q–Y, S–Z, R–dummy

    A1: total cost £
    4949, and R makes no delivery
    Accept: the lines drawn differently, if they still cover all zeros with three lines

    Accept: a total found from
    21+14+1421+14+14

    Total for question 3: 7 marks

  4. 4
    A garage has four mechanics, Kai, Lou, Mia and Ned, and four repair jobs, J1, J2, J3 and J4. Each mechanic does exactly one job. The cost, in £, of each mechanic doing each job is given below in the order J1, J2, J3, J4, where a dash means the mechanic is not qualified for that job. Kai: 44, 23, –, 40. Lou: 28, 43, 45, 34. Mia: 45, 23, 49, 48. Ned: 26, 39, 47, 30. The garage wants the total cost to be as small as possible.
    (a)
    Use the Hungarian algorithm, dealing with the missing entry, to find an allocation with the least total cost, and state that cost.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: a very large number MM entered for Kai doing J3
    M1: rows reduced by subtracting the row minima (
    23,28,23,2623, 28, 23, 26)
    A1: columns reduced by
    0,0,17,40, 0, 17, 4 to give (210M−40130150222092101340)\begin{pmatrix} 21 & 0 & M-40 & 13 \\ 0 & 15 & 0 & 2 \\ 22 & 0 & 9 & 21 \\ 0 & 13 & 4 & 0 \end{pmatrix}
    M1: three lines cover the zeros (J2 column, and the rows of Lou and Ned), fewer than 4, so augment using the smallest uncovered entry

    A1: smallest uncovered entry
    99 used, giving (120M−4940240213001202240)\begin{pmatrix} 12 & 0 & M-49 & 4 \\ 0 & 24 & 0 & 2 \\ 13 & 0 & 0 & 12 \\ 0 & 22 & 4 & 0 \end{pmatrix}
    A1: Kai–J2, Lou–J1, Mia–J3, Ned–J4 with total cost £
    130130
    Accept: any large number in place of
    MM
    (b)
    The garage can train Kai to do J3 at a cost of £3131 for the job, with the training costing £1515. Use the Hungarian algorithm to decide whether the training is worthwhile.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: 3131 replaces MM and the row minima 23,28,23,2623, 28, 23, 26 are subtracted
    M1: columns reduced by
    0,0,8,40, 0, 8, 4
    A1: reduced matrix
    (210013015922201821013130)\begin{pmatrix} 21 & 0 & 0 & 13 \\ 0 & 15 & 9 & 2 \\ 22 & 0 & 18 & 21 \\ 0 & 13 & 13 & 0 \end{pmatrix}
    M1: allocation read from the zeros (a complete allocation exists, so no augmenting is needed): Kai–J3, Lou–J1, Mia–J2, Ned–J4

    A1: total cost £
    112112
    R1: saving of
    130−112=18130-112=18 is greater than the training cost of 1515, so the training is worthwhile (net saving £33)
    Accept: comparing £
    112+15=127112+15=127 with £130130

    Total for question 4: 12 marks

End of questions

Subtopic tests