Question

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.

(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?

consultant	A	B	C	D
charlie	15	16	12	18
gerald	13	15	16	12
johnny	15	21	20	15
rick	17	19	12	22

Answer 1

This is the original time matrix:

15	16	12	18
13	15	16	12
15	21	20	15
17	19	12	22

Subtract row minima

We subtract the row minimum from each row:

3	4	0	6	(-12)
1	3	4	0	(-12)
0	6	5	0	(-15)
5	7	0	10	(-12)

Subtract column minima

We subtract the column minimum from each column:

3	1	0	6
1	0	4	0
0	3	5	0
5	4	0	10
	(-3)

Cover all zeros with a minimum number of lines

There are 3 lines required to cover all zeros:

3	1	0	6
1	0	4	0	x
0	3	5	0	x
5	4	0	10
		x

Create additional zeros

The number of lines is smaller than 4. The smallest uncovered number is 1. We subtract this number from all uncovered elements and add it to all elements that are covered twice:

2	0	0	5
1	0	5	0
0	3	6	0
4	3	0	9

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

2	0	0	5	x
1	0	5	0	x
0	3	6	0	x
4	3	0	9	x

The optimal assignment

Because there are 4 lines required, the zeros cover an optimal assignment:

2	0	0	5
1	0	5	0
0	3	6	0
4	3	0	9

This corresponds to the following optimal assignment in the original time matrix:

15	16	12	18
13	15	16	12
15	21	20	15
17	19	12	22

The optimal value equals 55.

Optimal assignments are A B C D CHARLIE 2 [0] 5 GERALD 1 x 5 [0] JOHNY [0] 3 6 RACK 4 3 [O] 9 Optimal solution is Work Job Cost CHARLIE 16 GERALD D 12 JOHNY 15 RACK с 12 Total 55