4D.2.1 The Hungarian algorithm for allocation problems Quiz: Pearson Edexcel Further Maths, Unit 41

The 20 questions

1. What is the first step of the Hungarian algorithm for a minimising allocation problem?

   • Multiply each row by its smallest entry.
   • Add the smallest entry in each row to the diagonal.
   • Subtract the largest entry in each column from every entry in the matrix.
   • Subtract the smallest entry in each row from every entry in that row.

2. After row reduction, what is the second step of the Hungarian algorithm?

   • Draw lines through the largest entries in the matrix.
   • Add the largest entry in each column to every entry.
   • Reduce each column by subtracting its smallest entry from every entry in that column.
   • Count the zeros in each row and stop if every row has one.

3. What is the purpose of covering the zeros with lines in the Hungarian algorithm?

   • To show that every row has exactly two zeros.
   • To calculate the total minimum cost directly.
   • To find the largest entry that can be removed from the matrix.
   • To test whether an optimal allocation can be made using only zero entries.

4. When is an optimal allocation found in the Hungarian algorithm?

   • When the smallest uncovered entry is zero.
   • When every row contains exactly one zero.
   • When the number of lines equals the number of zeros.
   • When the minimum number of covering lines equals the size of the matrix.

5. For a maximum-profit allocation problem, how is the matrix converted to a minimum-cost problem?

   • Take the reciprocal of each value.
   • Subtract the largest value from every value.
   • Multiply every value by minus one and add the largest.
   • Subtract every value from the largest value in the original matrix.

6. What does a dummy location allow in the Hungarian algorithm?

   • The matrix to be converted into a transportation table.
   • Row reduction to be skipped completely.
   • A rectangular matrix to be made square by adding a dummy column of zeros.
   • A worker to be assigned to two jobs at once.

7. In the Hungarian method, what is subtracted from row 1 of the cost matrix [[4, 2, 8], [3, 9, 5], [6, 4, 7]] during row reduction?

   • 2
   • 8
   • 6
   • 4

8. After row reduction the second row is [0, 6, 2]. What is the entry in row 2, column 2 of the reduced matrix?

   • 3
   • 2
   • 6
   • 9

9. After row reduction the matrix is [[2, 0, 6], [0, 6, 2], [2, 0, 3]]. What is the smallest entry in column 3, which is subtracted in column reduction?

   • 2
   • 6
   • 0
   • 3

10. After column reduction, the zeros of the matrix lie at which cells?

    • (1, 2), (2, 1), (2, 3) and (3, 2)
    • (1, 1), (2, 2) and (3, 3)
    • (1, 2), (2, 1) and (3, 2) only
    • (1, 3), (2, 1), (3, 2) and (3, 3)

11. In the matrix with zeros at (1, 2), (2, 1), (2, 3) and (3, 2), what is the minimum number of lines needed to cover all the zeros?

    • 3
    • 4
    • 2
    • 1

12. The smallest uncovered entry in that matrix is 1. After adjusting the matrix, what is the new value at row 2, column 2?

    • 8
    • 7
    • 5
    • 6

13. In the optimal allocation of the cost matrix [[4, 2, 8], [3, 9, 5], [6, 4, 7]], which column is assigned to row 3?

    • Column 2
    • Column 1
    • Either column 1 or column 2
    • Column 3

14. What is the minimum total cost for the cost matrix [[4, 2, 8], [3, 9, 5], [6, 4, 7]]?

    • 20
    • 15
    • 13
    • 12

15. A profit matrix has largest value 9. What is the converted cost for an entry of 4?

    • 4
    • -4
    • 5
    • 13

16. Why does the algorithm need extra lines when the minimum number of lines is less than the matrix size?

    • A row has all zeros, which means the matrix is wrong.
    • No complete allocation of zeros exists yet, so the uncovered entries are adjusted to create new zeros.
    • The costs must be rounded before the algorithm can continue.
    • The matrix is already optimal and the lines must be removed.

17. A 3 by 4 matrix is made square by adding a dummy row. What should the entries in the dummy row be?

    • Large numbers, so the dummy is never chosen.
    • Negative numbers, to reduce costs.
    • The largest value in the matrix.
    • Zeros, so the dummy assigned job costs nothing.

18. A maximum-profit version of the problem is solved by the minimum-cost method. Why does the optimal allocation still maximise profit?

    • Each profit p becomes (largest - p), so minimising the transformed costs maximises the original profit.
    • Total profit always equals total cost.
    • Only the diagonal entries are used.
    • The transformed costs are all made equal.

19. Which assignment gives the minimum total cost for the matrix [[4, 2, 8], [3, 9, 5], [6, 4, 7]]?

    • Row 1 to column 1, row 2 to column 2 and row 3 to column 3, with total 20.
    • Row 1 to column 2, row 2 to column 1 and row 3 to column 3, with total 12.
    • Row 1 to column 3, row 2 to column 1 and row 3 to column 2, with total 15.
    • Row 1 to column 2, row 2 to column 3 and row 3 to column 1, with total 13.

20. How many possible allocations are there for a 3 by 3 assignment problem?

    • 3
    • 27
    • 9
    • 6

Related quizzes

• The Hungarian algorithm as a linear program Quiz · 4D.2.2 · 20 questions
• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions
• Applying the Central Limit Theorem Quiz · 3B.5.1 · 20 questions
• Goodness of fit tests for discrete distributions Quiz · 3B.6.1 · 20 questions