Question

Solve the following problem :

Solve the following assignment problem to maximize sales:

Salesman	Territories
	I	II	III	IV	V
A	11	16	18	15	15
B	7	19	11	13	17
C	9	6	14	14	7
D	13	12	17	11	13

Answer 1

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 19.

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 salesman E with zero sales.

The resulting matrix is

Salesman	Territories
	I	II	III	IV	V
A	8	3	1	4	4
B	12	0	8	6	2
C	10	13	5	5	12
D	6	7	2	8	6
E	0	0	0	0	0

Step 2: Row minimum

Subtract the smallest element in each row from every element in its row.

The matrix obtained is given below:

Salesman	Territories
	I	II	III	IV	V
A	7	2	0	3	3
B	12	0	8	6	2
C	5	8	0	0	7
D	4	5	0	6	4
E	0	0	0	0	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	Territories
	I	II	III	IV	V
A	7	2	0	3	3
B	12	0	8	6	2
C	5	8	0	0	7
D	4	5	0	6	4
E	0	0	0	0	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., 2 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.

Salesman	Territories
	I	II	III	IV	V
A	5	2	0	1	1
B	10	0	8	4	0
C	5	10	2	0	7
D	2	5	0	4	2
E	0	2	2	0	0

Step 6:

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

Salesman	Territories
	I	II	III	IV	V
A	5	2	0	1	1
B	10	0	8	4	0
C	5	10	2	0	7
D	2	5	0	4	2
E	0	2	2	0	0

Step 7:

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

Salesman	Territories
	I	II	III	IV	V
A	4	1	0	1	0
B	10	0	9	5	0
C	4	9	2	0	6
D	1	4	0	4	1
E	0	2	3	1	0

Step 8:

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

Salesman	Territories
	I	II	III	IV	V
A	4	1	0	1	0
B	10	0	9	5	0
C	4	9	2	0	6
D	1	4	0	4	1
E	0	2	3	1	0

Step 9:

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

Salesman	Territories
	I	II	III	IV	V
A	4	1	0	1	0
B	10	0	9	5	0
C	4	9	2	0	6
D	1	4	0	4	1
E	0	2	3	1	0

∴ The optimal solution is

Salesman	Territories	Sales
A	V	15
B	II	19
C	IV	14
D	III	17
E	I	0

∴ Maximum sales = 15 + 19 + 14 + 17 + 0

= 65 units.

Note that no salesman will be assigned at territory I, since it gets dummy salesman E.