-1

Given a table of personal best records of 5 people in 4 different swimming styles (freestyle stroke, backstroke, breaststroke, butterfly stroke) how can I choose 4 out of 5 said swimmers for an upcoming competition (Using Linear Programming).

There are many ways I can approach this question but none of them seem to be related to linear algebra in any way, I feel like this question is more related to probability.

First I tried to choose based on their total average, then I tried to choose the guy most likely to get the most losses, But as I said before none of them seem to be related to linear algebra.

any help will be appreciated.

Shubham Johri
  • 17,659
nothatcreative5
  • 343
  • 1
    What are the requirements of the competition? One race for each stroke? Do each of the swimmers have to race in all four strokes? Are there different distances involved? – jlammy Jan 11 '21 at 17:09
  • Those are good questions. But unfortunately we are given no information on how the swimmers compete in the race. – nothatcreative5 Jan 11 '21 at 17:15
  • Without further assumptions, then there's very little we can say. To wit, we can't optimise something when we don't know what we're optimising for! For example, say one of the swimmers was extremely good at breaststroke, but weaker on the other strokes (in comparison to the other four swimmers). If they only had to swim a breaststroke race, then for sure we would put them on the team. But if they had to swim other events, then we might not want them on the team. – jlammy Jan 11 '21 at 17:19
  • If we were to choose one swimmer for each style, how would I go about modeling this question using linear programming? – nothatcreative5 Jan 11 '21 at 17:42

1 Answers1

2

Assume you have to chose one swimmer for each style and no swimmer can perform in more than one style. This is an unbalanced assignment problem. You can frame the linear programming problem as follows:

$$\begin{array}{|c|c|c|c|c|} \hline \text{Style\Swimmer}&1&2&3&4&5\\\hline 1&x_{11}&x_{12}&x_{13}&x_{14}&x_{15}\\\hline 2&x_{21}&x_{22}&x_{23}&x_{24}&x_{25}\\\hline 3&x_{31}&x_{32}&x_{33}&x_{34}&x_{35}\\\hline 4&x_{41}&x_{42}&x_{43}&x_{44}&x_{45}\\\hline \end{array} $$

In the above table I have arranged the swimmers column-wise and strokes row-wise. $x_{ij}=1$ iff swimmer $j$ is selected to compete in stroke $i$ and $0$ otherwise. Let $t_{ij}$ denote the personal best of swimmer $j$ in stroke $i$.

Since one swimmer can be selected for at-most one stroke, we require all column-sums to be $\le1$. Thus one set of constraints is $\forall j\left(\sum_{i=1}^4x_{ij}\le1\right)$.

For each stroke we must select exactly one swimmer, so the row-sum must be $1$. Thus another set of constraints is $\forall i\left(\sum_{j=1}^5x_{ij}=1\right)$.

The final set of constraints is that $0\le x_{ij}\le1$ and integral (i.e. $x_{ij}=0,1$). The objective, in my opinion, should be to minimize the total time $T=\sum_i\sum_jx_{ij}t_{ij}$. You can solve this LPP using integer programming or the Hungarian method to solve assignment problems.

Shubham Johri
  • 17,659
  • Thank you very much, But there's a second part to the problem. Lets say I could brush 5 seconds off of one of the swimmers personal best. is there any efficient way for us to determine how that changes the outcome or should we just brute force it for the 20 possibilities? – nothatcreative5 Jan 11 '21 at 18:55