Question

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.

Answer 1

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. Hence optimal solution has reached.
∴ 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:

∴  The optimal solution is:

Salesman	District	Profit (in ₹)
A	1	16
B	3	15
C	2	15
D	4	15

∴ The maximum profit = 16 + 15 + 15 + 15 = ₹ 61.