0
7.1kviews
Solve the following assignment problem.
I II III IV V
1 6 2 5 2 6
2 2 5 8 7 7
3 7 8 6 9 8
4 6 2 3 4 5
5 9 3 8 9 10
6 4 7 5 6 8
1
98views

(NOTE: The question does not specify whether to maximize or minimize the allocations. So we assume itâ€™s a minimization problem while solving)

Consider the matrix:

• Subtracting the smallest element in each row, from all the other row elements:

Number of lines = 3 < order of matrix = 5

• Subtracting the smallest element in each column, from all the other column elements:

Allocation can be made as shown. However, each row and column do not have one allocation. Drawing minimum number of lines through the zeroes:

• Subtracting the minimum uncovered element from all the other uncovered elements, and adding it to the elements where 2 lines intersect:

Allocation can be made as shown above. Each row and column still do not have one allocation. Drawing minimum number of lines through the zeroes:

• Subtracting the minimum uncovered element from all the other uncovered elements, and adding it to the elements where 2 lines intersect:

The remaining zeroes can be allocated in 2 possible ways (alternate solution):

Making the same allocations in the original matrix:

Minimum = 11 + 7 + 17 + 12 + 13 = 60

AND

Minimum = 11 + 10 + 17 + 6 + 16 = 60