Section 6.2 Primal-Dual Relationships
Objectives
-
Understand the relationship between the primal and dual problems.
-
Determine the optimal values of the dual problem from the final tableau of the primal problem.
-
Understand the set of lemmas relating the dual and primal problems.
-
Understand the proof of the Strong Duality Theorem.
Let’s consider a Primal LOP
\begin{equation}
\begin{aligned} \text{Maximize} \amp\amp z = 3x_1 + 4x_2 + 7 x_3, \amp \\ \text{such that}\amp\amp x_1 + 2x_2 + 3x_3 \amp \leq 12, \\ \amp\amp 4x_1 + 3x_2 + 2x_3 \amp \leq 18, \\ \text{and}\amp\amp x_1, x_2, x_3 \amp \geq 0.
\end{aligned}\tag{6.2.1}
\end{equation}
\begin{equation*}
\left[\begin{array}{rrr|rrr|r} 1 \amp 2 \amp 3 \amp 1 \amp 0 \amp 0 \amp 12\\ 4 \amp 3 \amp 2 \amp 0 \amp 1 \amp 0 \amp 18\\ \hline -3 \amp -4 \amp -7 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and using the simplex method, the tableau with optimal solutions is
\begin{equation}
\begin{array}{r} 1 \mapsto 5, \\ 2 \mapsto 4, \\ 3 \mapsto 2, \end{array} \qquad \left[\begin{array}{rrr|rrr|r} 0 \amp 5 \amp 10 \amp 4 \amp -1 \amp 0 \amp 30\\ 10 \amp 5 \amp 0 \amp -2 \amp 3 \amp 0 \amp 30\\ \hline 0 \amp 10 \amp 0 \amp 22 \amp 2 \amp 10 \amp 300\\ \end{array} \right].\tag{6.2.2}
\end{equation}
The optimal basic solution is
\begin{equation*}
\boldsymbol{x}^{\star} = \left[\begin{array}{rrr|rr} 3 \amp 0 \amp 3 \amp 0 \amp 0 \end{array}\right]^{\intercal}
\end{equation*}
with
\(z^{\star} = 30\text{.}\)
The dual problem is written
\begin{equation}
\begin{aligned} \text{Minimize} \amp\amp w = 12y_1 +18 y_2 \amp\\ \text{such that} \amp\amp y_1 + 4y_2 \amp\geq 3, \\ \amp\amp2y_1 + 3y_2 \amp \geq 4, \\ \amp\amp 3y_1 + 2y_2 \amp \geq 7, \\ \text{and} \amp\amp y_1, y_2, \amp \geq 0.
\end{aligned}\tag{6.2.3}
\end{equation}
This can be solved with the simplex method. The initial tableau is
\begin{equation*}
\left[\begin{array}{rr|rrrr|r} -1 \amp -4 \amp 1 \amp 0 \amp 0 \amp 0 \amp -3\\ -2 \amp -3 \amp 0 \amp 1 \amp 0 \amp 0 \amp -4\\ -3 \amp -2 \amp 0 \amp 0 \amp 1 \amp 0 \amp -7\\ \hline 12 \amp 18 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and tableau pivots result in
\begin{equation}
\begin{array}{r} 1 \mapsto 5, \\ 2 \mapsto 3, \end{array} \qquad \left[\begin{array}{rr|rrrr|r} 0 \amp 10 \amp -3 \amp 0 \amp 1 \amp 0 \amp 2\\ 0 \amp 0 \amp -5 \amp 10 \amp -5 \amp 0 \amp 10\\ 10 \amp 0 \amp 2 \amp 0 \amp -4 \amp 0 \amp 22\\ \hline 0 \amp 0 \amp 30 \amp 0 \amp 30 \amp 10 \amp -300\\ \end{array} \right].\tag{6.2.4}
\end{equation}
\begin{equation*}
\boldsymbol{y}^{\star} = \frac{1}{10} \left[\begin{array}{rr|rrr} 22 \amp 2 \amp 0 \amp 10 \amp 0 \end{array} \right]^{\intercal}.
\end{equation*}
with \(w^{\star} = 300/10 = 30\text{.}\)
Looking at the final tableau for both the primal and dual problems, you should notice many similarities. In particular, the nonzero elements of
\(\boldsymbol{y}^{\star}\) are located in the final objective row of the primal tableau (except for some shuffling of locations). Additionally, the nonzero values of
\(\boldsymbol{x}^{\star}\)are located in the final objective row of the dual tableau, again with shuffling of locations. This section will discuss why this occurs.
Consider now that the simplex method was performed on the primal problem. The final objective row will take on the form:
\begin{equation*}
\left[ \begin{array}{ccccc|cccccc|c} \amp\amp\amp\amp\amp\amp\amp\amp\amp\amp \\ \hline c_1^{\star} \amp \cdots \amp c_j^{\star} \amp \cdots \amp c_n^{\star} \amp c_{n+1}^{\star} \amp \cdots \amp c_{n+i}^{\star} \amp \cdots \amp c_{n+m}^{\star} \amp 1 \amp z^{\star} \end{array} \right],
\end{equation*}
where the last row needs to be scaled such that the second to last element is
\(1\text{.}\) Thus, if that value is not 1, like in
(6.2.4), the row should be multiplied through by
\(1/d\text{,}\) where
\(d\) is the final pivot value.eq-ex-dual-tableau-solution
From what we saw in the problem above, it appears that
\begin{equation}
y_i^{\star} = c_{n+i}^{\star} \qquad \text{for $1 \leq i \leq m$} \qquad y_{m+j}^{\star} = c_j^{\star} \qquad \text{for $1 \leq j \leq n$}.\tag{6.2.5}
\end{equation}
Here’s the roadmap for what we are trying to do. We have the tableau from the primal problem, and specifically the final objective row. We want to show that
-
The values of the objective row correspond to the optimal values of
\(\boldsymbol{y}^{\star}\) in the dual.
-
The values of
\(c_j^{\star}\) satisfy constraints thus the values of
\(y_j^{\star}\) are non-negative.
-
The variables
\(y_j^{\star}\) satisfy the other constraints of the dual.
-
The optimal value of
\(w^{\star}\) equals
\(z^{\star}\text{.}\)
We will then call the optimal values of
\(\boldsymbol{y}\) the
certificate for the primal problem. The last statement above is the
strong-duality theorem the crux of this section.
Lemma 6.2.1.
The optimal values of
\(\boldsymbol{y}^{\star}\) as defined by
(6.2.5) satisfies the nonnegative constraint.
Proof.
Because
\(c_{j}^{\star}\) for all
\(j\) is in the objective row of the final tableau, all elements are nonnegative, therefore
\(y_i^{\star}\) is nonnegative.
Lemma 6.2.2.
\begin{equation}
z = \sum_{j=1}^n c_j x_j = \biggl(z^{\star} - \sum_{i=1}^m b_i y_i^{\star} \biggr) + \sum_{j=1}^n \biggl(\sum_{i=1}^m a_{ij} y^{\star}_i - y_{m+j}^{\star} \biggr) x_j.\tag{6.2.6}
\end{equation}
where
\(z^{\star}\) is the optimal value of
\(z\) of the Primal LOP and the
\(y^{\star}\)’s. The values of
\(x_j\) can be any nonnegative value.
Proof.
The last row of the objective function of the final primal tableau states that
\begin{equation*}
z = z^{\star}- \sum_{j=1}^{n} c^{\star}_{j} x_{j} -\sum_{i=1}^{m} c^{\star}_{n+i}x_{n+i}
\end{equation*}
\begin{equation}
z= z^{\star}- \sum_{j=1}^{n} y^{\star}_{m+j}x_{j} -\sum_{i=1}^{m} y^{\star}_{i}x_{n+i}.\tag{6.2.7}
\end{equation}
Since the slack variable
\(x_{n+i}\) from the original form of the dictionary can be written:
\begin{equation*}
x_{n+i} = b_{i} - \sum_{j=1}^{n} a_{ij}x_{j} \qquad \text{for $i=1,2,\ldots,m$}
\end{equation*}
we can use this and the objective
\(z=\sum_{j=1}^n c_j x_j\) from the Primal LOP to write
(6.2.7) as
\begin{equation*}
\sum_{j=1}^{n} c_{j} x_{j} = z^{\star}- \sum_{j=1}^{n} y^{\star}_{m+j}x_{j} - \sum_{i=1}^{m} y^{\star}_{i} \biggl( b_{i} - \sum_{j=1}^{n} a_{ij}x_{j} \biggr)
\end{equation*}
\begin{equation*}
\sum_{j=1}^{n} c_{j} x_{j} = \biggl( z^{\star}-\sum_{i=1}^{m} b_{i} y_{i}^{\star}\biggr) + \sum_{j=1}^{n} \biggl( \sum_{i=1}^{m} a_{ij}y^{\star}_i - y_{m+j}^{\star}\biggr) x_{j}.
\end{equation*}
Corollary 6.2.3.
\begin{equation*}
z^{\star} = \sum_{i=1}^m b_i y^{\star}_i
\end{equation*}
Proof.
Corollary 6.2.4.
\begin{equation*}
\sum_{j=1}^n c_j x_j = \sum_{j=1}^n \biggl( \sum_{i=1}^m a_{ij} y^{\star}_i - y^{\star}_{m+j} \biggr) x_j.
\end{equation*}
Proof.
Corollary 6.2.5.
\begin{equation}
c_j = \sum_{i=1}^m a_{ij} y^{\star}_i - y^{\star}_{m+j}\tag{6.2.8}
\end{equation}
\begin{equation}
\sum_{i=1}^m a_{ij} y^{\star}_i \geq c_j.\tag{6.2.9}
\end{equation}
Proof.
Note that we have shown that the values of
\(c_{i}^{\star}\) taken from the objective row of the final primal tableau, which are called the certificates, are equal to the solution of the dual problem,
\(y_i^{\star}\text{.}\)
Additionally, the values of
\(y_{i}^{\star}\) satisfy the dual problem. Specifically, the values of
\(y_{i}^{\star}\) satisfy the nonnegative constraints from
Lemma 6.2.1 and they also satisfy the more general constraint from
Corollary 6.2.5. To show the dual objective function is satifised, we need the next theorem.
Theorem 6.2.6. Strong Duality Theorem.
If a linear problem
\(P\) has an optimal value
\(z^{\star}\text{,}\) and its dual problem
\(D\) has an optimal value
\(w^{\star}\) then
\(z^{\star}=w^{\star}\text{.}\)
Proof.
The objective function of the dual is define as
\begin{equation*}
w = \sum_{j=1}^n b_j y_j.
\end{equation*}
and if the optimal values are used then
\begin{equation*}
w^{\star} = \sum_{j=1}^n b_j y_j^{\star}.
\end{equation*}
