Doc Councillman is putting together a relay team for the 400-meter relay. Each s
ID: 367027 • Letter: D
Question
Doc Councillman is putting together a relay team for the 400-meter relay. Each swimmer must swim 100 meters of breaststroke, backstroke, butterfly, or freestyle. Doc believes that each swimmer will attain the times given in the table below. To minimize the team’s time for the race, which swimmer should swim which stroke?
1) Use branch and bound method with global-best rule to solve the problem. Show the searching steps and the graph of the searching tree.
2) Use Hungarian method to solve the problem. Show the solution steps.
Time (seconds) Fly 51 52 54 Swimmer rea Back Gary Hall Mark Spitz Jim Montgomery Chet Jastremski 54 54 57 53 54 53 52 56 53 50 56Explanation / Answer
Hungarian method:-
Time (seconds)
Swimmer
Free
Breast
Fly
Back
Gary Hall
54
54
51
53
Mark Spitz
51
57
52
52
Jim Montgomery
50
53
54
56
Chet Jastremski
56
54
55
53
the time matrix is:
Free Breast Fly Back row min
Hall
54
54
51
53
51
Spitz
51
57
52
52
51
Montgomery
50
53
54
56
50
Jastremski
56
54
55
53
53
Applying the Hungarian Method yields
Free Breast Fly Back
Hall
3
3
0
2
Spitz
0
6
1
1
Montgomery
0
3
4
6
Jastremski
3
1
2
0
Column Min 0 1 0 0
The Reduced Cost Matrix is
Free Breast Fly Back
Hall
3
2
0
2
Spitz
0
5
1
1
Montgomery
0
2
4
6
Jastremski
3
0
2
0
Only three lines are required (we have used Row 1, Row 4 and Column 1) to cover all the 0's. Since smallest uncovered element is a 1, we subtract 1 from all uncovered costs and add 1 to all twice covered costs. The result is
Free Breast Fly Back
Hall
4
2
0
2
Spitz
0
4
0
0
Montgomery
0
1
3
5
Jastremski
4
0
2
0
Since 4 lines are required to cover all the 0's in this matrix, an optimal solution is available. One such assignment is x13=1, x24=1, x31=1, and x42=1. Thus Hall swims butterfly, Spitz swims backstroke, Montgomery swims freestyle and Jastremski swims breaststroke. z=207 seconds.
Time (seconds)
Swimmer
Free
Breast
Fly
Back
Gary Hall
54
54
51
53
Mark Spitz
51
57
52
52
Jim Montgomery
50
53
54
56
Chet Jastremski
56
54
55
53
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.