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?

   • Dummy allocation
   • Maximum matching
   • Column addition
   • Row reduction

2. What is the second main step of the Hungarian algorithm after row reduction?

   • Line covering
   • Matrix expansion
   • Column reduction
   • Row reduction

3. What do covering lines test in the Hungarian algorithm?

   • Unimodularity
   • Maximum profit
   • Feasibility
   • Optimality

4. When using covering lines in the Hungarian algorithm, when is an optimal allocation reached?

   • Lines exceed matrix size
   • Lines equal zero
   • Lines equal total rows
   • Lines equal matrix size

5. How is a profit matrix converted to a cost matrix for the Hungarian algorithm?

   • Reciprocal of each value
   • Add to minimum
   • Multiply by minus one
   • Subtract from maximum

6. What is the purpose of a dummy row or column?

   • Eliminate large entries
   • Remove negative values
   • Make matrix square
   • Reduce total cost

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. What happens when covering lines are fewer than the matrix size?

    • Add a dummy row
    • Adjust uncovered entries
    • Reset all reductions
    • Stop the algorithm

17. What should the entries in a dummy row be?

    • Ones
    • Matrix minimums
    • Matrix maximums
    • Zeros

18. Why does solving a transformed profit matrix using the minimum-cost Hungarian method still maximise profit?

    • Minimising transformed costs
    • Maximising total revenues
    • Inverting the allocation matrix
    • Scaling all profits up

19. What type of problem must the Hungarian algorithm be directly applied to?

    • Maximisation
    • Minimisation
    • Optimisation
    • Distribution

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