Question

4. 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, Gerald, Johnny, and Rick -- to complete any of the four projects, as indicated in the table below. Consultant Charlie Gerald Johnny Rick Project (hours) А B 15 16 13 15 15 21 17 19 с 12 16 20 12 D 18 12 15 22 (a) Find the optimal assignment such that the total number of hours is minimized. (Show your table in each step) (b) What is the optimal assignment? What is the total number of hours required by your optimal assignment?

Answer 1

(a)

Optimal assignment is determined using Hungarian method as shown below step-by-step

Hungarian Method Cons. Charlie Gerald Johnny Rick A 15 13 15 17 Project (hours) B с 16 12 15 16 20 19 12 D 18 12 15 22 21 Step 1: Row reduction - Subtract the smallest element in each row from every element in that row A B с D Charlie 3 4 0 6 Gerald 1 3 4 0 Johnny 0 6 5 0 Rick 5 7 0 10 Step 2: Column reduction - Subtract the smallest element in each column from every element in that column A B с D Charlie 3 6 Gerald 1 0 4 0 Johnny 0 3 5 0 Rick 5 4 0 10 1 0

Step 3: Now we test whether it is possible to make an assignment using only zero distances. (a) Starting with row 1 of the matrix, we examine rows one by one until a row containing exactly single zero elements are found. We make an experimental assignment to that cell. Then we cross all other zeros in the column in which the assignment was made. (b) When the set of rows has been completely examined an identical procedure is applied successively to columns. Starting with Column 1, we examine columns until a column containing exactly one remaining zero is found. We make an experimental assignment in that position and cross other zeros in the row in which the assignment was made. It is found that no additional assignments are possible. Thus, we have the complete Zero assignment с B 1 A 3 1 0 5 D 6 0 Charlie Gerald Johnny Rick 4 5 3 4 0 10

--------------------------------------------------------------------------------

(b)

Optimal assignment of consultants to projects

Consultant	Project	Time (hours)
Charlie	B	16
Gerald	D	12
Johnny	A	15
Rick	C	12
Total time		55

Total number of hours required by optimal assignment = 55 hours