Solve the following problem :
A dairy plant has five milk tankers, I, II, III, IV & V. These milk tankers are to be used on five delivery routes A, B, C, D & E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.
I | II | III | IV | V | |
A | 150 | 120 | 175 | 180 | 200 |
B | 125 | 110 | 120 | 150 | 165 |
C | 130 | 100 | 145 | 160 | 175 |
D | 40 | 40 | 70 | 70 | 100 |
E | 45 | 25 | 60 | 70 | 95 |
How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?
Solution
Step 1: Row minimum
Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:
I | II | III | IV | V | |
A | 30 | 0 | 55 | 60 | 80 |
B | 15 | 0 | 10 | 40 | 55 |
C | 30 | 0 | 45 | 60 | 75 |
D | 0 | 0 | 30 | 30 | 60 |
E | 20 | 0 | 35 | 45 | 70 |
Step 2: Column minimum
Subtract the smallest element in each column of assignment matrix obtained in step 1 from every element in its column.
I | II | III | IV | V | |
A | 30 | 0 | 45 | 30 | 25 |
B | 15 | 0 | 0 | 10 | 0 |
C | 30 | 0 | 35 | 30 | 20 |
D | 0 | 0 | 20 | 0 | 5 |
E | 20 | 0 | 25 | 15 | 15 |
Step 3:
Draw minimum number of vertical and horizontal lines to cover all zeros. F
First cover all rows and columns which have maximum number of zeros.
I | II | III | IV | V | |
A | 30 | 0 | 45 | 0 | 25 |
B | 15 | 0 | 0 | 10 | 0 |
C | 30 | 0 | 20 | 0 | 5 |
D | 0 | 0 | 20 | 0 | 5 |
E | 20 | 0 | 25 | 15 | 15 |
Step 4:
From step 3, minimum number of lines covering all the zeros are 3, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 15 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.
I | II | III | IV | V | |
A | 15 | 0 | 30 | 15 | 10 |
B | 15 | 15 | 0 | 10 | 10 |
C | 15 | 0 | 20 | 15 | 5 |
D | 0 | 15 | 20 | 0 | 5 |
E | 5 | 0 | 10 | 0 | 0 |
Step 5:
Draw minimum number of vertical and horizontal lines to cover all zeros.
I | II | III | IV | V | |
A | 15 | 0 | 30 | 15 | 10 |
B | 15 | 15 | 0 | 10 | 0 |
C | 15 | 0 | 20 | 15 | 5 |
D | 0 | 15 | 20 | 0 | 5 |
E | 5 | 0 | 10 | 0 | 0 |
Step 6:
From step 5, minimum number of lines covering all the zeros are 4, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 5 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.
I | II | III | IV | V | |
A | 10 | 0 | 25 | 10 | 5 |
B | 15 | 20 | 0 | 10 | 0 |
C | 10 | 0 | 15 | 10 | 0 |
D | 0 | 20 | 20 | 0 | 5 |
E | 5 | 5 | 10 | 0 | 0 |
Step 7:
Draw minimum number of vertical and horizontal lines to cover all zeros.
I | II | III | IV | V | |
A | 10 | 0 | 25 | 10 | 5 |
B | 15 | 20 | 0 | 10 | 0 |
C | 10 | 0 | 15 | 10 | 0 |
D | 0 | 20 | 20 | 0 | 5 |
E | 5 | 5 | 10 | 0 | 0 |
Step 8:
From step 7, minimum number of lines covering all the zeros are 5, which is equal to order of the matrix, i.e., 5.
∴ Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:
I | II | III | IV | V | |
A | 10 | 0 | 25 | 10 | 5 |
B | 15 | 20 | 0 | 10 | 0 |
C | 10 | 0 | 15 | 10 | 0 |
D | 0 | 20 | 20 | 0 | 5 |
E | 5 | 5 | 10 | 0 | 0 |
Step 9:
The matrix obtained in step 8 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:
Routes | Dairy Plant | Distance (kms) |
A | II | 120 |
B | III | 120 |
C | V | 175 |
D | I | 40 |
E | IV | 70 |
525 |
∴ Minimum distance travelled = 120 + 120 + 175 + 40 + 70 = 525 kms.