ass1 [ 4s + 4le + 12li = 9.4]
ass2 [ 12s + 4le + 4li = 7.6]
ass3 [ 8s + 8le + 8li = 11.0]
s= 0.2
l= 0.25
li= 0.3
I'd guess you would want to put these into a matrix form and then reduce it,
4 4 12 | 9.4
12 4 4 | 7.6
8 8 8 | 11.0
The required LP is
$\begin{align}
\min & \sum_{i=1}^n\sum_{j=1}^n M_{ij} x_{ij} \\
& \sum_{i=1}^n x_{ij} = 1 \quad \forall j \in \{1,\dots, n\} \tag{each job is assigned to exactly one person} \\
& \sum_{j=1}^n x_{ij} = 1 \quad \forall i \in \{1,\dots, n\} \tag{each person is assigned to exactly one job} \\
& x_{ij} \in \{0,1\} \quad \forall i,j \in \{1, \dots, n\}
\end{align}$
To understand the objective function, for each job $j$, there exist unique $i_0 \in \{1, \dots, n\}$ such that $x_{ij} = \begin{cases} 1 &\text{if } i = i_0 \\ 0 &\text{otherwise,} \end{cases}$ so the cost for the $j$-th job is $M_{i_0j} = \sum
\limits_{i=1}^n M_{ij}$. Sum the previous equality over $j \in \{1,\dots,n\}$ to get the above double sum.
How do I convert this minimization problem into a maximization problem?
To minimize a quantity is equivalent to maximizing its additive inverse.
Furthermore, how would the constraints be defined by this sort of problem?
Use the standard technique of transforming an equality constraint to a set of two inequality constraints:
$$x = a \iff \begin{cases} - x &\le -a \\ x &\le a. \end{cases}$$
Are my definitions adequate for the problem?
They are more than enough. You don't need to define $M$, since you already have $C$, which represents the costs.
To write the LP is a more concise matrix form, denote
- $\mathbf{1} \in \{0,1\}^n$ the $n \times 1$ vector filled with $1$.
- $C = (C[i,j])_{ij} = (c_{ij})_{ij} \in \mathbb{R}^{n \times n}$: the matrix $C$ is defined by $C[i,j]$ as the $(i,j)$-th element, so that
- $(C^T)_{ij} = c_{ji}$: the $(i,j)$-th element of $C^T$ is the $(j,i)$-th element of $C$.
- $X = (x_{ij})_{ij} \in \{0,1\}^{n \times n}$
Remarks: I prefer using capital letters for matrices, and use small letters with a subscript to denote the corresponding matrix elements.
Note that the cost function is
\begin{align}
\sum_{i=1}^n \sum_{j=1}^n C[i,j] x_{ij} &= \sum_{i=1}^n \sum_{j=1}^n (C^T)_{ji} x_{ij} \tag{take transpose of $C$} \\
&= \sum_{j=1}^n \left( \sum_{i=1}^n (C^T)_{ji} x_{ij} \right) \tag{change order of summation} \\
&= \sum_{j=1}^n \left( C^T X \right)_{jj} \tag{defintion of matrix product} \\
&= \mathop{\mathrm{tr}}(C^T X). \tag{definition of trace}
\end{align}
$\sum\limits_{i=1}^n x_{ij} = 1$ can be rewritten as $\mathbf{1}^T X = \mathbf{1}^T$; $\sum\limits_{j=1}^n x_{ij} = 1$ can be rewritten as $X \mathbf{1} = \mathbf{1}$.
Hence the LP in matrix form is $\min\{\mathop{\mathrm{tr}}(C^T X) \mid \mathbf{1}^T X = \mathbf{1}^T, X \mathbf{1} = \mathbf{1}, X \in \{0,1\}^{n \times n} \}$
Best Answer
Yes, this is correct, although you might want to explicitly impose lower bounds $x \ge 0$ and $y \ge 0$. The dual variables $(3,0,0,6)$ provide a short proof that $1560$ is an upper bound on the objective value: $$5x+6y = 3(x+y)+6\left(\frac{1}{3}x+\frac{1}{2}y\right) \le 3(300) + 6(110) = 1560$$