Question

A natural truck-rental service has a surplus of one truck in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one truck in each of the cities 7, 8, 9, 10, 11 and 12. The distance(in kilometers) between the cities with a surplus and the cities with a deficit are displayed below:

		To
		7	8	9	10	11	12
From	1	31	62	29	42	15	41
	2	12	19	39	55	71	40
	3	17	29	50	41	22	22
	4	35	40	38	42	27	33
	5	19	30	29	16	20	33
	6	72	30	30	50	41	20

How should the truck be dispersed so as to minimize the total distance travelled?

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.

		To
		7	8	9	10	11	12
From	1	16	47	14	27	0	26
	2	0	7	27	43	59	28
	3	0	12	33	24	5	5
	4	8	13	11	15	0	6
	5	3	14	13	0	4	17
	6	52	10	10	30	21	0

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

		To
		7	8	9	10	11	12
From	1	16	40	4	27	0	26
	2	0	0	17	43	59	28
	3	0	5	23	24	5	5
	4	8	6	1	15	0	6
	5	3	7	3	0	4	17
	6	52	3	0	30	21	0

Step 3: Examine the rows with exactly one zero, mark the zero by □ mark other zeros, in its column by X

		To
		7	8	9	10	11	12
From	1	16	40	4	27	0	26
	2	0	0	17	43	59	28
	3	0	5	23	24	5	5
	4	8	6	1	15	0	6
	5	3	7	3	0	4	17
	6	52	3	0	30	21	0

Step 4: Examine the Columns with exactly one zero. If there is exactly one zero, mark that zero by □ mark other zeros in its rows by X

		To
		7	8	9	10	11	12
From	1	16	40	4	27	0	26
	2	0	0	17	43	59	28
	3	0	5	23	24	5	5
	4	8	6	1	15	0	6
	5	3	7	3	0	4	17
	6	52	3	0	30	21	0

Step 5: Cover all the zeros of table 4 with five lines. Since three assignments were made

		To
		7	8	9	10	11	12
From	1	16	40	4	27	0	26
	2	0	0	17	43	59	28
	3	0	5	23	24	5	5
	4	8	6	1	15	0	6
	5	3	7	3	0	4	17
	6	52	3	0	30	21	0

Step 6: Develop the new revised tableau. Examine those elements that are not covered by a line in Table 5. Take the smallest element. This is l(one) in our case. By subtracting 1 from the uncovered cells.

		To
		7	8	9	10	11	12
From	1	16	40	4	27	0	26
	2	0	0	17	43	59	28
	3	0	5	23	24	5	5
	4	8	6	1	15	0	6
	5	3	7	3	0	4	17
	6	52	3	0	30	21	0

Step 7: Go to step 3 and repeat the procedure until you arrive at an optimal assignments.

Step 8: Determine an assignment

		Depots
		7	8	9	10	11	12
From	1	16	40	4	27	0	26
	2	0	0	17	43	59	28
	3	0	5	23	24	5	5
	4	7	5	0	14	0	5
	5	3	7	3	0	4	17
	6	52	3	0	30	21	0

Here all the six assignments have been made.

The optimal assignment schedule and total distance is

From	To	Total Distance
1	11	15
2	8	19
3	7	17
4	9	38
5	10	16
6	12	20
Total		125

∴The optimum Distance (minimum) = 125 kms