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. Press hours! Consultan ABCD Charlie 1516 EUR Gerald 13151GE Johnny US 2120 LS Rick 0719 1222 (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)

The given problem is

A B C D Charlie 15 16 12 18 Gerald 13 | 15 | 16 | 12 Johnny 15 21 2015 Rick 1719 12 | 22

Step-1: We find each row minimum element and subtract it from that row

3 A B C D Charlie 4 06 (-12) Gerald 1 13 340 (-12) Johnny 0 6 5 50 (-15) Rick 7 010 (-12) 5

Step-2: We find each column minimum element and subtract it from that column.

B C D Charlie 3 1 0 6 Gerald 1 0 0 Johnny 0 0 3 5 50 Rick 5 4 0 10 (-0) (-3) (0) (0)

Iteration-1 of steps 3 to 6
Step-3: Make assignment in the opportunity cost table

(1) Rowwise cell (Charlie,C) is assigned, so columnwise cell (Rick,C) crossed off.
(2) Columnwise cell (Johnny,A) is assigned, so rowwise cell (Johnny,D) crossed off.
(3) Columnwise cell (Gerald,B) is assigned, so rowwise cell (Gerald,D) crossed off.

Rowwise & columnwise assignment is shown in below table

A|B|C|D Charlie 31 [0] 6 Gerald 1 [0] 4 x Johnny [0] 3 8 Rick 54 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 0
We cover the 0 with minimum number of lines

(1) Mark(✓) row Rick since it has no assignment
(2) Mark(✓) column C since row Rick has 0 in this column
(3) Mark(✓) 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,Johnny and marked columns C

We tick mark not allocated rows and allocated columns as below.

B C D Charlie 3 1 [O] 6 (3) Gerald 1 to y [O] 3 Johnny Rick 5 4 10 (1) (2)

Step-6: Develop the new revised opportunity cost table
We develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 1)
Subtract k = 1 from every element in the cell not covered by a line and we add k = 1 to every element in the intersection cell of two lines.

ABC Charlie 2005 Gerald 1 05 0 Johnny 03 6 0 Rick 4 3 0 9

Repeat steps 3 to 6 until an optimal solution is obtained.

Iteration-2 of steps 3 to 6
Step-3: Make assignment in the opportunity cost table

(1) Rowwise cell (Rick,C) 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 (Johnny,D) crossed off.
(4) Rowwise cell (Johnny,A) is assigned

Rowwise & columnwise assignment is shown in table

AB C D 5 Charlie 2 [O] Gerald 1 5 [O] Johnny 601 36 Rick 4 3 [O] 9

Step-4: Number of assignments = 4, number of rows = 4
Which is equal, so solution is optimal

Therefore, the optimal assignments are

A B C D Charlie 2 [O] 05 Gerald 1 0 5 [O] Johnny 101 360 Rick 4 3 [0] 9

b)

The optimal assignment is as below.

Consultant Project Hours Charlie B 16 Gerald D 12 Johnny 15 Rick с 12 Total 55

The total number of hours required for our optimal assignment is 55 hours.