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.