A company has a team of four salesmen and there are four districts where the company wants to start its business. After taking into account the capabilities of salesmen and the nature of districts, the company estimates that the profit per day in rupees for each salesman in each district is as below:
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 16 | 10 | 12 | 11 |
| B | 12 | 13 | 15 | 15 |
| C | 15 | 15 | 11 | 14 |
| D | 13 | 14 | 14 | 15 |
Find the assignment of salesman to various districts which will yield maximum profit.
Solution
Step 1:
Since it is a maximization problem, subtract each of the elements in the table from the largest element, i.e., 16
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 4 | 3 | 1 | 1 |
| C | 1 | 1 | 5 | 2 |
| D | 3 | 2 | 2 | 1 |
Step 2:
Row minimum Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 3 | 2 | 0 | 0 |
| C | 0 | 0 | 4 | 1 |
| D | 2 | 1 | 1 | 0 |
Step 3:
Column minimum Here, each column contains element zero.
∴ Matrix obtained by column minimum is same as above matrix.
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.
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 3 | 2 | 0 | 0 |
| C | 0 | 0 | 4 | 1 |
| D | 2 | 1 | 1 | 0 |
Step 5:
From step 4, minimum number of lines covering all the zeros are 4, which is equal to order of the matrix, i.e., 4.
∴ 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:
| Salesman | District | |||
| 1 | 2 | 3 | 4 | |
| A | 0 | 6 | 4 | 5 |
| B | 3 | 2 | 0 | 0 |
| C | 0 | 0 | 4 | 1 |
| D | 2 | 1 | 1 | 0 |
Step 6:
The matrix obtained in step 5 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:
| Salesman | District | Profit (in ₹) |
| A | 1 | 16 |
| B | 2 | 15 |
| C | 3 | 15 |
| D | 4 | 15 |
∴ The maximum profit = 16 + 15 + 15 + 15 = ₹ 61.
