8 3-4

8.3-4.
The coach of an age group swim team needs to assign swimmers to a 200-yard medley relay
team to send to the Junior Olympics. Since most of his best swimmers are very fast in more than one
stroke, it is not clear which swimmer should be assigned to each of the four strokes. The five fastest
swimmers and the best times (in seconds) they have achieved in each of the strokes (for 50 yards)
are
Stroke
Backstroke
Breaststroke
Butterfly
Freestyle
Carl
37.7
43.4
33.3
29.2
Chris
32.9
33.1
28.5
26.4
David
33.8
42.2
38.9
29.6
Tony
37.0
34.7
30.4
28.5
Ken
35.4
41.8
33.6
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) Obtain an optimal solution.
Solution:
(a) Formulate this problem as an assignment problem
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstrok
e
37.7
32.9
33.8
37.0
35.4
Breastrok
e
43.4
33.1
42.2
34.7
41.8
Butterfly
Freestyle
Dummy
33.3
28.5
38.9
30.4
33.6
29.2
26.4
29.6
28.5
31.1
0
0
0
0
0
b) Obtain an optimal solution.

Subtract
smallest
number from
each
column/row
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
37.7
32.9
33.8
37.0
35.4
Breastroke
43.4
33.1
42.2
34.7
41.8
Butterfly
33.3
28.5
38.9
30.4
33.6
Freestyle
29.2
26.4
29.6
28.5
31.1
Dummy
0
0
0
0
0
Assigne
e
Column
Reduction
Check for
optimality
cover all zero
# of lines < 5
Task
Carl
Chris
David
Tony
Backstroke
4.8
0
0.9
4.1
Breastroke
10.3
0
9.1
1.6
1 of 4
Butterfly
4.8
0
10.4
1.9
Freestyle
2.8
0
3.2
2.1
Dummy
0
0
0
0
Ken
2.5
8.7
5.1
4.7
0
Subtract
smallest entry
from each
uncovered row
(0.90)
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.9
0
0
3.2
1.6
Breastroke
9.4
0
8.2
0.7
7.8
Butterfly
3.9
0
9.5
1.0
4.2
Freestyle
1.9
0
2.3
1.2
3.8
Dummy
-0.9
0
-0.9
-0.9
-0.9
Add smallest
entry 0.90 to
covered column
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.9
0
0
3.2
1.6
Breastroke
9.4
0
8.2
0.7
7.8
Butterfly
3.9
0
9.5
1.0
4.2
Freestyle
1.9
0
2.3
1.2
3.8
Dummy
0
0.9
0
0
0
Check for
optimality
cover all zeros
# of lines < 5
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.9
0
0
3.2
1.6
Breastroke
9.4
0
8.2
0.7
7.8
Butterfly
3.9
0
9.5
1.0
4.2
Freestyle
1.9
0
2.3
1.2
3.8
Dummy
0
0.9
0
0
0
Subtract
smallest entry
from each
uncovered row
(0.70)
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.2
0
-0.7
2.5
0.9
Breastroke
8.7
0
7.5
0
7.1
Butterfly
3.2
0
8.8
0.3
3.5
Freestyle
1.2
0
1.6
0.5
3.1
Dummy
-0.7
0.9
-0.7
-0.7
-0.7
Add smallest
entry 0.70 to
covered column
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.9
0.7
0
3.2
1.6
Breastroke
8.7
0
7.5
0
7.1
Assigne
Butterfly
3.2
0
8.8
0.3
3.5
Task
2 of 4
Freestyle
1.2
0
1.6
0.5
3.1
Dummy
0
1.6
0
0
0
Check for
optimality
cover all zeros

# of lines < 5
Carl
Chris
David
Tony
Ken
Backstroke
3.9
0.7
0
3.2
1.6
Breastroke
8.7
0
7.5
0
7.1
Butterfly
3.2
0
8.8
0.3
3.5
Freestyle
1.2
0
1.6
0.5
3.1
Dummy
0
1.6
0
0
0
Subtract
smallest entry
from each
uncovered row
(0.30)
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.6
0.7
0
2.9
1.3
Breastroke
8.4
0
7.5
-0.3
6.8
Butterfly
2.9
0
8.8
0
3.2
Freestyle
0.9
0
1.6
0.2
2.8
Dummy
-0.3
1.6
0
-0.3
-0.3
Add smallest
entry 0.30 to
covered column
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.6
0.7
0
2.9
1.3
Breastroke
8.7
0.3
7.8
0
7.1
Butterfly
2.9
0
8.8
0
3.2
Freestyle
0.9
0
1.6
0.2
2.8
Dummy
0
1.9
0.3
0
0
Check for
optimality
cover all zeros
# of lines < 5
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
3.6
0.7
0
2.9
1.3
Breastroke
8.7
0.3
7.8
0
7.1
Butterfly
2.9
0
8.8
0
3.2
Freestyle
0.9
0
1.6
0.2
2.8
Dummy
0
1.9
0.3
0
0
Subtract
smallest entry
from each
uncovered row
(0.90)
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
2.7
0.7
0
2.9
0.4
Breastroke
7.8
0.3
7.8
0
6.2
Assigne
e
Butterfly
2.0
0
8.8
0
2.3
Task
3 of 4
Freestyle
0
0
1.6
0.2
1.9
Dummy
-0.9
1.9
0.3
0
-0.9
Add smallest
entry 0.90 to
covered column
Carl
Chris
David
Tony
Ken
Backstroke
2.7
0.7
0
2.9
0.4
Breastroke
7.8
0.3
7.8
0
6.2
Butterfly
2.0
0
8.8
0
2.3
Freestyle
0
0
1.6
0.2
1.9
Dummy
0
2.8
1.2
0.9
0
Check for
optimality
cover all zeros
# of lines = 5
Task
Assigne
e
Carl
Chris
David
Tony
Ken
Backstroke
2.7
0.7
0
2.9
0.4
Breastroke
7.8
0.3
7.8
0
6.2
Butterfly
2.0
0
8.8
0
2.3
Since number of covered lines is 5, we can get optimal solution

Assignment:
Carl
Chris
David
Tony
Ken
Zmin
Freestyle
Butterfly
Backstroke
Breastroke
Dummy
= 29.2 + 28.5 + 33.80 + 34.7
= 126.20 seconds
4 of 4
Freestyle
0
0
1.6
0.2
1.9
Dummy
0
2.8
1.2
0.9
0

8 3-4

Uploaded by

Copyright:

Available Formats

8 3-4

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

8 3-4

Uploaded by

Copyright:

Available Formats

What is the problem being solved?

How is the problem formulated as an assignment problem?

8.3-4.

b) Obtain an optimal solution.

cover all zeros

Since number of covered lines is 5, we can get optimal solution

You might also like