How to formulate as an assignment problem?

Question

How will I formulate this problem as an assignment problem?

I really don't know.

By definition of assignment problem, all the variables $x_{ij}$ are binary $(0$ or $1)$ and all the supply and demand are equal to $1.$

Will the 'cost' be represented by 'times in seconds' ?

Please someone help me how to solve this, how to translate this table into assignment problem?

I know how to solve the assignment problem, with the Hungarian method, but I did not see any examples like 8.3-4 in class..

Answer 1

We can see that there are more swimmers than the number of swimming strokes.

We can introduce another dummy swimming stroke that cost time $0$ for everyone. Hence now we have a square table and we can perform Hungarian method to solve the problem.

\begin{array}{|c|c|c|c|c|}\hline 37.7 & 32.9 & 33.8 & 37 & 35.4 \\ \hline 43.4 & 33.1 & 42.2 & 34.7 & 41.8\\ \hline 33.3 & 28.5 & 38.9 & 30.4 & 33.6 \\ \hline 29.2 & 26.4 & 29.6 & 28.5 & 31.1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}

Subtracting the minimum of each row from each row and then subtract the minimum of each column from each column and then cover up the zero (using color blue).

\begin{array}{|c|c|c|c|c|}\hline 4.8 & \color{blue}0 & 0.9 & 4.1 & 2.5 \\ \hline 10.3 & \color{blue}0 & 9.1 & 1.6 & 8.7\\ \hline 4.8 & \color{blue}0 & 10.4 & 1.9 & 5.1 \\ \hline 2.8 & \color{blue}0 & 3.2 & 2.1 & 4.7 \\ \hline \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}0 \\ \hline \end{array}

We then shift the zero and repeat the procedure:

\begin{array}{|c|c|c|c|c|}\hline 3.9 & \color{blue}0 & \color{blue}0 & 3.2 & 1.6 \\ \hline 9.4 & \color{blue}0 & \color{blue}{8.2} & 0.7 & 7.8\\ \hline 3.9 & \color{blue}0 & \color{blue}{9.5} & 1 & 4.2\\ \hline 1.9 & \color{blue}0 & \color{blue}{2.3} & 1.2 & 3.8\\ \hline \color{blue}0 & \color{blue}{0.9} & \color{blue}0 & \color{blue}0 & \color{blue}0 \\ \hline \end{array}

\begin{array}{|c|c|c|c|c|}\hline 3.2 & \color{blue}0 & \color{blue}0 & \color{blue}{2.5} & 0.9 \\ \hline 8.7 & \color{blue}0 & \color{blue}{8.2} & \color{blue}{0} & 7.1\\ \hline 3.2 & \color{blue}0 & \color{blue}{9.5} & \color{blue}{0.3} & 3.5\\ \hline 1.2 & \color{blue}0 & \color{blue}{2.3} & \color{blue}{0.5} & 3.1\\ \hline \color{blue}0 & \color{blue}{1.6} & \color{blue}{0.7} & \color{blue}0 & \color{blue}0 \\ \hline \end{array}

\begin{array}{|c|c|c|c|c|}\hline \color{blue}{2.3} & \color{blue}0 & \color{blue}0 & \color{blue}{2.5} & \color{blue}0 \\ \hline \color{blue}{7.8} & \color{blue}0 & \color{blue}{8.2} & \color{blue}{0} & \color{blue}{6.2}\\ \hline 2.3 & \color{blue}0 & 9.5 & 0.3 & 2.6\\ \hline 0.3 & \color{blue}0 & 2.3 & 0.5 & 2.2\\ \hline \color{blue}0 & \color{blue}{2.5} & \color{blue}{1.6} & \color{blue}{0.9} & \color{blue}0 \\ \hline \end{array}

I indicate the selected position in red color.

\begin{array}{|c|c|c|c|c|}\hline 2.3 & 0.3 & \color{red}0 & 2.5 & 0 \\ \hline 7.8 & 0.3 & 8.2 & \color{red}{0} & 6.2\\ \hline 2 & \color{red}0 & 9.2 & 0 & 2.3\\ \hline \color{red}0 & 0 & 2 & 0.2 & 1.9\\ \hline 0 & 2.8 & 1.6 & 0.9 & \color{red}0 \\ \hline \end{array}

Hence Carl should do freestyle $(29.2)$, Chris should do butterfly $(28.5)$, David should do backstroke $(33.8)$, Tony should do breaststroke $(34.7)$. The total time by the team is $126.2$.

Let's check our final answer by $R$ software:

library(lpSolve)
n <- 5
f.obj <- c(c(37.7, 32.9, 33.8, 37, 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), rep(0,n))
f.con<- rbind( kronecker(diag(n), t(rep(1,n))), kronecker(t(rep(1,n)), diag(n)), -diag(n*n))
f.dir <- c(rep('=', n), rep('<=', n*(n+1)))
f.rhs <- c(rep(1,2*n), rep(0,n*n))
optimum <- lp(direction = "min", objective.in = f.obj, const.mat = f.con, const.dir = f.dir, const.rhs = f.rhs)
Success: the objective function is 126.2 
matrix(optimum$solution, nrow = n, byrow = TRUE)
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    1    0    0
[2,]    0    0    0    1    0
[3,]    0    1    0    0    0
[4,]    1    0    0    0    0
[5,]    0    0    0    0    1

Answer 2

As you have said, the assignment is $x_{ij} = 1$ if swimmer $i$ is assigned to stroke $j$, with $\forall i, j\sum_{j'} x_{ij'} = \sum_{i'} x_{i'j} = 1$ (since we want exactly one swimmer per stroke).

We are trying to get the minimum sum of times, meaning that our objective function is $\sum_{ij} x_{ij} t_{ij}$ where $t_{ij}$ is the time it takes for swimmer $i$ to swim stroke $j$, hence the time is indeed our cost.