Advertisement Remove all ads

Solve the following problem : A dairy plant has five milk tankers, I, II, III, IV and V. These milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the - Mathematics and Statistics

Sum

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?

Advertisement Remove all ads

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.

Concept: Assignment Problem
  Is there an error in this question or solution?
Advertisement Remove all ads

APPEARS IN

Balbharati Mathematics and Statistics 2 (Commerce) 12th Standard HSC Maharashtra State Board
Chapter 7 Assignment Problem and Sequencing
Part I | Q 2 | Page 128
Advertisement Remove all ads

Video TutorialsVIEW ALL [1]

Advertisement Remove all ads
Share
Notifications

View all notifications


      Forgot password?
View in app×