Question

1. The coach of a swim team needs to assign swimmers to a 200-yard medley relay team to send to an intercollegiate event. Since most of her best swimmers are very fast in more than one stroke, it is unclear which swimmer should be assigned to each of the four strokes. The five fastest swimmers and the best times in secs) that they have achieved in each of the strokes (for 50 yards) are as below: Dalstrolo 37.7 Stroke Backstroke Breaststroke Butterfly Freestyle Lloyd Morgan Solo Dunn Mewis 32.9 33.8 37.0 35.4 43.4 33.1 42.2 34.7 41.8 33.3 28.5 38.9 30.4 33.6 29.2 26.4 29.6 28.5 31.1 The coach wishes to determine how to assign four swimmers to the four different strokes to minimize the sum of the corresponding best times. (a) Formulate this problem as an assignment problem. (b) Solve the assignment problem using the Hungarian method.

1. The coach of a swim team needs to assign swimmers to a 200-yard medley relay team to send to an intercollegiate event. Since most of her best swimmers are very fast in more than one stroke, it is unclear which swimmer should be assigned to each of the four strokes. The five fastest swimmers and the best times (in secs) that they have achieved in each of the strokes (for 50 yards) are as below:

The coach wishes to determine how to assign four swimmers to the four different strokes to minimize the sum of the corresponding best times. (a) Formulate this problem as an assignment problem. (b) Solve the assignment problem using the Hungarian method.

PLEASE SHOW WORK

Answer 1

(a)

Swimmer \ Stroke	Backstroke	Breaststroke	Butterfly	Freestyle	Dummy	Supply
Lloyd	37.7	43.4	33.3	29.2	0	1
Morgan	32.9	33.1	28.5	26.4	0	1
Solo	33.8	42.2	38.9	29.6	0	1
Dunn	37.0	34.7	30.4	28.5	0	1
Mexis	35.4	41.8	33.6	31.1	0	1
Demand	1	1	1	1	1

(b)

Step-1: Subtract minimums from each row

	Backstroke	Breaststroke	Butterfly	Freestyle	Dummy
Lloyd	37.7	43.4	33.3	29.2	0
Morgan	32.9	33.1	28.5	26.4	0
Solo	33.8	42.2	38.9	29.6	0
Dunn	37.0	34.7	30.4	28.5	0
Mexis	35.4	41.8	33.6	31.1	0

Step-2: Subtract minimums from each column

	Backstroke	Breaststroke	Butterfly	Freestyle	Dummy
Lloyd	4.8	10.3	4.8	2.8	0
Morgan	0.0	0	0	0	0
Solo	0.9	9.1	10.4	3.2	0
Dunn	4.1	1.6	1.9	2.1	0
Mexis	2.5	8.7	5.1	4.7	0

Step-3: Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines

Dummy Lloyd Morgan Solo Backstroke Breaststroke 4.8 10.3 –8. 9.1 Butterfly 4.8 -0.8 10.4 1.9 5.1 Freestyle 2.8 8. 3.2 0.9 % Dunn A ។ Mexis 3.1. 4.7 ៖

Since the number of lines = 2 which is less than the number of assignments i.e. 5, we are yet to reach the optimality condition.

Step-4: Note the smallest entry not covered by any line (0.9). Subtract 0.9 from each uncovered row.

	Backstroke	Breaststroke	Butterfly	Freestyle	Dummy
Lloyd	3.9	9.4	3.9	1.9	-0.9
Morgan	0.0	0.0	0.0	0.0	0.0
Solo	0.0	8.2	9.5	2.3	-0.9
Dunn	3.2	0.7	1.0	1.2	-0.9
Mexis	1.6	7.8	4.2	3.8	-0.9

Step-5: Add 0.90 to each covered column. Then repeat Step-3

Freestyle Backstroke Breaststroke 9.4 Lloyd Butterfly 3.9 0.0 9.5 mo 0.0 8.2 Morgan Solo Dunn Mexis 2.3

Still the number of lines < 5, so, we have to repeat Step-4 and 5.

So, note the smallest entry not covered by any line (0.7). Subtract 0.7 from each uncovered row.

Breaststroke Backstroke 3.2 0.0 -0.7 Butterfly 3.2 0.0 Lloyd Morgan Solo Dunn Mexis Freestyle 1.2 0.0 1.6 Dummy -0.7 0.9 -0.7 -0.7 -0.7 7.5 0.9 7.1 3.5 3.1

Add 0.7 to each covered column. Then repeat Step-3

Backstroke Breaststroke Freestyle Dummy Lloyd Butterfly 3.2 0.0 1.2 0.0 Morgan Solo Dunn Mexis OOM 1.6

Still the number of lines < 5, so, we have to repeat Step-4 and 5.

So, note the smallest entry not covered by any line (0.3). Subtract 0.3 from each uncovered row.

Breaststroke Butterfly Backstroke 3.6 8.4 2.9 0.0 Freestyle 0.9 0.0 1.3 Lloyd Morgan Solo Dunn Mexis 0.7 Dummy -0.3 1.6 -0.3 0.0 8.5 -0.3 -0.3 0.3 6.8 3.2 2.8 -0.3

Add 0.3 to each covered column. Then repeat Step-3

Freestyle Lloyd Backstroke Breaststroke 3.9 1.0 0.0 Butterfly 2.9 0.0 8.5 0.0 0.9 0.0 Dummy 0.0 1.9 0.0 Morgan Solo Dunn Mexis 1.3 3.2 2.8

Still the number of lines < 5, so, we have to repeat Step-4 and 5.

So, note the smallest entry not covered by any line (0.9). Subtract 0.9 from each uncovered row.

Freestyle 7.8 0.0 Backstroke Breaststroke 3.0 0.3 -0.9 0.0 Butterfly 2.0 0.0 7.6 Lloyd Morgan Solo Dunn Mexis 1.0 0.0 Dummy -0.9 1.9 -0.9 0.0 -0.9 6.6 0.4 0.2 3.2 0.0 0.7 6.2 2.3

Add 0.9 to each covered column. Then repeat Step-3

Dummy Backstroke Breaststroke 3.9 1.9 Butterfly 2.0 Lloyd 0.0 0.0 2.8 0.0 Morgan Solo Dunn Mexis 0.0 2.3

Now, the number of lines=5 and hence this can be converted into an optimal assignment by marking the position of the zeros as an assignment. Note that first mark the unique zeros. So, for example, Mexis has only one zero at the Dummy. So, mark that.

So, the optimal assignment is as follows:

Backstroke Breaststroke Freestyle Lloyd 3.9 7.8 0.3 1.9 0 Butterfly 2.0 0 7.6 0.0 0.0 0.4 Morgan Solo Dunn Mexis Dummy 0.0 2.8 0.0 0.9 0 6.6 4.1 0.2 1.6 6.2 1.9

Lloyd - Freestyle
Morgan - Butterfly
Solo - Backstroke
Dunn - Breaststroke

Total minimum time = 29.2+28.5+33.8+34.7 = 126.2 seconds