Exercise 9.1
\[\begin{split}\begin{array}{cc|ccccccc}
l & & & & \boxed{0} & & \boxed{0} & &\\
& u & & & 6 & & 8 & &\\
\hline
& & \zeta & = & -x_1 & + & x_2 & = & 0\\
\hline
-\infty & 5 & w_1 & = & -x_1 & + & x_2 & = & 0\\
-\infty & 9 & w_2 & = & x_1 & - & 2 x_2 & = & 0
\end{array}\end{split}\]
The initial primal dictionary is feasible.
\(x_2\) is the only choice as the entering variable. \(w_1\) is the
leaving variable because its upper bound is the first constraint encountered
when maximizing \(x_2\).
\[\begin{split}\begin{array}{cc|ccccccc}
l & & & & \boxed{0} & & -\infty & &\\
& u & & & 6 & & \boxed{5} & &\\
\hline
& & \zeta & = & & & w_1 & = & 5\\
\hline
0 & 8 & x_2 & = & x_1 & + & w_1 & = & 5\\
-\infty & 9 & w_2 & = & -x_1 & - & 2 w_1 & = & -10
\end{array}\end{split}\]
\(w_1\) is already at its upper bound, so it cannot be the entering variable
even though its coefficient is positive. Therefore, with \(x_1\)’s
coefficient being zero, the current solution is optimal.
Exercise 9.2
Rewriting the LP to the form in (9.1) yields
\[\begin{split}\mathcal{P} \quad \text{maximize} \quad
-3 x_1 - x_2 + x_3 + 2 x_4 - x_5 + x_6 - x_7 - 4 x_8 &\\
\text{subject to} \quad
7 \leq x_1 + 4 x_3 + x_4 - 5 x_5 - 2 x_6 + 3 x_7 - 6 x_8 &\leq 7\\
-3 \leq x_2 - 3 x_3 - x_4 + 4 x_5 + x_6 - 2 x_7 + 5 x_8 &\leq -3\\
0 \leq x_1 &\leq 8\\
0 \leq x_2 &\leq 6\\
0 \leq x_3 &\leq 10\\
0 \leq x_4 &\leq 15\\
0 \leq x_5 &\leq 2\\
0 \leq x_6 &\leq 10\\
0 \leq x_7 &\leq 4\\
0 \leq x_8 &\leq 3.\end{split}\]
Imposing the complementarity conditions results in (9.4)
\[\begin{split}\mathcal{D} \quad \text{minimize} \quad
7 y_1^+ - 3 y_2^+ - 7 y_1^- + 3 y_2^- +
8 z_1^+ + 6 z_2^+ + 10 z_3^+ + 15 z_4^+ +
2 z_5^+ + 10 z_6^+ + 4 z_7^+ + 3 z_8^+ &\\
\text{subject to} \quad
y_1 - z_1 &= -3\\
y_2 - z_2 &= -1\\
4 y_1 - 3 y_2 - z_3 &= 1\\
y_1 - y_2 - z_4 &= 2\\
-5 y_1 + 4 y_2 - z_5 &= -1\\
-2 y_1 + y_2 - z_6 &= 1\\
3 y_1 - 2 y_2 - z_7 &= -1\\
-6 y_1 + 5 y_2 - z_8 &= -4.\end{split}\]
The generalized dual simplex method proposed in the book is not descriptive
enough to solve this systematically. It is much simpler to convert the original
primal LP to the usual standard form [Bur] and apply the usual dual
simplex method. The solution is then
\[(x_1, \ldots, x_8) =
(0, 6, 1, 15, 2, 1, 0, 0)
\quad \text{and} \quad
\zeta = 24.\]