Objectives
-
Understand the concept of a dual problem in linear optimization.
-
Be able to write down a dual problem from any primal linear optimization problem.
Section 6.1 Introduction to Dual Problems
The concept of a dual problem is one of the most important ideas in linear optimization. It is a way to look at the same problem from a different perspective. The dual problem is related to the primal problem, which is the original problem we are trying to solve. In this section and the next two, we will first determine how to set up a dual problem. In the next section, we will examine the link between the solutions of the primal and dual problems. This will result in a certificate that the solution to the primal problem is optimal.
Subsection 6.1.1 Developing a Dual Problem
We return to Problem 2.1.1, in which Luis is a toymaker who is making decisions about the numbers of toy cars, trucks and SUVs to build to maximize his profit.
The applied problem was written in mathematical form in Section 2.1, but can be summarized as
Problem 6.1.1.
\begin{equation}
\begin{aligned} \text{Maximize} \amp \amp z = 10 x_1 + 15 x_2 + 12 x_3 \amp \\ \text{subject to} \amp \amp 6 x_1 + 5 x_2 + 4 x_3 \amp \leq 183 \\ \amp \amp 3 x_1 + 6 x_2 + 7 x_3 \amp \leq 204 \\ \amp \amp 45 x_1 + 75 x_2 + 90 x_3 \amp \leq 2655 \\ \text{and} \amp \amp x_1, x_2, x_3 \amp \geq 0.
\end{aligned}\tag{6.1.1}
\end{equation}
Let’s pretend we don’t know how to solve this. Instead, we want to see if we can estimate the amount of money that Luis will make. If we take the second constraint and multiply it by 4 to get
\begin{equation*}
12 x_1 + 24x_2 + 28 x_3 \leq 4(204) = 816
\end{equation*}
and use the fact that
\begin{equation*}
z = 10 x_1 + 15 x_2 + 12 x_3 \leq 12 x_1 + 24x_2 + 28 x_3 \leq 816.
\end{equation*}
This shows that the maximize that Luis will earn in the week is less than $816. Also, note that it is important that \(x_1, x_2, x_3 \geq 0\) for the inequalities to hold.
Another possible bound will be to multiply the first constraint by \(3/2\text{,}\) the second by \(1/2\) and the last by \(1/15\) or
\begin{align*}
9 x_1 + \frac{15}{2} x_2 + 6 x_3 \amp \leq \frac{549}{2} \\
\frac{3}{2}x_1 + 3 x_2 + \frac{7}{2} x_3 \amp \leq 102 \\
3x_1 + 5x_2 + 6x_3 \amp \leq 177
\end{align*}
If we add these three constraints:
\begin{equation*}
\begin{aligned} \left(9 x_1 + \frac{15}{2} x_2 + 6 x_3 \right) + \amp \left(\frac{3}{2}x_1 + 3 x_2 + \frac{7}{2} x_3 \right) + \left(3x_1 + 5x_2 + 6x_3 \right) \\ \amp = \frac{27}{2} x_1 + \frac{31}{2} x_2 + \frac{31}{2} x_3 \\ \amp \leq \frac{549}{2} + 102 + 177 = 553.5 \end{aligned}
\end{equation*}
Since \(z = 10 x_1 + 15 x_2 + 12 x_3 \leq \frac{27}{2} x_1 + \frac{31}{2} x_2 + \frac{31}{2} x_3 \leq 553.5 \text{,}\) we can conclude that \(z \leq 553.5,\) so this is a better bound than the previous one.
Checkpoint 6.1.2.
Find another bound for \(z\text{.}\) Can you beat $816? How about $553.50? You can take a single inequality and multiply through a constant or take a linear combination like the above example.
We arbitrarily picked some values to multiply the three constraints by to try to develop a bound. Instead, if we use the variables \(y_1, y_2\) and \(y_3\) as factors, let’s see what happens. That is
\begin{equation}
\begin{aligned}y_1 (6x_1 + 5x_2 + 4x_3) \leq 183 y_1 \\ y_2 (3x_1 + 6x_2 + 7x_3) \leq 204 y_2 \\ y_3 (45x_1 + 75x_2 + 90x_3) \leq 2655 y_3 \\ \end{aligned}\tag{6.1.2}
\end{equation}
If we sum the left hand sides of these, to get
\begin{equation}
\begin{aligned}
B \amp = (6x_1 + 5x_2 + 4x_3) y_1 + (3x_1 + 6x_2 + 7x_3) y_2 + (45 x_1 + 75 x_2 + 90 x_3) y_3 \\
\amp = (6y_1 + 3y_2 + 45y_3) x_1 + (5y_1 + 6y_2 + 75y_3) x_2 + (4y_1 + 7y_2 + 90 y_3) x_3 \\ \end{aligned}\tag{6.1.3}
\end{equation}
where the terms have been rearranged to be factors of \(x_1, x_2\) and \(x_3\text{.}\) From the the terms in (6.1.2), we have
\begin{equation}
B \leq 183 y_1 + 204 y_2 + 2655 y_3\tag{6.1.4}
\end{equation}
and we defined \(w\) to be the right hand side of this inequality. Also, because \(B\) is also an upper bound on \(z\text{,}\) we have
\begin{equation}
z = 10x_1 + 15x_2 + 12 x_3 \leq B \tag{6.1.5}
\end{equation}
\begin{equation*}
\begin{aligned} z \amp = 10 x_1 + 15 x_2 + 12 x_3 \\ \amp \leq (6y_1 + 3y_2 + 45y_3) x_1 + (5y_1 + 6y_2 + 75y_3) x_2 + (4y_1 + 7y_2 + 90 y_3) x_3 \end{aligned}
\end{equation*}
\begin{align*}
6y_1 + 3 y_2 + 45 y_3 \amp \geq 10, \\
5y_1 + 6y_2 + 75 y_3 \amp \geq 15, \\
4y_1 + 7y_2 + 90 y_3 \amp \geq 12,
\end{align*}
If we define \(w = 183 y_1 + 204 y_2 + 2655 y_3\text{,}\) then we can determine the smallest bound for \(z\text{,}\) if we minimize \(w\text{.}\) Specifically, we can define the problem
Problem 6.1.3.
\begin{equation*}
\begin{aligned} \text{Minimize} \amp \amp w = 183 y_1 + 204 y_2 + 2655 y_3, \amp \\ \text{subject to} \amp \amp 6 y_1 + 3 y_2 + 45 y_3 \amp \geq 10, \\ \amp \amp 5 y_1 + 6 y_2 + 75 y_3 \amp \geq 15, \\ \amp \amp 4 y_1 + 7 y_2 + 90 y_3 \amp \geq 12, \\ \text{and} \amp \amp y_1, y_2, y_3 \amp \geq 0.
\end{aligned}
\end{equation*}
This problem is called the dual of (6.1.1) and we will see in this section that there is an important relationship between a problem and its dual.
We will see how the dual plays an important mathematical relationship to the original (primal) problem throughout the rest of this chapter, however, let’s look at this example and interpret the new variables \(y_1, y_2\) and \(y_3\text{.}\)
First, note that \(w\) is the objective and it has the same units as \(z\) in the primal problem. In the primal problem, the goal was to maximize the profit. The unit of \(w\) is the same, but we are trying to minimize a cost.
Also recall that the coefficients of the dual objective are 183, 204 and 2655. These represent the units of pine, units of birch and total hours of labor that are available. The three \(y\) variables multiply these terms to give dollars so
\begin{align*}
y_1 \amp = \text{profit/unit of birch} \\
y_2 \amp = \text{profit/unit of pine} \\
y_3 \amp = \text{profit/hour of labor}
\end{align*}
In this example, the terms are called the marginal values or shadow prices, which come from economics. The value of \(y_1\) is the amount that the profit that can be earned for an extra unit of birch. This is the same for \(y_2\) except for pine. The value of \(y_3\) is the amount profit that could be made for an extra hour of labor.
Much more could be said about this and for certain problems, the analysis of this is helpful for businesses making decisions.
Subsection 6.1.2 Generalizing the Dual
Recall that in Subsection 2.2.3 we wrote an LOP in standard form as
Problem 6.1.4. Primal Maximal LOP.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp \amp z = \sum_{j=1}^n c_j x_j \amp \\ \text{subject to} \amp \amp \sum_{j=1}^n a_{ij} x_j \amp \leq b_j \qquad \text{for $1 \leq i \leq m$} \\ \text{and} \amp \amp x_j \amp \geq 0, \qquad \text{for $1 \leq j \leq n$} \end{aligned}
\end{equation*}
is labeled Primal to distinguish it from the dual and a maximal problem. This can be written in matrix form as
\begin{equation}
\begin{aligned} \text{Maximize} \amp \amp z = \boldsymbol{c}^{\intercal} \boldsymbol{x}, \\ \text{subject to} \amp \amp A \boldsymbol{x} \leq \boldsymbol{b}, \amp \amp \text{and}\qquad \amp \boldsymbol{x} \geq 0.
\end{aligned}\tag{6.1.6}
\end{equation}
Notice that the coefficients of the variables throughout the dual problem are the same as the primal problem, but in different locations.
Problem 6.1.5. Dual Minimal LOP.
\begin{equation*}
\begin{aligned} \text{Minimize} \amp \amp w = \sum_{i=1}^m b_i y_i, \amp \\ \text{subject to} \amp \amp \sum_{i=1}^m a_{ij} y_i \amp \geq c_i \qquad \text{for $1 \leq j \leq n$,} \\ \text{and} \amp \amp y_i \amp \geq 0, \qquad \text{for $1 \leq i \leq m$.} \end{aligned}
\end{equation*}
or in matrix form as
\begin{equation}
\begin{aligned} \text{Minimize} \amp \amp w = \boldsymbol{b}^{\intercal} \boldsymbol{y}, \\ \text{subject to} \amp \amp A^{\intercal} \boldsymbol{y} \geq \boldsymbol{c}, \amp \amp \text{and}\qquad \amp \boldsymbol{y} \geq 0.
\end{aligned}\tag{6.1.7}
\end{equation}
Checkpoint 6.1.6.
Write down the dual of Problem 2.2.2 and then find its optimal solution using the simplex method finding the final tableau.
Solution.
The dual can be written as
\begin{equation*}
\begin{aligned} \text{Minimize} \amp \amp w = 120 y_1 + 40 y_2 + 16 y_3 \amp \\ \text{subject to} \amp \amp 4y_1 + 2 y_2 \amp \geq 1, \\ \amp \amp 3y_1 + 2 y_2 + y_3 \amp \geq 3, \\ \text{and} \amp \amp y_1, y_2, y_3 \amp \geq 0, \end{aligned}
\end{equation*}
The solution can be found by starting with the tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrr|r} -4 \amp -2 \amp 0 \amp 1 \amp 0 \amp 0 \amp -3\\ -3 \amp -2 \amp -1 \amp 0 \amp 1 \amp 0 \amp -3\\ \hline 120 \amp 40 \amp 16 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and then performing the simplex method to get the final tableau:
\begin{equation*}
\begin{array}{r} 1 \mapsto 4, \\ 2 \mapsto 5, \\ 5 \mapsto 1, \end{array} \qquad \left[\begin{array}{rrr|rrr|r} 2 \amp 0 \amp -2 \amp -2 \amp 2 \amp 0 \amp 0\\ 4 \amp 2 \amp 0 \amp -1 \amp 0 \amp 0 \amp 3\\ \hline 80 \amp 0 \amp 32 \amp 40 \amp 0 \amp 2 \amp -120\\ \end{array} \right]
\end{equation*}
This has the solution
\begin{equation*}
\boldsymbol{y} = \frac{1}{2} \left[\begin{array}{rrr|rr} 0 \amp 3 \amp 0 \amp 0 \amp 0 \end{array}\right],
\end{equation*}
and the objective for this is \(w=-z = 120\text{.}\)
Subsection 6.1.3 Weak Primal-Dual Theorem
In the specific problem that we defined the dual in this section in the inequalities in (6.1.3), (6.1.4) and (6.1.5). Using the general primal and dual problems, we can set up the following inequalities:
\begin{align}
z \; = \; \amp \boldsymbol{c}^{\intercal} \boldsymbol{x} \tag{6.1.8}\\
\; \leq \;\amp (A^{\intercal} \boldsymbol{y})^{\intercal} \boldsymbol{x} \tag{6.1.9}\\
\; = \; \amp \boldsymbol{y}^{\intercal} A \boldsymbol{x} \tag{6.1.10}\\
\;\leq\; \amp \boldsymbol{y}^{\intercal} \boldsymbol{b} \tag{6.1.11}\\
\;= \; \amp \boldsymbol{b}^{\intercal} \boldsymbol{y} = w \tag{6.1.12}
\end{align}
where the equality in (6.1.8) arises from the objective function in (6.1.6). The inequality in (6.1.9) is a result of the inequality in (6.1.7). The equality in (6.1.10) is the property of transposes of matrices and the inequality in (6.1.11) is the inequality constraint from the Primal problem in (6.1.6). Finally the last step in (6.1.12) is because each of the right hand sides of the last two equations are scalars and thus the transposes can be interchanged. Then the term \(\boldsymbol{b}^{\intercal} \boldsymbol{y}\) is the definition of the objective in (6.1.7).
If we examine the inequalities in (6.1.8), this is true for any \(\boldsymbol{x}\) and \(\boldsymbol{y}\) that satisfy the constraints in the primal and dual problems, respectively. In short, \(\boldsymbol{x}\) and \(\boldsymbol{y}\) must be feasible points.
The results of this is summarized as the following.
Theorem 6.1.7. Weak Duality Theorem.
\begin{equation*}
z = \boldsymbol{c}^{\intercal} \boldsymbol{x} \leq \boldsymbol{b}^{\intercal} \boldsymbol{y} = w
\end{equation*}
for any point \(\boldsymbol{x}\) that is feasible in the Primal problem and \(\boldsymbol{y}\) a feasible point in the Dual problem.
As an example, in Subsection 6.1.1, some attempts to find a bound on the maximum profit from Luis the toymaker. For example, the first bound of $816 was found by taking the second constraint and multiplying it by 4, which is a feasible point in the dual problem. The second bound of $564 was found by taking a linear combination of the first two constraints. The first bound is actually \(\boldsymbol{y} = [0~4~0]^{\intercal}\) and the second bound is \(\boldsymbol{y} = [\frac{3}{2}\;\;\frac{1}{2}\;\;\frac{1}{15}]^{\intercal}\text{.}\)
The bounds can be calculated by using the objective function in the dual problem in Problem 6.1.3. For the first bound:
\begin{equation*}
w = 183 \cdot 0 + 204 \cdot 4 + 2655 \cdot 0 = 816.
\end{equation*}
and for the second bound:
\begin{equation*}
w = 183 \cdot \frac{3}{2} + 204 \cdot \frac{1}{2} + 2655 \cdot \frac{1}{15} = 564.
\end{equation*}
Checkpoint 6.1.8.
For these two bounds, show that the value of \(\boldsymbol{y}\) are feasible points in the dual problem.
Solution.
For the first bound, we have
\begin{equation*}
\begin{aligned} 6 \cdot 0 + 3 \cdot 4 + 45 \cdot 0 = 12 \amp \geq 12 \\ 5 \cdot 0 + 6 \cdot 4 + 75 \cdot 0 = 24 \amp \geq 15 \\ 4 \cdot 0 + 7 \cdot 4 + 90 \cdot 0 = 28 \amp \geq 12.
\end{aligned}
\end{equation*}
and for the second bound, we have
\begin{equation*}
\begin{aligned} 6 \cdot \frac{3}{2} + 3 \cdot \frac{1}{2} + 45 \cdot \frac{1}{15} \amp = 9 + 1.5 + 3 = 13.5 \geq 12 \\
5 \cdot \frac{3}{2} + 6 \cdot \frac{1}{2} + 75 \cdot \frac{1}{15} \amp = 7.5 + 3 + 5 = 15.5 \geq 15 \\
4 \cdot \frac{3}{2} + 7 \cdot \frac{1}{2} + 90 \cdot \frac{1}{15} \amp = 6 + 3.5 + 6 = 15.5 \geq 12.
\end{aligned}
\end{equation*}
