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) A 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) (6) What is the optimal assignment? What is the total number of hours required by your optimal assignment?

Answer 1

The values are written as below:

Step-1: Find out the each row minimum element and subtract it from that row A B C D CHARLIE 3 4 0 6 (-12) GERALD 1 3 4 0 (-12) 0 6 5 0 (-15) 5 7 0 10 (-12) JOHNY RACK Step-2: Find out the each column minimum element and subtract it from that column. 1 CHARLIE 3 1 0 6 GERALD 0 JOHNY 0 3 5 0 RACK 5 4 0 | (-0) (-3) (-0)| (-0) 10 Iteration-1 of steps 3 to 6 + Step-3. Make assignment in the opporunity cost table Step-3: Make assignment in the opporunity cost table (1) Rowwise cell (CHARLIE, C) is assigned, so columnwise cell(RACK ) crossed off. (2) Columnwise cell (JOHNY. 4) is assigned, so rowwise cell (JOHNY,D) crossed off. (3) Columnwise cell (GERALD. B) is assigned, so rowwise cell (GERALD. D) crossed off. RowWise & columnwise assignment shown in table A B C D CHARLIE 3 1 0 6 GERALD 1 04 X JOHNY [O] 3 5 x RACK 5 4 6 10

Step-4 Number of assignments = 3 number of rows = 4 Which is not equal, so solution is not optimal + Step-5 Draw a set of horizontal and vertical lines to cover all the Step-5. Cover the with minimum number of lines (1) Markrow RACK since has no assignment (2) Mark column C since row RACK has o in this column (3) Mark 7) row CHARLIE since column C has an assignment in this row CHARLIE. (4) Since no other rows or columns can be marked, therefore draw straight lines through the unmarked rows GERALD, JORNY and marked columns Tick mark not allocated rows and allocated columns CHARLIE GERALD 101 TOHNY to RACK 5 12) + Step 6. Develop the new revised opportunity coettable Stop-: Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say - 1) Subtract k-1 from every element in the cel not covered by a ine. Add = 1 to every elment in the intersection cell of two lines. A B C D CHARLIE 2005 GERALD JOHNY 03 60 BACK 9

Iteration : 1 Iteration 2 of steps 3 to 6 Step-3. Make assignment in the opporunity cost table (1) Rowwise cell (RACK, ) is assigned, so columnwise cell (CHARLIE, C) crossed off. (2) Rowwise cell (CHARLIE, B) is assigned, so columnwise cell (GERALD. B) crossed off. (3) Rowwise cell (GERALD, D) is assigned, so columnwise cell (JOHNY, D) crossed off. (4) Rowwise cell (JOHNY, 4) is assigned Rowwise & columnwise assignment shown in table CHARLIE 205 GERALD 1 5 [0] JOHNY O3 6 x 4 3 [O] 9 RACK Step-4: Number of assignments = 4, number of rows = 4 Which is equal, so solution is optimal Optimal assignments are A B C D CHARLIE 2 to 5 GERALD 1 5 [] JOHNY 0 3 6 x 4 3 0 9 RACK Optimal solution is Work Job Cost CHARLIE B 16 GERALD D 12 JOHNY 15 RACK 12 Total 55