Consider the linear program illustrated in Figure 7.9, $$
\min _{\boldsymbol{x} \in \mathbb{R}^{2}}\quad -\left[\begin{array}{l}
5 \\
3
\end{array}\right]^{\top}\left[\begin{array}{l}
x_{1} \\
x_{2}
\end{array}\right]
$$ $$
\text { subject to }\quad \left[\begin{array}{cc}
2 & 2 \\
2 & -4 \\
-2 & 1 \\
0 & -1 \\
0 & 1
\end{array}\right]\left[\begin{array}{l}
x_{1} \\
x_{2}
\end{array}\right] \leqslant\left[\begin{array}{c}
33 \\
8 \\
5 \\
-1 \\
8
\end{array}\right]
$$ Derive the dual linear program using Lagrange duality.
Solution: We use (7.43) on Page 239 directly. Note that in this case, see (7.39), we have $$\boldsymbol c=-\left[\begin{array}{l}
5 \\
3
\end{array}\right],\quad \boldsymbol b=\left[\begin{array}{c}
33 \\
8 \\
5 \\
-1 \\
8
\end{array}\right],$$ $$\boldsymbol A=\left[\begin{array}{cc}
2 & 2 \\
2 & -4 \\
-2 & 1 \\
0 & -1 \\
0 & 1
\end{array}\right].$$By (7.43), the dual linear program is $$
\max _{\boldsymbol{\lambda} \in \mathbb{R}^{5}}\quad -\left[\begin{array}{c}
33 \\
8 \\
5 \\
-1 \\
8
\end{array}\right]^{\top}\left[\begin{array}{c}
\lambda_{1} \\
\lambda_{2} \\
\lambda_{3} \\
\lambda_{4} \\
\lambda_{5}
\end{array}\right]
$$ $$
\text { subject to } \quad -\left[\begin{array}{l}
5 \\
3
\end{array}\right]+\left[\begin{array}{cc}
2 & 2 \\
2 & -4 \\
-2 & 1 \\
0 & -1 \\
0 & 1
\end{array}\right]^\top \left[\begin{array}{c}
\lambda_{1} \\
\lambda_{2} \\
\lambda_{3} \\
\lambda_{4} \\
\lambda_{5}
\end{array}\right]=0
$$ $$\left[\begin{array}{c}
\lambda_{1} \\
\lambda_{2} \\
\lambda_{3} \\
\lambda_{4} \\
\lambda_{5}
\end{array}\right]\geqslant 0.$$
