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 Answer
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:

enter image description here

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

enter image description here

Number of lines = 3 < order of matrix = 5

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

enter image description here

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

enter image description here

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

enter image description here

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:

enter image description here

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

enter image description here

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

enter image description here

Making the same allocations in the original matrix:

enter image description here

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

AND

enter image description here

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

Please log in to add an answer.

Continue reading...

The best way to discover useful content is by searching it.

Search