Question

A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins) and the towers(destinations) where the customers are given in the following distance matrix.

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105

How should the cars be assigned to the customers so as to minimize the 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.

		Depots
		a	b	c	d	e
	A	30	0	45	60	70
	B	15	0	10	40	55
Customers	C	30	0	45	60	75
	D	0	0	30	30	60
	E	20	0	35	45	70

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

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	20
	D	0	0	20	0	5
	E	20	0	25	15	15

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

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	20
	D	0	0	20	0	5
	E	20	0	25	15	15

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

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	20
	D	0	0	20	0	5
	E	20	0	25	15	15

Step 5: Cover all the zeros of table 4 with three lives.

Since three assignments were made please note that check [✓] Row C and E which have no assignment.

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C✓	30	0	35	30	20
	D	0	0	20	0	5
	E✓	20	0	25	15	15

Step 6: Develop the new revised tableau. Examine those elements that are not covered by a line in Table 5.

Take the smallest element in each row and subtract from the uncovered cells, depots

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	0
	D	0	0	20	0	5
	E	20	0	25	0	0

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

Step 8: Determine an assignment

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	0
	D	0	0	20	0	5
	E	20	0	25	0	0

Here all the five assignments have been made.

The optimal assignment schedule and total distance is

Customers	Depots	Total Distances
A	b	130
B	c	130
C	e	185
D	a	50
E	d	80
Total		575

∴ The optimum Distance (minimum) is 575 kms.