Question

Assign four trucks 1, 2, 3 and 4 to vacant spaces A, B, C, D, E and F so that distance travelled is minimized. The matrix below shows the distance.

	1	2	3	4
A	4	7	3	7
B	8	2	5	5
C	4	9	6	9
D	7	5	4	8
E	6	3	5	4
F	6	8	7	3

Answer 1

Since the number of columns is less than the number of rows, the given assignment problem is unbalanced one.

To balance it, introduce two dummy columns with all the entries zeros.

The revised assignment problem is

		Trucks
		1	2	3	4
	A	4	7	3	7
	B	8	2	5	5
Vacant Spaces	C	4	9	6	9
	D	7	5	4	8
	E	6	3	5	4
	F	6	8	7	3

Here only 4 tasks can be assigned to 4 vacant spaces.

Step 1: It is not necessary, since each row contains zero entry. Go to step 2.

		Trucks
		1	2	3	4	d1	d2
	A	0	5	0	4	0	0
	B	4	0	2	2	0	0
Vacant Spaces	C	0	7	3	6	0	0
	D	3	3	1	5	0	0
	E	2	1	2	1	0	0
	F	2	6	4	0	0	0

Step 3: (Assignment)
Since each row contains more than one zeros. Go to step 4.

Step 4: Examine the columns with exactly one zero, mark the zero by □ Mark other zeros in its rows by X.

		Trucks
		1	2	3	4	d1	d2
	A	0	5	0	4	0	0
	B	4	0	2	2	0	0
Vacant Spaces	C	0	7	3	6	0	0
	D	3	3	1	5	0	0
	E	2	1	2	1	0	0
	F	2	6	4	0	0	0

		Trucks
		1	2	3	4	d1	d2
	A	0	5	0	4	0	0
	B	4	0	2	2	0	0
Vacant Spaces	C	0	7	3	6	0	0
	D	3	3	1	5	0	0
	E	2	1	2	1	0	0
	F	2	6	4	0	0	0

Step 5: Here all the four assignments have been made we can assign d₁ for D then we will get d₂ for E.

		Trucks
		1	2	3	4	d1	d2
	A	0	5	0	4	0	0
	B	4	0	2	2	0	0
Vacant Spaces	C	0	7	3	6	0	0
	D	3	3	1	5	0	0
	E	2	1	2	1	0	0
	F	2	6	4	0	0	0

The optimal assignment schedule and total distance is

Vacant	Trucks	Total distances
A	3	3
B	2	2
C	1	4
D	d1	0
E	d2	0
F	4	3
Total		12

∴ The Optimum Distant (minimum) = 12 units.