Q.In the Hungarian method, after row and column reduction the minimum number of lines needed to cover all the zeros of a $5 \times 5$ matrix is $4$. This means:

The optimality test compares the number of covering lines with the order $n$ of the matrix.

An optimal assignment exists only when the minimum number of covering lines equals $n$. Here $4 < 5$, so we must revise the matrix (subtract the smallest uncovered value, add it at intersections) and test again.

Rule. In the Hungarian method, once every row and column has a zero, we cover all zeros with the fewest possible horizontal/vertical lines. The optimality test states:

If the number of lines is less than $n$, the current zeros are not enough to make a complete assignment, and the matrix must be revised.

Applying it. Here $n = 5$ but only $4$ lines are needed to cover all zeros. Since $4 < 5$, an optimal assignment is not yet available.

• (a) is wrong — optimality would require $5$ lines, not $4$.
• (c) is wrong — a (balanced) assignment problem always has a feasible solution; the method has simply not finished.
• (d) is wrong — a dummy row is for unbalanced problems; this matrix is already square.
• (b) is correct — we take the smallest uncovered entry $\theta$, subtract it from all uncovered entries, add it at the intersections of lines, and re-test.

Believing that having a zero in every row and column already means the solution is optimal. Optimality needs $n$ independent zeros, equivalently $n$ covering lines; fewer lines means another revision step is required.