I'm confronted with the following situation:
A company has $5$ employees (conveniently numbered from $1$ to $5$). Each employee is paid at a fixed rate per task completed. The company also has an owner, who is salaried.
There are $77$ tasks to perform next week, each of which must be allocated to exactly one of the six people. The owner must perform $9$ of the tasks, but (due to scheduling conflicts) cannot perform more than $24$ of the tasks. Furthermore, each of the employees is contractually limited to a maximum number of tasks per week.
The company has entered a slow season, and so the owner wishes to minimize the total amount paid to the employees next week. How many tasks should be allocated to each employee next week?
So, to put this into terms of a linear program, I proceeded as follows:
- For each $i\in\{1,2,3,4,5\},$ let $r_i$ be the rate per task at which employee $i$ is paid, let $x_i$ be the number of tasks allocated to employee $i$ next week, and let $m_i$ be the contractual maximum number of tasks per week that may be allocated to employee $i$.
- Since the employees can be allocated at most $77-9=68$ tasks in total, then $$x_1+x_2+x_3+x_4+x_5\le 68,$$ and since they must be allocated at least $53$ of the tasks in total, then $$-x_1+-x_2+-x_3+-x_4+-x_5\le -53.$$
- Constraints due to contractual limits take the form $$x_i\le m_i$$ for each $i\in\{1,2,3,4,5\}.$
- Since a negative number of tasks cannot be assigned, then $x_i\ge 0$ for each $i\in\{1,2,3,4,5\}.$
- The goal is to minimize $r_1x_1+r_2x_2+r_3x_3+r_4x_4+r_5x_5.$
Let $\mathbf{e}_n$ indicate the column vector consisting of $n$ entries of $1$ only, let $\mathbf{0}_n$ indicate the column vector consisting of $n$ entries of $0$ only, and let $\mathbf{I}_n$ indicate the $n\times n$ identity matrix. Further, let $\mathbf{m},$ $\mathbf{r},$ and $\mathbf{x}$ be the column vectors whose respective entries are the numbers $m_i,$ the numbers $r_i,$ and the variables $x_i.$ We can then express the goal in block matrix form as follows:
Minimize $\mathbf{r}^T\mathbf{x}$ subject to the constraints $\mathbf x\ge\mathbf 0_5$ and $$\begin{bmatrix}\mathbf{e}_5^T \\ -\mathbf{e}_5^T \\ \mathbf{I}_5\end{bmatrix}\mathbf{x}\le\begin{bmatrix}68\\-53\\\mathbf{m}\end{bmatrix}.$$
Given the vector $\mathbf m,$ it isn't difficult to optimize as asked. However, I'm curious about the dual of this linear program.
Following the "recipe" given by Wikipedia, it seems that the dual linear program would be constructed as follows:
- We have dual variables $y_1,y_2,...,y_6,y_7.$
- We have the sign constraints $y_j\ge 0$ for each $j\in\{1,2,...,6,7\}.$
- We must maximize $68y_1-53y_2+\sum_{k=1}^5 m_iy_{i+2}.$
- We have dual constraints $y_1-y_2+y_{2+k}\ge r_k$ for each $k\in\{1,2,3,4,5\}.$
We can then express this in block matrix form as follows:
Maximize $\begin{bmatrix}68 & -53 & \mathbf{m}^T\end{bmatrix}\mathbf{y}$ subject to the constraints $\mathbf y\ge\mathbf 0_7$ and $$\begin{bmatrix}\mathbf{e}_5 & -\mathbf{e}_5 & \mathbf{I}_5\end{bmatrix}\mathbf{y}\ge\mathbf{r}.$$
First (but less important) question: Have I correctly followed the "recipe" for finding the dual linear program?
Second (far more important) question: I can see clearly that the optimal solution of the primal linear program gives us the hours the owner should assign to each employee to minimize the total amount paid to the employees next week, but (assuming I've correctly determined the dual LP) how should I interpret the variables/constraints/optimal solution for the dual in context?