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 an assignment problem, what does the variable x_ij represent?

   • The total number of jobs done by worker i.
   • The cost of assigning worker i to job j.
   • 1 if worker i is assigned to job j, and 0 otherwise.
   • The reduced cost of cell (i, j) after row reduction.

2. Which constraint states that each worker is assigned exactly one job?

   • The sum over all i and j of x_ij = n squared.
   • The sum over i of x_ij = 1 for each job j.
   • The sum over j of x_ij = 0 for each worker i.
   • The sum over j of x_ij = 1 for each worker i.

3. Which constraint states that each job is done by exactly one worker?

   • The sum over j of x_ij = 1 for each worker i.
   • x_ij = 1 for every pair (i, j).
   • The sum over i of x_ij = 1 for each job j.
   • The sum over i of x_ij = 0 for each job j.

4. What is the objective of the assignment linear program with costs c_ij?

   • Minimise the sum over all i and j of c_ij x_ij.
   • Minimise the sum of x_ij over the unassigned pairs.
   • Maximise the sum of x_ij.
   • Maximise the sum over all i and j of c_ij x_ij.

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

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

6. Why is the solution of the assignment linear program automatically 0 or 1 at each variable?

   • Each variable is forced to be less than 2.
   • The constraint matrix is totally unimodular, so every vertex of the feasible region is integer valued.
   • The objective is linear, so every solution is rounded.
   • Assignment costs are always integers.

7. Which statement connects the Hungarian algorithm with its linear programming formulation?

   • The algorithm replaces the objective function with a constraint.
   • The Hungarian algorithm finds an optimal solution to the assignment linear program without using the simplex method.
   • The algorithm is only valid when the linear program has no integer solution.
   • The algorithm needs slack variables to represent unassigned workers.

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. Subtracting a constant from every entry of one row changes the total cost of every assignment by the same amount. Why does this leave the optimal assignment unchanged?

    • Each assignment uses no entries from that row, so costs remain the same.
    • The constant is only subtracted from the diagonal, so assignments change.
    • Row constants change the constraints, which alters feasibility.
    • Each assignment uses exactly one entry from that row, so the total falls by the same constant for every assignment.

13. To maximise profit p_ij with the same assignment constraints, which objective is used?

    • Minimise the sum of x_ij.
    • Minimise the sum of p_ij x_ij.
    • Maximise the sum of p_ij x_ij.
    • Maximise the sum of x_ij divided by p_ij.

14. Is the constraint 'sum over j of x_ij = 1' an equality or an inequality in the standard assignment linear program?

    • An inequality of type ≥, since jobs may be assigned twice.
    • An equality with right-hand side zero.
    • An inequality of type ≤, since workers may be unassigned.
    • An equality, since each worker must be assigned exactly one job.

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

    • 4
    • 3
    • 1
    • 2

16. An assignment problem has 4 workers and 3 jobs. To use the square method, what change is needed?

    • Remove one worker, so the matrix becomes 3 by 3 with the same constraints.
    • Add a dummy job column with zero costs so the matrix is square.
    • Double every cost so that the rows balance.
    • Add a dummy job with cost 1 to every cell.

17. A worker cannot do a particular job. How is that pair normally handled in the assignment linear program?

    • Give it a very large cost or omit the variable, so it is never chosen in a minimum solution.
    • Add an extra slack variable to that pair only.
    • Set x_ij = 2 for that pair.
    • Give it a cost of zero, so it is always chosen.

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. Which method is the Hungarian algorithm a special case of when applied to the assignment linear program?

    • Dynamic programming with stage variables.
    • The labelling procedure for flows.
    • The simplex algorithm applied to the assignment linear program.
    • The stepping-stone method on a 1 by 1 table.

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