The Simplex Method in Matrix Notation

Exercise 6.1

(a)

\[\mathcal{B} = \{ 3, 1 \} \quad \land \quad \mathcal{N} = \{ 2, 4, 5 \}\]

(b)

\[\begin{split}x^*_\mathcal{B} = \begin{bmatrix} x^*_3\\ x^*_1 \end{bmatrix} = \begin{bmatrix} 2\\ 0 \end{bmatrix}\end{split}\]

(c)

\[\begin{split}z^*_\mathcal{N} = -c_\mathcal{N} = \begin{bmatrix} z^*_4\\ z^*_2 \end{bmatrix} = \begin{bmatrix} 3\\ -2 \end{bmatrix}\end{split}\]

(d)

\[\begin{split}B^{-1} N = \begin{bmatrix} 1 & -4 & 2\\ -2 & 1 & -3 \end{bmatrix}\end{split}\]

(e)

Applying (6.10) shows that the associated current primal solution is feasible.

(f)

Since \(z^*_\mathcal{N}\) has some negative components, the current solution is not optimal.

(g)

The dictionary is degenerate because one of its basic variables is zero.

Exercise 6.2

(a)

\[\begin{split}\mathcal{B} = \{ 6, 7 \} \quad \land \quad B = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}\end{split}\]

(b)

\[\begin{split}\mathcal{N} = \{ 1, 2, 3, 4, 5 \} \quad \land \quad N = \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 7 & 5 & -3 & -2 & 0 \end{bmatrix}\end{split}\]

(c)

\[\begin{split}b = \begin{bmatrix} 2\\ 0 \end{bmatrix}\end{split}\]

(d)

\[\begin{split}c_\mathcal{B} = \begin{bmatrix} 0\\ 0 \end{bmatrix}\end{split}\]

(e)

\[\begin{split}c_\mathcal{N} = \begin{bmatrix} 1\\ 2\\ 4\\ 8\\ 16 \end{bmatrix}\end{split}\]

(f)

\[B^{-1} N = N\]

(g)

\[x^*_\mathcal{B} = B^{-1} b = b\]

(h)

\[\zeta^* = c_\mathcal{B}^\top B^{-1} b = \boldsymbol{0}\]

(i)

\[\begin{split}z^*_\mathcal{N} = \left( B^{-1} N \right)^\top c_\mathcal{B} - c_\mathcal{N} = -c_\mathcal{N} = \begin{bmatrix} -1\\ -2\\ -4\\ -8\\ -16 \end{bmatrix}\end{split}\]

(j)

The primal dictionary in succinct form (6.10) is

\[\begin{split}\zeta &= \zeta^* - {z^*_\mathcal{N}}^\top x_\mathcal{N} = \boldsymbol{0} - \begin{bmatrix} -1\\ -2\\ -4\\ -8\\ -16 \end{bmatrix}^\top \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5 \end{bmatrix} = x_1 + 2 x_2 + 4 x_3 + 8 x_4 + 16 x_5\end{split}\]

\[\begin{split}x_\mathcal{B} &= x^*_\mathcal{B} - B^{-1} N x_\mathcal{N}\\ &= \begin{bmatrix} 2\\ 0 \end{bmatrix} - \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 7 & 5 & -3 & -2 & 0 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5 \end{bmatrix}\\ \begin{bmatrix} x_6\\ x_7 \end{bmatrix} &= \begin{bmatrix} 2 - x_1 - 2 x_2 - 4 x_3 - 8 x_4 - 16 x_5\\ -7 x_1 - 5 x_2 + 3 x_3 + 2 x_4 \end{bmatrix}.\end{split}\]

Exercise 6.3

Rewriting Exercise 2.1 into matrix form yields

\[\begin{split}\mathcal{B} &= \{ 5, 6 \} \quad & \quad \mathcal{N} &= \{ 1, 2, 3, 4 \}\\ B &= \mathbf{I}_2 \quad & \quad N &= \begin{bmatrix} 2 & 1 & 1 & 3\\ 1 & 3 & 1 & 2 \end{bmatrix}\\ x^*_\mathcal{B} &= b = \begin{bmatrix} 5\\ 3 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= -c_\mathcal{N} = \begin{bmatrix} -6\\ -8\\ -5\\ -9 \end{bmatrix}.\end{split}\]

Iteration 1

Step 1

Since \(z^*_\mathcal{N}\) has some negative components, the current solution is not optimal.

Step 2

Applying Bland’s rule restricts the entering variable index to \(j = 1 \in \mathcal{N}\).

Step 3

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \begin{bmatrix} 2 & 1 & 1 & 3\\ 1 & 3 & 1 & 2 \end{bmatrix} \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} 2\\ 1 \end{bmatrix}.\end{split}\]

Step 4

The primal step length is

\[t = \left( \max_{i \in \mathcal{B}} \frac{\Delta x_i}{x^*_i} \right)^{-1} = \left( \max \left\{ \frac{2}{5}, \frac{1}{3} \right\} \right)^{-1} = \frac{5}{2}.\]

Step 5

The leaving variable index is \(i = 5 \in \mathcal{B}\).

Step 6

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top \mathbf{e}_i = -\begin{bmatrix} 2 & 1\\ 1 & 3\\ 1 & 1\\ 3 & 2 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} -2\\ -1\\ -1\\ -3 \end{bmatrix}.\end{split}\]

Step 7

The dual step length is

\[s = \frac{z^*_j}{\Delta z_j} = \frac{-6}{-2} = 3.\]

Step 8

The current primal and dual solutions are updated to

\[\begin{split}x^*_\mathcal{B} \leftarrow x^*_\mathcal{B} - t \Delta x_\mathcal{B} = \begin{bmatrix} 5\\ 3 \end{bmatrix} - \frac{5}{2} \begin{bmatrix} 2\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ \frac{1}{2} \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = \frac{5}{2}\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} \leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} -6\\ -8\\ -5\\ -9 \end{bmatrix} - 3 \begin{bmatrix} -2\\ -1\\ -1\\ -3 \end{bmatrix} = \begin{bmatrix} 0\\ -5\\ -2\\ 0 \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = 3.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{ 1, 6 \} \quad & \quad \mathcal{N} &= \{ 5, 2, 3, 4 \}\\ B &= \begin{bmatrix} 2 & 0\\ 1 & 1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 1 & 1 & 1 & 3\\ 0 & 3 & 1 & 2 \end{bmatrix}\\ x^*_\mathcal{B} &= \begin{bmatrix} \frac{5}{2}\\ \frac{1}{2} \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \begin{bmatrix} 3\\ -5\\ -2\\ 0 \end{bmatrix}.\end{split}\]

Iteration 2

Step 1

Since \(z^*_\mathcal{N}\) has some negative components, the current solution is not optimal.

Step 2

Applying Bland’s rule restricts the entering variable index to \(j = 2 \in \mathcal{N}\).

Step 3

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \left( \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 3\\ -1 & 5 & 1 & 1 \end{bmatrix} \right) \begin{bmatrix} 0\\ 1\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{2}\\ \frac{5}{2} \end{bmatrix}.\end{split}\]

Step 4

The primal step length is

\[t = \left( \max_{i \in \mathcal{B}} \frac{\Delta x_i}{x^*_i} \right)^{-1} = \left( \max \left\{ \frac{0.5}{2.5}, \frac{2.5}{0.5} \right\} \right)^{-1} = \frac{1}{5}.\]

Step 5

The leaving variable index is \(i = 6 \in \mathcal{B}\).

Step 6

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top \mathbf{e}_i = -\left( \frac{1}{2} \begin{bmatrix} 1 & -1\\ 1 & 5\\ 1 & 1\\ 3 & 1 \end{bmatrix} \right) \begin{bmatrix} 0\\ 1 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1\\ -5\\ -1\\ -1 \end{bmatrix}.\end{split}\]

Step 7

The dual step length is

\[s = \frac{z^*_j}{\Delta z_j} = \frac{-5}{-5 / 2} = 2.\]

Step 8

The current primal and dual solutions are updated to

\[\begin{split}x^*_\mathcal{B} \leftarrow x^*_\mathcal{B} - t \Delta x_\mathcal{B} = \begin{bmatrix} \frac{5}{2}\\ \frac{1}{2} \end{bmatrix} - \frac{1}{5} \begin{bmatrix} \frac{1}{2}\\ \frac{5}{2} \end{bmatrix} = \begin{bmatrix} \frac{12}{5}\\ 0 \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = \frac{1}{5}\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} \leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} 3\\ -5\\ -2\\ 0 \end{bmatrix} - 2 \left( \frac{1}{2} \begin{bmatrix} 1\\ -5\\ -1\\ -1 \end{bmatrix} \right) = \begin{bmatrix} 2\\ 0\\ -1\\ 1 \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = 2.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{ 1, 2 \} \quad & \quad \mathcal{N} &= \{ 5, 6, 3, 4 \}\\ B &= \begin{bmatrix} 2 & 1\\ 1 & 3 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 1 & 0 & 1 & 3\\ 0 & 1 & 1 & 2 \end{bmatrix}\\ x^*_\mathcal{B} &= \begin{bmatrix} \frac{12}{5}\\ \frac{1}{5} \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \begin{bmatrix} 2\\ 2\\ -1\\ 1 \end{bmatrix}.\end{split}\]

Iteration 3

Step 1

Since \(z^*_\mathcal{N}\) has some negative components, the current solution is not optimal.

Step 2

Applying Bland’s rule restricts the entering variable index to \(j = 3 \in \mathcal{N}\).

Step 3

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \left( \frac{1}{5} \begin{bmatrix} 3 & -1 & 2 & 7\\ -1 & 2 & 1 & 1 \end{bmatrix} \right) \begin{bmatrix} 0\\ 0\\ 1\\ 0 \end{bmatrix} = \begin{bmatrix} \frac{2}{5}\\ \frac{1}{5} \end{bmatrix}.\end{split}\]

Step 4

The primal step length is

\[t = \left( \max_{i \in \mathcal{B}} \frac{\Delta x_i}{x^*_i} \right)^{-1} = \left( \max \left\{ \frac{0.4}{2.4}, \frac{0.2}{0.2} \right\} \right)^{-1} = 1.\]

Step 5

The leaving variable index is \(i = 2 \in \mathcal{B}\).

Step 6

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top \mathbf{e}_i = -\left( \frac{1}{5} \begin{bmatrix} 3 & -1\\ -1 & 2\\ 2 & 1\\ 7 & 1 \end{bmatrix} \right) \begin{bmatrix} 0\\ 1 \end{bmatrix} = \frac{1}{5} \begin{bmatrix} 1\\ -2\\ -1\\ -1 \end{bmatrix}.\end{split}\]

Step 7

The dual step length is

\[s = \frac{z^*_j}{\Delta z_j} = \frac{-1}{-1 / 5} = 5.\]

Step 8

The current primal and dual solutions are updated to

\[\begin{split}x^*_\mathcal{B} \leftarrow x^*_\mathcal{B} - t \Delta x_\mathcal{B} = \begin{bmatrix} \frac{12}{5}\\ \frac{1}{5} \end{bmatrix} - (1) \begin{bmatrix} \frac{2}{5}\\ \frac{1}{5} \end{bmatrix} = \begin{bmatrix} 2\\ 0 \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = 1\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} \leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} 2\\ 2\\ -1\\ 1 \end{bmatrix} - 5 \left( \frac{1}{5} \begin{bmatrix} 1\\ -2\\ -1\\ -1 \end{bmatrix} \right) = \begin{bmatrix} 1\\ 4\\ 0\\ 2 \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = 5.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{ 1, 3 \} \quad & \quad \mathcal{N} &= \{ 5, 6, 2, 4 \}\\ B &= \begin{bmatrix} 2 & 1\\ 1 & 1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 1 & 0 & 1 & 3\\ 0 & 1 & 3 & 2 \end{bmatrix}\\ x^*_\mathcal{B} &= \begin{bmatrix} 2\\ 1 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \begin{bmatrix} 1\\ 4\\ 5\\ 2 \end{bmatrix}.\end{split}\]

Iteration 4

Step 1

Since \(z^*_\mathcal{N}\) has all non-negative components, the current solution is optimal. The optimal objective function value is

\[\zeta^* = 6 x_1^* + 8 x_2^* + 5 x_3^* + 9 x_4^* = 17.\]

Exercise 6.4

Rewriting Exercise 2.4 into matrix form yields

\[\begin{split}\mathcal{B} &= \{ 4, 5 \} \quad & \quad \mathcal{N} &= \{ 1, 2, 3 \}\\ B &= \mathbf{I}_2 \quad & \quad N &= \begin{bmatrix} 2 & -5 & 1\\ 2 & -1 & 2 \end{bmatrix}\\ x^*_\mathcal{B} &= b = \begin{bmatrix} -5\\ 4 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= -c_\mathcal{N} = \begin{bmatrix} 1\\ 3\\ 1 \end{bmatrix}.\end{split}\]

Iteration 1

Step 1

Since \(x^*_\mathcal{B}\) has some negative components, the current solution is not optimal.

Step 2

Applying Bland’s rule restricts the entering variable index to \(i = 4 \in \mathcal{B}\).

Step 3

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top \mathbf{e}_i = -\begin{bmatrix} 2 & 2\\ -5 & -1\\ 1 & 2 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} -2\\ 5\\ -1 \end{bmatrix}.\end{split}\]

Step 4

The dual step length is

\[s = \left( \max_{j \in \mathcal{N}} \frac{\Delta z_j}{z^*_j} \right)^{-1} = \left( \max \left\{ \frac{-2}{1}, \frac{5}{3}, \frac{-1}{1} \right\} \right)^{-1} = \frac{3}{5}.\]

Step 5

The leaving variable index is \(j = 2 \in \mathcal{N}\).

Step 6

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \begin{bmatrix} 2 & -5 & 1\\ 2 & -1 & 2 \end{bmatrix} \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix} = \begin{bmatrix} -5\\ -1 \end{bmatrix}.\end{split}\]

Step 7

The primal step length is

\[t = \frac{x^*_i}{\Delta x_i} = \frac{-5}{-5} = 1.\]

Step 8

The current primal and dual solutions are updated to

\[\begin{split}x^*_\mathcal{B} \leftarrow x^*_\mathcal{B} - t \Delta x_\mathcal{B} = \begin{bmatrix} -5\\ 4 \end{bmatrix} - (1) \begin{bmatrix} -5\\ -1 \end{bmatrix} = \begin{bmatrix} 0\\ 5 \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = 1\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} \leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 3\\ 1 \end{bmatrix} - \frac{3}{5} \begin{bmatrix} -2\\ 5\\ -1 \end{bmatrix} = \begin{bmatrix} \frac{11}{5}\\ 0\\ \frac{8}{5} \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = \frac{3}{5}.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{ 2, 5 \} \quad & \quad \mathcal{N} &= \{ 1, 4, 3 \}\\ B &= \begin{bmatrix} -5 & 0\\ -1 & 1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 2 & 1 & 1\\ 2 & 0 & 2 \end{bmatrix}\\ x^*_\mathcal{B} &= \begin{bmatrix} 1\\ 5 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \begin{bmatrix} \frac{11}{5}\\ \frac{3}{5}\\ \frac{8}{5} \end{bmatrix}.\end{split}\]

Iteration 2

Step 1

Since \(x^*_\mathcal{B}\) has all non-negative components, the current solution is optimal. The optimal objective function value is

\[\zeta^* = -x_1^* - 3 x_2^* - x_3^* = -3.\]

Exercise 6.5

Rewriting Exercise 2.3 into matrix form yields

\[\begin{split}\mathcal{B} &= \{ 4, 5 \} \quad & \quad \mathcal{N} &= \{ 1, 2, 3 \}\\ B &= \mathbf{I}_2 \quad & \quad N &= \begin{bmatrix} -1 & -1 & -1\\ 2 & -1 & 1 \end{bmatrix}\\ x^*_\mathcal{B} &= b = \begin{bmatrix} -2\\ 1 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= -c_\mathcal{N} = \begin{bmatrix} -2\\ 6\\ 0 \end{bmatrix}.\end{split}\]

Since both \(b\) and \(c_\mathcal{N}\) have some negative components, arbitrarily set \(c_\mathcal{N} = \begin{bmatrix} -1\\ -1\\ -1 \end{bmatrix}\) to make the problem dual feasible.

Iteration 1

Step 1

Since \(x^*_\mathcal{B}\) has some negative components, the current solution is not optimal.

Step 2

Applying Bland’s rule restricts the entering variable index to \(i = 4 \in \mathcal{B}\).

Step 3

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top \mathbf{e}_i = -\begin{bmatrix} -1 & 2\\ -1 & -1\\ -1 & 1 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}.\end{split}\]

Step 4

The dual step length is

\[s = \left( \max_{j \in \mathcal{N}} \frac{\Delta z_j}{z^*_j} \right)^{-1} = \left( \max \left\{ \frac{1}{1}, \frac{1}{1}, \frac{1}{1} \right\} \right)^{-1} = 1.\]

Step 5

Applying Bland’s rule restricts the leaving variable index to \(j = 1 \in \mathcal{N}\).

Step 6

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \begin{bmatrix} -1 & -1 & -1\\ 2 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} -1\\ 2 \end{bmatrix}.\end{split}\]

Step 7

The primal step length is

\[t = \frac{x^*_i}{\Delta x_i} = \frac{-2}{-1} = 2.\]

Step 8

The current primal and dual solutions are updated to

\[\begin{split}x^*_\mathcal{B} \leftarrow x^*_\mathcal{B} - t \Delta x_\mathcal{B} = \begin{bmatrix} -2\\ 1 \end{bmatrix} - (2) \begin{bmatrix} -1\\ 2 \end{bmatrix} = \begin{bmatrix} 0\\ -3 \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = 2\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} \leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} - (1) \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = 1.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{ 1, 5 \} \quad & \quad \mathcal{N} &= \{ 4, 2, 3 \}\\ B &= \begin{bmatrix} -1 & 0\\ 2 & 1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 1 & -1 & -1\\ 0 & -1 & 1 \end{bmatrix}\\ x^*_\mathcal{B} &= \begin{bmatrix} 2\\ -3 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}.\end{split}\]

Iteration 2

Step 1

Since \(x^*_\mathcal{B}\) has some negative components, the current solution is not optimal.

Step 2

Applying Bland’s rule restricts the entering variable index to \(i = 5 \in \mathcal{B}\).

Step 3

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top \mathbf{e}_i = -\begin{bmatrix} -1 & 2\\ 1 & -3\\ 1 & -1 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} -2\\ 3\\ 1 \end{bmatrix}.\end{split}\]

Step 4

The dual step length is

\[s = \left( \max_{j \in \mathcal{N}} \frac{\Delta z_j}{z^*_j} \right)^{-1} = \left( \max \left\{ \frac{-2}{1}, \frac{3}{0}, \frac{1}{0} \right\} \right)^{-1} = 0.\]

Step 5

Applying Bland’s rule restricts the leaving variable index to \(j = 2 \in \mathcal{N}\).

Step 6

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \begin{bmatrix} -1 & 1 & 1\\ 2 & -3 & -1 \end{bmatrix} \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix} = \begin{bmatrix} 1\\ -3 \end{bmatrix}.\end{split}\]

Step 7

The primal step length is

\[t = \frac{x^*_i}{\Delta x_i} = \frac{-3}{-3} = 1.\]

Step 8

The current primal and dual solutions are updated to

\[\begin{split}x^*_\mathcal{B} \leftarrow x^*_\mathcal{B} - t \Delta x_\mathcal{B} = \begin{bmatrix} 2\\ -3 \end{bmatrix} - (1) \begin{bmatrix} 1\\ -3 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = 1\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} \leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} - (0) \begin{bmatrix} -2\\ 3\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = 0.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{ 1, 2 \} \quad & \quad \mathcal{N} &= \{ 4, 5, 3 \}\\ B &= \begin{bmatrix} -1 & -1\\ 2 & -1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 1 & 0 & -1\\ 0 & 1 & 1 \end{bmatrix}\\ x^*_\mathcal{B} &= \begin{bmatrix} 1\\ 1 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}.\end{split}\]

Iteration 3

Since \(x^*_\mathcal{B}\) has all non-negative components, the current solution is optimal for the modified objective. The original objective

\[\begin{split}c_\mathcal{N'} x_\mathcal{N'} = \begin{bmatrix} 2 & -6 & 0 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = 2 x_1 - 6 x_2\end{split}\]

can be reinstated by setting

\[\begin{split}z^*_\mathcal{N} = \left( B^{-1} N \right)^\top c_{\mathcal{N'} \cap \mathcal{B}}+ \sum_{j \in \mathcal{N'} \cap \mathcal{N}} c_j e_j = \left( \frac{1}{3} \begin{bmatrix} -1 & 1 & 2\\ -2 & -1 & 1 \end{bmatrix} \right)^\top \begin{bmatrix} 2\\ -6 \end{bmatrix} + 0 e_3 = \frac{1}{3} \begin{bmatrix} 10\\ 8\\ -2 \end{bmatrix}\end{split}\]

where \(c_{\mathcal{N'} \cap \mathcal{B}}\) is a vector whose elements are zero when the corresponding variable index \(i \in \mathcal{B} \setminus \mathcal{N'}\).

Step 1

Since \(z^*_\mathcal{N}\) has some negative components, the current solution is not optimal.

Step 2

Applying Bland’s rule restricts the entering variable index to \(j = 3 \in \mathcal{N}\).

Step 3

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \frac{1}{3} \begin{bmatrix} -1 & 1 & 2\\ -2 & -1 & 1 \end{bmatrix} \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} = \begin{bmatrix} \frac{2}{3}\\ \frac{1}{3} \end{bmatrix}.\end{split}\]

Step 4

The primal step length is

\[t = \left( \max_{i \in \mathcal{B}} \frac{\Delta x_i}{x^*_i} \right)^{-1} = \left( \max \left\{ \frac{2 / 3}{1}, \frac{1 / 3}{1} \right\} \right)^{-1} = \frac{3}{2}.\]

Step 5

The leaving variable index is \(i = 1 \in \mathcal{B}\).

Step 6

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top \mathbf{e}_i = -\frac{1}{3} \begin{bmatrix} -1 & -2\\ 1 & -1\\ 2 & 1 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{3}\\ \frac{-1}{3}\\ \frac{-2}{3} \end{bmatrix}.\end{split}\]

Step 7

The dual step length is

\[s = \frac{z^*_j}{\Delta z_j} = \frac{-2 / 3}{-2 / 3} = 1.\]

Step 8

The current primal and dual solutions are updated to

\[\begin{split}x^*_\mathcal{B} \leftarrow x^*_\mathcal{B} - t \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 1 \end{bmatrix} - \frac{3}{2} \begin{bmatrix} \frac{2}{3}\\ \frac{1}{3} \end{bmatrix} = \begin{bmatrix} 0\\ \frac{1}{2} \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = \frac{3}{2}\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} \leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \frac{1}{3} \begin{bmatrix} 10\\ 8\\ -2 \end{bmatrix} - \frac{1}{3} \begin{bmatrix} 1\\ -1\\ -2 \end{bmatrix} = \frac{1}{3} \begin{bmatrix} 9\\ 9\\ 4 \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = 1.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{ 3, 2 \} \quad & \quad \mathcal{N} &= \{ 4, 5, 1 \}\\ B &= \begin{bmatrix} -1 & -1\\ 1 & -1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 1 & 0 & -1\\ 0 & 1 & 2 \end{bmatrix}\\ x^*_\mathcal{B} &= \begin{bmatrix} \frac{3}{2}\\ \frac{1}{2} \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \begin{bmatrix} 3\\ 3\\ 1 \end{bmatrix}.\end{split}\]

Iteration 4

Step 1

Since \(z^*_\mathcal{N}\) has all non-negative components, the current solution is optimal. The optimal objective function value is

\[\zeta^* = 2 x_1^* - 6 x_2^* = -3.\]

Exercise 6.6

Rewriting the LP in standard form according to [Bur] yields

\[\begin{split}\begin{aligned} \mathcal{P} \quad \text{maximize} \quad \mathbf{c}^\top \mathbf{w} + \mathbf{c}^\top \mathbf{l} &\\ \text{subject to} \quad \mathbf{A} \mathbf{w} &\leq \mathbf{b} - \mathbf{A} \mathbf{l}\\ -\mathbf{A} \mathbf{w} &\leq -\mathbf{a} + \mathbf{A} \mathbf{l}\\ 0 &\leq \mathbf{w} \end{aligned}\end{split}\]

where \(\mathbf{w} = \mathbf{x} - \mathbf{l}\). Note that the constant \(\mathbf{c}^\top \mathbf{l}\) in the objective function can and will be ignored in the following analysis.

The dual of \(\mathcal{P}\) is

\[\begin{split}\begin{aligned} \mathcal{D} \quad \text{minimize} \quad \mathbf{y}_b^\top \left( \mathbf{b} - \mathbf{A} \mathbf{l} \right) + \mathbf{y}_a^\top \left( -\mathbf{a} + \mathbf{A} \mathbf{l} \right) &\\ \text{subject to} \quad \mathbf{A}^\top \left( \mathbf{y}_b - \mathbf{y}_a \right) &\geq \mathbf{c}\\ 0 &\leq \mathbf{y}_a, \mathbf{y}_b \end{aligned} \quad = \quad \begin{aligned} -\mathcal{D} \quad \text{maximize} \quad -\mathbf{y}_b^\top \left( \mathbf{b} - \mathbf{A} \mathbf{l} \right) - \mathbf{y}_a^\top \left( -\mathbf{a} + \mathbf{A} \mathbf{l} \right) &\\ \text{subject to} \quad \mathbf{A}^\top \left( \mathbf{y}_a - \mathbf{y}_b \right) &\leq -\mathbf{c}\\ 0 &\leq \mathbf{y}_a, \mathbf{y}_b. \end{aligned}\end{split}\]

Observe that the dual to \(\mathcal{D}\) is indeed \(\mathcal{P}\):

\[\begin{split}\begin{aligned} \mathcal{P} \quad \text{minimize} \quad -\mathbf{c}^\top \mathbf{w} &\\ \text{subject to} \quad -\mathbf{A} \mathbf{w} &\leq -\mathbf{b} + \mathbf{A} \mathbf{l}\\ \mathbf{A} \mathbf{w} &\leq \mathbf{a} - \mathbf{A} \mathbf{l}\\ 0 &\leq \mathbf{w} \end{aligned} \quad = \quad \begin{aligned} \mathcal{P} \quad \text{maximize} \quad \mathbf{c}^\top \mathbf{w} &\\ \text{subject to} \quad \mathbf{A} \mathbf{w} &\leq \mathbf{b} - \mathbf{A} \mathbf{l}\\ -\mathbf{A} \mathbf{w} &\leq -\mathbf{a} + \mathbf{A} \mathbf{l}\\ 0 &\leq \mathbf{w}. \end{aligned}\end{split}\]

Exercise 6.7

Computing the gradient is not useful for this problem because the only constraints are \(x, y \geq 0\). The optimization can be carried out through reasoning in 1D without loss of generality.

(a)

Define

\[\begin{split}p(x) &= \min_{y \geq 0} c^\top x - y^\top A x + b^\top y\\ &= c^\top x + \min_{y \geq 0} y^\top (b - A x)\\ &= c^\top x + \begin{cases} 0 & \text{if } Ax \leq b\\ -\infty & \text{otherwise.} \end{cases}\end{split}\]

The primal LP is

\[\begin{split}\mathcal{P} \quad \max_{x \geq 0} p(x) = \text{maximize} \quad c^\top x&\\ \text{subject to} \quad Ax &\leq b\\ 0 &\leq x.\end{split}\]

(b)

Define

\[\begin{split}d(y) &= \max_{x \geq 0} c^\top x - y^\top A x + b^\top y\\ &= b^\top y + \max_{x \geq 0} \left( c - A^\top y \right)^\top x\\ &= b^\top y + \begin{cases} 0 & \text{if } A^\top y \geq c\\ \infty & \text{otherwise.} \end{cases}\end{split}\]

The dual LP is

\[\begin{split}\mathcal{D} \quad \min_{y \geq 0} d(y) = \text{minimize} \quad b^\top y&\\ \text{subject to} \quad A^\top y &\geq c\\ 0 &\leq y.\end{split}\]