4D.2.2 The Hungarian algorithm as a linear program Quiz: Pearson Edexcel Further Maths, Unit 41

The 20 questions

1. In the linear programming formulation of assignment, what does x_ij represent?

   • Capacity constraint limit
   • Total cost coefficient
   • Binary assignment variable
   • Dummy flow amount

2. What linear programming constraint ensures that each worker receives exactly one job?

   • Total cost zero
   • Column sum one
   • Matrix sum one
   • Row sum one

3. What linear programming constraint ensures that each job is done by one worker?

   • Row sum one
   • Column sum zero
   • Column sum one
   • Row sum zero

4. What algorithmic technique solves the assignment problem as a linear program in polynomial time?

   • Simplex method
   • Gaussian elimination
   • Newton Raphson
   • Binary search

5. For an n by n assignment problem, how many independent constraints are there?

   • 2n - 1
   • n
   • 2n
   • n squared

6. What property of the constraint matrix ensures integer solutions in an assignment LP?

   • Symmetric positive definite
   • Totally unimodular
   • Strictly diagonally dominant
   • Lower triangular

7. What geometric property do the extreme points of the assignment constraint polytope possess?

   • Zero determinants
   • Integer coordinates
   • Negative coefficients
   • Fractional values

8. How many decision variables x_ij does a 3 by 3 assignment linear program have?

   • 9
   • 3
   • 6
   • 27

9. In the 3 by 3 assignment linear program, how many of the six row and column equality constraints are independent?

   • 3
   • 6
   • 5
   • 9

10. A candidate allocation sets x_11 = x_22 = x_33 = 1 in a 3 by 3 problem with costs [[4, 2, 8], [3, 9, 5], [6, 4, 7]]. What is its total cost?

    • 23
    • 20
    • 15
    • 12

11. Which set of variables is a valid assignment for a 3 by 3 problem?

    • x_11 = x_22 = 1, all others 0
    • x_12 = x_21 = x_33 = 1, all others 0
    • x_11 = x_12 = x_33 = 1, all others 0
    • x_12 = x_13 = x_21 = 1, all others 0

12. Why does subtracting a constant from a row leave the optimal assignment unchanged?

    • Zero total
    • Matrix scaling
    • Row elimination
    • Equal shift

13. To maximise profit with assignment constraints, what is the objective function?

    • Minimise slack variables
    • Minimise total cost
    • Maximise total profit
    • Maximise total flow

14. What type of constraint represents each worker being assigned exactly one job?

    • UpperBound
    • LowerBound
    • Inequality
    • Equality

15. How many independent constraints does a 2 by 2 assignment linear program have?

    • 4
    • 3
    • 1
    • 2

16. What must be added to a non-square assignment cost matrix to make it square?

    • Extra decision variable
    • Dummy row or column
    • Negative cost entry
    • Unit matrix

17. How is an impossible worker-job assignment normally represented in a cost matrix?

    • Very large cost
    • Zero cost
    • Undefined cost
    • Negative cost

18. Using the profit matrix [[3, 1], [2, 5]], what is the maximum total profit from assigning workers to jobs?

    • 6
    • 3
    • 10
    • 8

19. What is the minimum total cost for the cost matrix [[3, 1], [2, 5]]?

    • 7
    • 5
    • 3
    • 8

20. The Hungarian algorithm is a special case of which general algorithm applied to linear programming?

    • Prim algorithm
    • Kruskal algorithm
    • Simplex algorithm
    • Bellman-Ford algorithm

Related quizzes

• The Hungarian algorithm for allocation problems Quiz · 4D.2.1 · 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