The Assignment
The Optimal Assignment
Once the cover count reaches n, the reduced matrix contains independent zeros. Choosing one zero in each row and column gives an assignment. This lesson reads that assignment and evaluates its original cost, keeping separate the reduced matrix used for selection and the original matrix used for the objective.
Independent zeros
The selected cells are W1 to J1, W2 to J3, and W3 to J2. Why: assignment cells choose one zero in each row and each column. That independence condition is what turns promising zero cells into a valid one-to-one worker-job matching. A zero that conflicts with another selected zero is still useful information, but it cannot be part of this final assignment.
Original cost
Read the cost from the original matrix: 4 plus 7 plus 1 equals 12. Why: reductions guide the choice, but the objective is original cost. This is the honesty check at the end of the algorithm: the reduced zeros identify the assignment, and the original matrix evaluates it.
Diagram note
Legend: final-assignment cells and other zero cells are marked by role. The assignment is exact for this square integer cost matrix, and the selected cells are read back against the original costs. The reduced matrix identifies the matching, but the original matrix remains the source of truth for the cost. Pixel positions are rounded for layout; every number shown is exact.