Question

On Transportation and Assignment:

Mega Laundry has 3 laundrywomen and 3 branches. The company pays for the transportation expenses of these laundrywomen to their shop. As such, the company wishes to know the most economical assignment of laundrywomen to branches. Data about their fare is as follows: Angela Benedetta Chang'e 1 11 8 9 2 14 10 12 3 6 11 7 What assignment will yield the minimum total fare for the three laundrywomen?

Answer 1

Given data :

	1	2	3
Angela	11	14	6
Benedetta	8	10	11
Chang'e	9	12	7

Step I : Subtracting the minimum element of each row in the cost matrix from all elements of the respective row we get,

	1	2	3
Angela	5	8	0
Benedetta	0	2	3
Chang'e	2	5	0

Step II : Subtracting the minimum element of each column in the cost matrix from all elements of the respective column we get,

	1	2	3
Angela	5	6	0
Benedetta	0	0	3
Chang'e	2	3	0

Step III : Drawing the least possible number of horizontal and vertical lines to cover all the zeros of the cost matrix we get,

1 2 3 5 6 Angela Benedetta Chang'e o o 2 3

Step IV : Since the number of lines ,i.e, 2 is not equal to the order of the matrix ,i.e., 3, then the smallest of the uncrossed element ,i.e., 2 will be subtracted from the uncrossed elements in the cost matrix. Then we get,

	1	2	3
Angela	3	4	0
Benedetta	0	0	3
Chang'e	0	1	0

Step V : Drawing the least possible number of horizontal and vertical lines to cover all the zeros of the cost matrix we get,

1 2 3 B 4 P Angela Benedetta Chang'e (0 1 O

Step VI : Marking this zeros with 0 as an assignment will be made there we get,

	1	2	3
Angela	3	4	0
Benedetta	0	0	3
Chang'e	0	1	0

Therefore, the optimal assignment is :

Angela $\rightarrow$ 3

Bendetta $\rightarrow$ 2

Chang'e $\rightarrow$ 1

And, the minimum total fare is = (6+10+9) = 25.