Question

Printed (Chinese) Name: THU ID: Class: Problem 8 (10 points) The president of a consulting firm wants to minimize the total number of hours it will take to complete four projects for a new client. Accordingly, she has estimated the time it should take for each of her top consultants-Charlie, Betty, Johnny, and Rick-to complete any of the four projects, as follows: Project (Hours) Consultant A B Charlie .-13+1 16 11 1 3 21 Betty 11, 13DV 14 - 18 - Johnny 15 : 22 1 12 . 15 2 Rick 17 -> 1790 -2 12 y 225 14 5 1225 Assume there must be one-to-one matching between consultants and projects. What is the optimal assignment of consultants to projects? 41 = 24 How many 15418412413. rt Charlie y D Betty - A Johny c Rick B mai ales Dendropletne 29+12,25 = 4.149 13111112111=53 What is the optimal cost? A: 53

Answer 1

Solution

(a) For making an assignment with an object of minimization, we have to go through the following steps,

Step-1: First we have to draw a table as follows,

Consultant	Project (Hours)
	A	B	C	D
Charlie	13	16	11	13
Betty	11	15	14	18
Johnny	15	22	12	15
Rick	17	17	12	22

Step-2: We have to make Row operations first, i.e. deduct each row value with the minimum-most value in every row. For example, in the first row “Charlie”, the lowest value is 11. Here we have to deduct 11 from each value. This operation will be followed in every row as given below,

Consultant	Project (Hours)
	A	B	C	D
Charlie	13-11 = 2	16-11 = 5	11-11 = 0	13-11 = 2
Betty	11-11 = 0	15-11 = 4	14-11 = 3	18-11 = 7
Johnny	15-12 = 3	22-12 = 10	12-12 = 0	15-12 = 3
Rick	17-12 = 5	17-12 = 5	12-12 = 0	22-12 = 10

Or,

Consultant	Project (Hours)
	A	B	C	D
Charlie	2	5	0	2
Betty	0	4	3	7
Johnny	3	10	0	3
Rick	5	5	0	10

Step-3: Now we have to make column operations, i.e. deduct each column value with the minimum-most value in every column. For example, in the first column “A”, the lowest value is 0. Here we have to deduct 0 from each value. This operation will be followed in every column as given below,

Consultant	Project (Hours)
	A	B	C	D
Charlie	2-0 = 2	5-4 = 1	0-0 = 0	2-2 = 0
Betty	0-0 = 0	4-4 = 0	3-0 = 3	7-2 = 5
Johnny	3-0 = 3	10-4 = 6	0-0 = 0	3-2 = 1
Rick	5-0 = 5	5-4 = 1	0-0 = 0	10-2 = 8

Or,

Consultant	Project (Hours)
	A	B	C	D
Charlie	2	1	0	0
Betty	0	0	3	5
Johnny	3	6	0	1
Rick	5	1	0	8

Step-4: Here we have to draw lines over the respective rows and columns, starting from the row or column having the more number of “0” given as below,

Project (Hours) Consultant ek Charlie Betty Johnny Rick

Now, for an optimal assignment, number of lines will be equal to the matrix. Here the matrix is of 4x4. So the lines drawn should be also 4. But as number of lines are 3, we need to modify the matrix values. Here the matrix values will be modified as follows,

(1) Choose the minimum-most value from the matrix over which no line has been passed. Here the value is 1. Now, 1 will be deducted from the values in the matrix over which no line has been passed, and 1 will be added with the values at the intersection points. The values under line drawn will not be modified. Table redrafted as below,

Consultant	Project (Hours)
	A	B	C	D
Charlie	2-1 = 1	1-1 = 0	0	0
Betty	0	0	3+1 = 4	5+1 = 6
Johnny	3-1 = 2	6-1 = 5	0	1
Rick	5-1 = 4	1-1 = 0	0	8

Or,

Consultant	Project (Hours)
	A	B	C	D
Charlie	1	0	0	0
Betty	0	0	4	6
Johnny	2	5	0	1
Rick	4	0	0	8

(2) Now again we have to make row and column operations once again as mentioned in Step-2 and Step-3 above. Here we are not making this once again as all the rows and columns in the matrix consists one or more “0”. Therefore, if we draw the lines once again,

M Project (Hours) Consultant < + Charlie Betty Johnny Rick Otel Adb- otel +

Now, as the number of lines drawn has been equated with the matrix, we can draw an optimal assignment as follows,

Consultant	Project (Hours)
	A	B	C	D
Charlie	1	0	0	0
Betty	0	0	4	6
Johnny	2	5	0	1
Rick	4	0	0	8

The assignment will be made in such a way that for each consultant once a value has been chosen, no other values could be chosen in that same row and column of the value which is selected. For Example, we have chosen “Project A” for “Betty” as it will be optimum. We will be unable to make any assignment in either “Project A” column, or “Betty” row. Therefore, the remaining assignments will be done in the same way.

So,

Optimal Assignment:

Charlie = D

Betty = A

Johnny = C

Rick = B

(b) Referring back to the original table,

Consultant	Project (Hours)
	A	B	C	D
Charlie	13	16	11	13
Betty	11	15	14	18
Johnny	15	22	12	15
Rick	17	17	12	22

The optimal time will be as follows,

Consultant	Project (Hours)	Values
Charlie	D	13
Betty	A	11
Johnny	C	12
Rick	B	17
Total		53

Therefore, the total rate for the optimal time of 53 hours will be the optimal cost.