Objectives
-
Explain how the certificate ensures that a solution is optimal.
-
Use the Complementary Slackness Condition to further deepen your understanding of simplex tableaus.
Section 6.4 Finding Optimal Certificates
First of all, a reminder that a certificate for an LOP is the set of \(y_{i}\) values from the dual for a given set of \(x_{j}\) value from the Primal. If the values we are discussing arise from an optimal solution, then the \(y\)’s are called an optimal certificate.
We will show in this section why a certificate is important—how it can show that a basic solution is optimal.
For example, in the first example of this chapter we saw that \(\boldsymbol{x}=[3\; 0\; 3]^{\intercal}\) was a solution to the Primal LOP, with \(z=30\text{.}\) The certificate is \(\boldsymbol{y}=[11 \; 1]^{\intercal}/5\) with \(w=30\) and \(w=z\text{,}\) this is optimal.
We’ll use the notation \((+,0,\star~|~0,0,+,+,0)^{\intercal}\text{.}\) to describe any feasible solution of an LOP with 3 variable and 5 constraints for which coordinates labelled 0 have value 0, coordinates labelled + have positive value and coordinates labelled \(\star\) have nonnegative values.
The Complementary Slackness Condition above can be written as:
\begin{equation*}
\begin{aligned} x_{j}' \amp = 0 \amp \amp \text{or} \amp y'_{m+j} \amp = 0 \qquad \text{for all $1\leq j\leq n$}, \\ x_{n+i}' \amp = 0 \amp \amp \text{or} \amp y_{i}' \amp = 0 \qquad \text{for all $1 \leq i \leq m$}.
\end{aligned}
\end{equation*}
Thus if \(\boldsymbol{x}'\) has the form \((+,0,+~|~0,0,+,+,0)^{\intercal}\) then in order for it to be primal optimal, \(\boldsymbol{y}'\) must be of the form \((\star,\star,0,0,\star~|~0,\star,0)^{\intercal}\text{.}\)
The reason this is useful is the following: Suppose that you know think that \(\boldsymbol{x}=(3,0,3)\) is the solution to
\begin{equation*}
\begin{aligned}\text{Maximize} \amp \amp z = 3x_{1} + 4x_{2} + 7 x_{3} \amp \\ \text{s.t.} \amp \amp x_{1} + 2x_{2} + 3x_{3} \leq 12, \\ \amp \amp 4x_{1} + 3x_{2} + 2x_{3} \leq 18, \\ \text{and} \amp \amp x_{1}, x_{2}, x_{3} \geq 0.\end{aligned}
\end{equation*}
but you tossed out the simplex tableau. The value \(\boldsymbol{x}=(3,0,3)^{\intercal}\) generates equality for both constraints, so it really has the solution \(\boldsymbol{x}=(3,0,3~|~0,0)^{\intercal}\) which has the form \((+,0,+~|~0,0)^{\intercal}\) and thus its dual solution has the form, \((*,*~|~0,*,0)\text{.}\) Thus, if we solve:
\begin{equation*}
\begin{aligned}y_{1} + 4y_{2} \amp = 3, \\ 2y_{1}+3y_{2} -y_{4} \amp = 4, \\ 3y_{1}+2y_{2} \amp = 7,\end{aligned}
\end{equation*}
which has the unique solution \(y_{1}=11/5, y_{2}=1/5, y_{4}=1\text{.}\) These can be used to show that \(w=30\text{,}\) which equals \(z\) so this is optimal.
Theorem 6.4.1. Complementary Slackness Theorem.
Let \(\boldsymbol{x}'\) be \(P\)-feasible. Then \(\boldsymbol{x}'\) is primal optimal if and only if there is a \(D\)-feasible \(\boldsymbol{y}'\) such that both
\begin{equation*}
\begin{aligned} \amp \amp x'_{j} \amp > 0 \amp \amp \text{implies} \amp \sum_{i=1}^{m} a_{i,j}y'_{i} \amp = c_{j} \qquad \text{for all $1 \leq j \leq n$}\\ \text{and} \amp \amp \sum_{j=1}^{n} a_{i,j}x'_{j} \amp < b_{i} \amp \amp \text{implies} \amp y'_{i} \amp = 0 \qquad \text{for all $1 \leq i \leq m$}.\end{aligned}
\end{equation*}
Example 6.4.2.
Consider the Primal LOP:
\begin{equation*}
\begin{aligned}\text{Maximize} \amp \amp z = 3x_{1} + 4x_{2} -1 x_{3} -5x_{4} +8 x_{5}, \amp \\ \text{s.t.} \amp \amp 2x_{1} -x_{2} + 3x_{3} + 6x_{5} \amp \leq 36, \\ \amp \amp 3x_{1} -5x_{2} + x_{3} -3 x_4 + 2x_5 \amp \leq -40, \\ \amp \amp -4x_{1} + 3x_{2} - 4x_{4} + 6 x_5 \amp \leq 24, \\ \text{and} \amp \amp x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geq 0.\end{aligned}
\end{equation*}
(a)
Show that \(\boldsymbol{x}'=\begin{bmatrix}66 \amp 96 \amp 0 \amp 0 \amp 0 \end{bmatrix}^{\intercal}\) is optimal.
Solution.
\begin{equation}
\begin{aligned} 2 y_1' + 3y_2' -4y_3' \amp = 5, \\ -y_1' -5y_2' + 3y_3' \amp = 4, \end{aligned}\tag{6.4.1}
\end{equation}
Also, when \(\boldsymbol{x}'=\begin{bmatrix}66 \amp 96 \amp 0 \amp 0 \amp 0 \end{bmatrix}^{\intercal}\)
\begin{equation*}
\begin{aligned} 2x_{1} -x_{2} + 3x_{3} + 6x_{5} \amp = 36 \\ 3x_{1} -5x_{2} - x_{3} + x_4 - 2x_5 \amp = -282 \lt -40 \\ -4x_{1} + 3x_{2} + x_{3} - 4x_{4} + 6 x_5 \amp = 24 \end{aligned}
\end{equation*}
and since the second inequality satisfies the second part of the CST, then \(y_{2}' = 0\text{.}\) Setting this in (6.4.1) and solving results in \(y_{1}'= 25/2\) and \(y_{3}'=11/2\) or
\begin{equation}
\boldsymbol{y} = \frac{1}{2} \begin{bmatrix} 25 \amp 0 \amp 11 \end{bmatrix}^{\intercal}\tag{6.4.2}
\end{equation}
Recall that for a point \(\boldsymbol{y}'\) to be \(D\)-feasible, that \(A^{\intercal} \boldsymbol{y}' \geq c\) and using the point in (6.4.2)
\begin{equation*}
A^{\intercal} \boldsymbol{y}' = \begin{bmatrix} 2 \amp 3 \amp -4 \\ -1 \amp -5 \amp 3 \\ 3 \amp -1 \amp 1 \\ 0 \amp 1 \amp 4 \\ 6 \amp -2 \amp 6 \end{bmatrix} \begin{bmatrix} 25/2 \\ 0 \\ 11/2 \end{bmatrix} = \begin{bmatrix} 3 \\ 4 \\ 43 \\ 22\\ 108 \end{bmatrix}
\end{equation*}
And this vector is \(\geq \boldsymbol{c}\text{,}\) therefore \(\boldsymbol{x}'\) is optimal
(b)
Show that \(\boldsymbol{x}'=(0,7,1,0,0)^{\intercal}\) is not optimal.
Solution.
From Theorem 6.4.1, we get that in order to be optimal,
\begin{equation*}
\begin{aligned}\text{since $x_{2}' > 0$} \amp \amp 2y_{1}+2y_{3} \amp = 8, \\ \text{since $x_{3}' > 0$} \amp \amp 3y_{1}+3y_{2}+y_{3} \amp = 15, \\\end{aligned}
\end{equation*}
and all equations are satisfied, implying that \(x_{6} =0, x_{7}=0, x_{8}=0\text{,}\) thus \(\boldsymbol{x}=(0,7,1,0,0~|~0,0,0)^{\intercal}\) thus in order to be optimal, \(\boldsymbol{y}=(+,+,+~|~+,0,0,+,+)\text{.}\)
The solution to the equation above is:
\begin{equation*}
\begin{aligned}y_{1} \amp = 4-t, \\ y_{2} \amp =(3+2t)/3, \\ y_{3} \amp = t.\end{aligned}
\end{equation*}
for all values of \(t\text{,}\) however substituting these into the 1st, 4th, and 5th equations of the dual problem
\begin{equation*}
\begin{aligned}y_{1} - y_{2} + y_{3} \amp = (4-t)-(3+2t)/3+t = 3-2t/3 \geq 5 \\ 4y_{1} -y_{3} \amp = (4-t)-t = 4-2t \geq 20, \\ 5y_{1}-y_{2} \amp = 5(4-t)-(3+2t)/3 = 19-17t/3 \geq 13.\end{aligned}
\end{equation*}
Note from the fact that \(y_{3}=t\geq0\text{,}\) that the first constraint above is not satisfied, so this is not \(D\)-feasible.
