In the Hungarian method for solving assignment problem, an optimal assignment…
2015
In the Hungarian method for solving assignment problem, an optimal assignment requires that the maximum number of lines that can be drawn through squares with zero opportunity cost be equal to the number of :
- A.
rows or columns
- B.
rows + columns
- C.
rows + columns -1
- D.
rows + columns +1
Attempted by 25 students.
Show answer & explanation
Correct answer: A
Answer: rows or columns (the order n of the matrix).
Key idea: For an n×n assignment problem the Hungarian method produces an optimal assignment when the minimum number of horizontal or vertical lines needed to cover all zeros in the reduced cost matrix equals n. That condition indicates there are n independent zeros allowing a complete one-to-one assignment.
Start with the cost matrix and perform row and column reductions to create as many zeros as possible.
Cover all zeros using the minimum number of horizontal or vertical lines.
If the minimum number of lines equals n (the number of rows or columns), an optimal assignment exists and can be found by selecting n independent zeros (one per row and column).
If the minimum number of lines is less than n, adjust the matrix (subtract the smallest uncovered value from uncovered elements and add it to elements covered twice) and repeat until the condition holds.
Note: The phrasing in some questions may say 'maximum number of lines', but the correct test uses the minimum number of lines covering all zeros. The required equality is with the matrix order (number of rows or columns).