# Solve the following problem : The estimated sales (tons) per month in four different cities by five different managers are given below:Find out the assignment of managers to cities in order to maxim - Mathematics and Statistics

Sum

Solve the following problem :

The estimated sales (tons) per month in four different cities by five different managers are given below:

 Manager Cities P Q R S I 34 36 33 35 II 33 35 31 33 III 37 39 35 35 IV 36 36 34 34 V 35 36 35 33

Find out the assignment of managers to cities in order to maximize sales.

#### Solution

Step 1:
The given problem is maximization problem. This can be converted to minimization problem by subtracting all the elements from the largest element which is 39.
Also, the number of rows is not equal to number of columns.
∴ It is an unbalanced assignment problem. It can be balanced by introducing a dummy city T with zero sales.
The resulting matrix is

 Manager Cities P Q R S T I 5 3 6 4 0 II 6 4 8 6 0 III 2 0 4 4 0 IV 3 3 5 5 0 V 4 3 4 6 0

Step 2: Row minimum
Here, each row contains element zero.
∴ Matrix obtained by row minimum is same as above matrix

Step 3: Column minimum
Subtract the smallest element in each column of assignment matrix obtained in step 2 from every element in its column.

 Manager Cities P Q R S T I 3 3 2 0 0 II 4 4 4 2 0 III 0 0 0 0 0 IV 1 3 1 1 0 V 2 3 0 2 0

Step 4:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.

 Manager Cities P Q R S T I 3 3 2 0 0 II 4 4 4 2 0 III 0 0 0 0 0 IV 1 3 1 1 0 V 2 3 0 2 0

Step 5:
From step 4, 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., 1 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.

 Manager Cities P Q R S T I 2 2 2 0 0 II 3 3 4 2 0 III 0 0 1 1 1 IV 0 2 1 1 0 V 1 2 0 2 0

Step 6:
Draw minimum number of vertical and horizontal lines to cover all zeros.

 Manager Cities P Q R S T I 2 2 2 0 0 II 3 3 4 2 0 III 0 0 1 1 1 IV 0 2 1 1 0 V 1 2 0 2 0

Step 7:
From step 6, 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:

 Manager Cities P Q R S T I 2 2 2 0 0 II 3 3 4 2 0 III 0 0 1 1 1 IV 0 2 1 1 0 V 1 2 0 2 0

∴ The optimal solution is

 Manager Cities Sales (tons) I S 35 II T 0 III Q 39 IV P 36 V R 35

∴ Maximum sales 35 + 0 + 39 + 36 + 35 = 145 tons.

Is there an error in this question or solution?

#### APPEARS IN

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