Question

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.

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