Solve the following assignment problem (Profits in ‘000 Rs)

The hyphens indicate that there is zero profit in those cells.

Converting the problem to a minimization problem, by considering the difference between the largest element in the whole matrix, and each other element:

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

• Subtracting the smallest element from each row, from all the other row 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. However, 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:

Every row and column has an allocation.

Making the same allocation in the original matrix:

Maximum profit = 18 + 10 + 13 + 22 + 17 = Rs. 80000