Advertisements
Advertisements
Question
Solve the following assignment problem to maximization:
| I | II | III | IV | V | |
| 1 | 18 | 24 | 19 | 20 | 23 |
| 2 | 19 | 21 | 20 | 18 | 22 |
| 3 | 22 | 23 | 20 | 21 | 23 |
| 4 | 20 | 18 | 21 | 19 | 19 |
| 5 | 18 | 22 | 23 | 22 | 21 |
Step - I
Subtract the Smallest element of each row from every element of that row
| I | II | III | IV | V | |
| 1 | 0 | 6 | 1 | 2 | 4 |
| 2 | 1 | 3 | 2 | 0 | 3 |
| 3 | 2 | 3 | 0 | 1 | 3 |
| 4 | 2 | 0 | 3 | 1 | 1 |
| 5 | 0 | 4 | 5 | 4 | 3 |
Step - II
Subtract the smallest element of each column from every element of that column:
| I | II | III | IV | V | |
| 1 | 0 | 6 | 1 | 2 | 4 |
| 2 | 1 | 3 | 2 | 0 | 3 |
| 3 | 2 | 3 | 0 | 1 | 2 |
| 4 | 2 | 0 | 3 | 1 | 0 |
| 5 | 0 | 4 | 5 | 4 | 2 |
Step - III
Draw minimum number of lines covering all zeros.
| I | II | III | IV | V | |
| 1 | 0 | 6 | 1 | 2 | 4 |
| 2 | 1 | 3 | 2 | 0 | 3 |
| 3 | 2 | 3 | 0 | 1 | 2 |
| 4 | 2 | 0 | 3 | 1 | 0 |
| 5 | 0 | 4 | 5 | 4 | 2 |
Step - 1V
The smallest uncovered element is 1, which is to be subtracted from all uncovered elements and add it to all elements which lie at the intersection of two lines:
| I | II | III | IV | V | |
| 1 | 0 | 5 | 0 | 3 | |
| 2 | 2 | 3 | 2 | 0 | 3 |
| 3 | 3 | 3 | 0 | 2 | |
| 4 | 3 | 0 | 3 | 1 | 0 |
| 5 | 0 | 3 | 4 | 3 |
Step - V
Draw minimum number of lines that are required to cover all zeros:
| I | II | III | IV | V | |
| 1 | 0 | 5 | 0 | 1 | 3 |
| 2 | 2 | 3 | 2 | 0 | 3 |
| 3 | 3 | 3 | 0 | 1 | 2 |
| 4 | 3 | 0 | 3 | 1 | 0 |
| 5 | 0 | 3 | 4 | 3 | 1 |
Here minimum number of Lines = order of matrix.
Step - VI
Find smallest uncovered element (1). Subtract this number from all uncovered elements and add it to all elements which lie at the intersection of two lines:
| I | II | III | IV | V | |
| 1 | 0 | 4 | 0 | 0 | 2 |
| 2 | 3 | 3 | 3 | 0 | 3 |
| 3 | 3 | 0 | 0 | ||
| 4 | 3 | 0 | 3 | 1 | 0 |
| 5 | 0 | 2 | 4 | 3 | 0 |
Now minimium number of lines = order of matrix.
The optimal assignment can be made.
Optimal solution is
1 → I
2 → IV
3 → `square`
4 → `square`
5 → V
Minimum value = `square`
Solution
Step - I
Subtract the Smallest element of each row from every element of that row
| I | II | III | IV | V | |
| 1 | 0 | 6 | 1 | 2 | 4 |
| 2 | 1 | 3 | 2 | 0 | 3 |
| 3 | 2 | 3 | 0 | 1 | 3 |
| 4 | 2 | 0 | 3 | 1 | 1 |
| 5 | 0 | 4 | 5 | 4 | 3 |
Step - II
Subtract the smallest element of each column from every element of that column:
| I | II | III | IV | V | |
| 1 | 0 | 6 | 1 | 2 | 4 |
| 2 | 1 | 3 | 2 | 0 | 3 |
| 3 | 2 | 3 | 0 | 1 | 2 |
| 4 | 2 | 0 | 3 | 1 | 0 |
| 5 | 0 | 4 | 5 | 4 | 2 |
Step - III
Draw minimum number of lines covering all zeros.
| I | II | III | IV | V | |
| 1 | 0 | 6 | 1 | 2 | 4 |
| 2 | 1 | 3 | 2 | 0 | 3 |
| 3 | 2 | 3 | 0 | 1 | 2 |
| 4 | 2 | 0 | 3 | 1 | 0 |
| 5 | 0 | 4 | 5 | 4 | 2 |
Step - 1V
The smallest uncovered element is 1, which is to be subtracted from all uncovered elements and add it to all elements which lie at the intersection of two lines:
| I | II | III | IV | V | |
| 1 | 0 | 5 | 0 | 1 | 3 |
| 2 | 2 | 3 | 2 | 0 | 3 |
| 3 | 3 | 3 | 0 | 1 | 2 |
| 4 | 3 | 0 | 3 | 1 | 0 |
| 5 | 0 | 3 | 4 | 3 | 1 |
Step - V
Draw minimum number of lines that are required to cover all zeros:
| I | II | III | IV | V | |
| 1 | 0 | 5 | 0 | 1 | 3 |
| 2 | 2 | 3 | 2 | 0 | 3 |
| 3 | 3 | 3 | 0 | 1 | 2 |
| 4 | 3 | 0 | 3 | 1 | 0 |
| 5 | 0 | 3 | 4 | 3 | 1 |
Here minimum number of Lines = order of matrix.
Step - VI
Find smallest uncovered element (1). Subtract this number from all uncovered elements and add it to all elements which lie at the intersection of two lines:
| I | II | III | IV | V | |
| 1 | 0 | 4 | 0 | 0 | 2 |
| 2 | 3 | 3 | 3 | 0 | 3 |
| 3 | 3 | 2 | 0 | 0 | 1 |
| 4 | 3 | 0 | 3 | 1 | 0 |
| 5 | 0 | 2 | 4 | 3 | 0 |
Now minimium number of lines = order of matrix.
The optimal assignment can be made.
Optimal solution is
1 → I (Value = 18)
2 → IV (Value = 18)
3 → III (Value = 20)
4 → II (Value = 18)
5 → V (Value = 21)
Minimum value = 18 + 18 + 20 + 18 + 21 = 95
∴ Minimum value = 95
