Solve the following assignment problem for minimization :IIIIIIIVV1182419202321921201822322232021234201821191951822232221Solution :Step-I : Subtract the smallest element of each row from every element of that rowIIIIIIIVV10612421320332301342031150454…
Q.6 (C) (ii) Solve the following assignment problem for minimization :
| 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 |
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 |
[Note: the Step-I matrix is transcribed exactly as printed. Its column V entries for rows 1 and 2 are misprinted as 4 and 3; after subtracting the row minima they should be 5 and 4. The Step-II matrix below is correct.]
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. [Lines are drawn through rows 2, 3, 4 and column I.] Here minimum number of lines (4) \(\lt\) order of matrix (5).
Step-IV : 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 |
[Lines are drawn through rows 2, 4 and columns I, III.] Here minimum number of lines \(\ne\) order of matrix.
Step-VI : Find the 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 | 4 | 0 | 4 | 0 | 0 |
| 5 | 0 | 2 | 4 | 2 | 0 |
[Lines are drawn through rows 1, 4, 5 and columns III, IV. The entry in row 4, column IV is printed as 0; by the working it should be 1 (it lies on only one line in Step-V, so it is unchanged).]
Now minimum number of lines = order of matrix. The optimal assignment can be made.
Optimal solution is \(1\to\) I, \(2\to\) IV, \(3\to\square\), \(4\to\square\), \(5\to\) V
Minimum value = \(\square\)