Q10Advanced Engineering Mathematics
Question
2 marks
Find the optimal assignment for the problem with minimum cost:
Answer
Subtract the minimum value in each row and column, then draw lines to cover all zeros to find the optimal assignment.
To solve the assignment problem for minimum cost, we use the Hungarian Algorithm:
Step 1: Subtract the minimum element of each row from all elements of that row. This creates at least one zero in each row.
Step 2: Subtract the minimum element of each column from all elements of that column.
Step 3: Draw the minimum number of horizontal and vertical lines to cover all the zeros in the matrix. If the number of lines equals the number of rows (), an optimal assignment can be made at the positions of the zeros.