Question

Five wagons are available at stations 1, 2, 3, 4 and 5. These are required at 5 stations I, II, III, IV and V. The mileage between various stations are given in the table below. How should the wagons be transported so as to minimize the mileage covered?

	I	II	III	IV	V
1	10	5	9	18	11
2	13	9	6	12	14
3	7	2	4	4	5
4	18	9	12	17	15
5	11	6	14	19	10

Answer 1

Step 1: Row minimum

Subtract the smallest element is each row from every element of that row.

Wagons	Mileage of Sations
	I	II	III	IV	V
1	5	0	4	13	6
2	7	3	0	6	8
3	5	0	2	2	3
4	9	0	3	8	6
5	5	0	8	13	4

Step 2: Column minimum

Subtract the smallest element of each column from every element of that column.

Wagons	Mileage of Sations
	I	II	III	IV	V
1	0	0	4	11	3
2	2	3	0	4	5
3	0	0	2	0	0
4	4	0	3	6	3
5	0	0	8	11	1

The number of lines covering all zeroes (4) is not equal to order of matrix (5). So solution has not reached.

Step 3: Therefore, subtract the smallest uncovered element (i) from all uncovered elements and add it to all elements which lie at the intersection of two unchanged:

Wagons	Mileage of Sations
	I	II	III	IV	V
1	0	0	4	10	2
2	2	3	0	3	4
3	1	1	3	0	0
4	4	0	3	5	2
5	0	0	8	10	0

The number of lines covering all zeroes is equal to order of matrix.

Step 4: Hence, optimal solution has reached. Therefore, the optimal assignment is made as follows:

Wagons	Mileage of Sations
	I	II	III	IV	V
1	0	0	4	10	2
2	2	3	0	3	4
3	1	1	3	0	0
4	4	0	3	5	2
5	0	0	8	2	0

The optimal assignment is shown as follows:

Wagons	Station	Miles
1	I	10
2	III	6
3	IV	4
4	II	9
5	V	10

The minimum milage covered = 10 + 6 + 4 + 9 + 10 = 39 miles.