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