/ / 1Winston Chapter 7.5, Page 379, Number 2 (Assignment)
Problem Statement: 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 Table 51. To minimize the team’s time for the race, which swimmer should swim which stroke? Solve the problem manually.
Table 51: / Time (seconds)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*
First, the difference between each value in each cell (above) and the minimum value in each row (above) is found, as shown below:
Time (seconds)Free / Breast / Fly / Back
54 – 51 = / 54 – 51 = / 51 – 51 = / 53 – 51 =
Gary Hall / 3 / 3 / 0 / 2
51 – 51 = / 57 – 51 = / 52 – 51 = / 52 – 51 =
Mark Spitz / 0 / 6 / 1 / 1
50 – 50 = / 53 – 50 = / 54 – 50 = / 56 – 50 =
Jim Montgomery / 0 / 3 / 4 / 6
56 – 53 = / 54 – 53 = / 55 – 53 = / 53 – 53 =
Chet Jastremski / 3 / 1 / 2 / 0
Second, the difference between each value in each cell (above) and the minimum value in each column is found, as shown below:
Time (seconds)Free / Breast / Fly / Back
3 – 0 = / 3 – 1 = / 0 – 0 = / 2 – 0 =
Gary Hall / 3 / 2 / 0 / 2
0 – 0 = / 6 – 1 = 5 / 1 – 0 = / 1 – 0 =
Mark Spitz / 0 / 5 / 1 / 1
0 – 0 = / 3 – 1 = / 4 – 0 = / 6 – 0 =
Jim Montgomery / 0 / 2 / 4 / 6
3 – 0 = / 1 – 1 = / 2 – 0 = / 0 – 0 =
Chet Jastremski / 3 / 0 / 2 / 0
Then, to determine whether or not this matrix will give an optimal solution, a minimum number of lines will be drawn through all zeros, as shown below. Since a minimum of three lines can be drawn, but four columns and rows exist, this is not an optimal matrix.
Time (seconds)Free / Breast / Fly / Back
/ Gary Hall / 3 / 2 / 0 / 2
Mark Spitz / 0 / 5 / 1 / 1
Jim Montgomery / 0 / 2 / 4 / 6
/ Chet Jastremski / 3 / 0 / 2 / 0
Since the above was not an optimal matrix, the values that are not covered by lines are subtracted by the minimum value of all cells not covered. In the case above, the minimum value of all non-covered values is one. As well, all non-covered values are reduced by a value of one and values under lines that intersect are increased by a value of one. The results are shown below.
Time (seconds)Free / Breast / Fly / Back
Gary Hall / 4 / 2 / 0 / 2
Mark Spitz / 0 / 4 / 0 / 0
Jim Montgomery / 0 / 1 / 3 / 5
Chet Jastremski / 4 / 0 / 1 / 0
Again, to determine whether or not this matrix will give an optimal solution, a minimum number of lines will be drawn through all zeros, as shown below. Since a minimum of four lines can be drawn and four columns and rows exist, this is indeed an optimal matrix.
Time (seconds)Free / Breast / Fly / Back
/ Gary Hall / 4 / 2 / 0 / 2
/ Mark Spitz / 0 / 4 / 0 / 0
/ Jim Montgomery / 0 / 1 / 3 / 5
/ Chet Jastremski / 4 / 0 / 1 / 0
Since the above matrix is an optimal matrix, an optimal solution can be found by trial and error. To find a solution, each row’s an each column’s capacity must be used once and only once while allowing the rows and columns to intersect over cells with values of zero. Once a row and column are used to make one intersection, neither row nor column can be used again to intersect over another zero value. The solution to the problem is found when all rows and all columns are intersecting once and only once above cells with a value of zero. The optimal solution is found below after completing this trial and error method.
Time (seconds)Free / Breast / Fly / Back /
Capacity Used?
Gary Hall / 4 / 2 / [ 0 ] / 2 / XMark Spitz / 0 / 4 / 0 / [ 0 ] / X
Jim Montgomery / [ 0 ] / 1 / 3 / 5 / X
Chet Jastremski / 4 / [ 0 ] / 1 / 0 / X
Capacity Used?
/ X / X / X / XThus, a solution for Doc Councillman to consider for minimizing the team’s time for the race is as follows:
Since each swimmer must swim 100 meters of breaststroke, backstroke, butterfly, or freestyle and each swimmer must swim one and only one stroke,
- Jim Montgomery should swim the freestyle and can be completed in 50 seconds.
- Chet Jastremski should swim the breaststroke and can be completed in 54 seconds.
- Mark Spitz should swim the backstroke and can be completed in 52 seconds.
- Gary Hall should swim the butterfly and can be completed in 51 seconds.
This combination will allow the team to complete the 400-meter relay in the minimum time possible which is approximately 207 seconds or 3 minutes and 27 seconds.