1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Not a direct answer to your question, but are you familiar with the concept of “shadow prices”? This is typically how people try to interpret dual variables in LPs. $\endgroup$ – David M. Apr 11 at 3:21
  • $\begingroup$ I'm afraid not, but that at least gives me something to look into. Thanks! $\endgroup$ – Cameron Buie Apr 11 at 10:27
  • $\begingroup$ Roughly, the variables $y_i$ for $i=3,\dots,7$ measure the amount that the manager is willing to pay to increase the contractual limit $m_i$ for employee $i$ by $1$. $y_1$ is the amount the manager is willing to pay to decrease the number of tasks he has to perform from $9$ to $8$. And $y_2$ is the amount the manager is willing to pay to decrease the total number of tasks from $77$ to $76$ (I would need to check on the details, but this is the "standard" interpretation more or less. I often find these explanations unsatisfying myself). $\endgroup$ – David M. Apr 11 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.