Question

Find the optimal solution for the assignment problem with the following cost matrix.

		Area
		1	2	3	4
	P	11	17	8	16
Salesman	Q	9	7	12	6
	R	13	16	15	12
	S	14	10	12	11

Answer 1

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced.

Step 1: Select the smallest element in each row and subtract this from all the elements in its row.

		Area
		1	2	3	4
	P	3	9	0	8
Salesman	Q	3	1	6	0
	R	1	4	3	0
	S	4	0	2	1

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

		Area
		1	2	3	4
	P	2	9	0	8
Salesman	Q	2	1	6	0
	R	0	4	3	0
	S	3	0	2	1

Step 3: (Assignment)
Examine the rows with exactly one zero. Mark the zero by □ Mark other zeros in its column by X

		Area
		1	2	3	4
	P	2	9	0	8
Salesman	Q	2	1	6	0
	R	0	4	3	0
	S	3	0	2	1

Thus all the four assignments have been made.

The optimal assignment schedule and total cost.

Salesman	Area	Cost
P	3	8
Q	4	6
R	1	13
S	2	10
Total		37

The Optimum cost (minimum) = ₹ 37