Sensitivity and Parametric Analyses

The Advanced Simplex Pivot Tool is useful for verifying the application of the self-dual simplex method.

3. The Parametric Self-Dual Simplex Method

Figure 7.1 incorrectly lists the \(arg\,max\) criterion. [Eng] illustrates in Figure 4.2 that it is more appropriate to take the \(arg\,min\) and only select among the ratios with a positive denominator.

Exercise 7.1

The matrix form of the original dictionary is

\[\begin{split}\mathcal{B} &= \{5, 6, 7\} \quad & \quad \mathcal{N} &= \{1, 2, 3, 4\}\\ B &= \mathbf{I}_3 \quad & \quad N &= \begin{bmatrix} 2 & 1 & 5 & 1\\ 2 & 2 & 0 & 4\\ 3 & 1 & 2 & 0 \end{bmatrix}\\ x^*_\mathcal{B} &= B^{-1} b = \begin{bmatrix} 8\\ 12\\ 18 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \left( B^{-1} N \right)^\top c_\mathcal{B} - c_\mathcal{N} = \begin{bmatrix} -1\\ -2\\ -1\\ -1 \end{bmatrix}.\end{split}\]

The matrix form of the final dictionary is

\[\begin{split}\mathcal{B} &= \{2, 3, 7\} \quad & \quad \mathcal{N} &= \{1, 5, 6, 4\}\\ B &= \begin{bmatrix} 1 & 5 & 0\\ 2 & 0 & 0\\ 1 & 2 & 1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 2 & 1 & 0 & 1\\ 2 & 0 & 1 & 4\\ 3 & 0 & 0 & 0 \end{bmatrix}\\ x^*_\mathcal{B} &= B^{-1} b = \begin{bmatrix} 6\\ 0.4\\ 11.2 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \left( B^{-1} N \right)^\top c_\mathcal{B} - c_\mathcal{N} = \begin{bmatrix} 1.2\\ 0.2\\ 0.9\\ 2.8 \end{bmatrix}.\end{split}\]

(a)

Changing the original objective function to \(3 x_1 + 2 x_2 + x_3 + x_4\) requires recomputing

\[\begin{split}z^*_\mathcal{N} = \left( B^{-1} N \right)^\top c_\mathcal{B} - c_\mathcal{N} = \left( B^{-1} N \right)^\top \begin{bmatrix} 2\\ 1\\ 0 \end{bmatrix} - \begin{bmatrix} 3\\ 0\\ 0\\ 1 \end{bmatrix} = \begin{bmatrix} -0.8\\ 0.2\\ 0.9\\ 2.8 \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} 1 & 0 & 0.5 & 2\\ 0.2 & 0.2 & -0.1 & -0.2\\ 1.6 & -0.4 & -0.3 & -1.6 \end{bmatrix} \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} 1\\ 0.2\\ 1.6 \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{1}{6}, \frac{0.2}{0.4}, \frac{1.6}{11.2} \right\} \right)^{-1} = 2.\]

Step 5

The leaving variable index is \(i = 3 \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} 1 & 0.2 & 1.6\\ 0 & 0.2 & -0.4\\ 0.5 & -0.1 & -0.3\\ 2 & -0.2 & -1.6 \end{bmatrix} \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix} = \begin{bmatrix} -0.2\\ -0.2\\ 0.1\\ 0.2 \end{bmatrix}.\end{split}\]

Step 7

The dual step length is

\[s = \frac{z^*_j}{\Delta z_j} = \frac{-0.8}{-0.2} = 4.\]

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} 6\\ 0.4\\ 11.2 \end{bmatrix} - 2 \begin{bmatrix} 1\\ 0.2\\ 1.6 \end{bmatrix} = \begin{bmatrix} 4\\ 0\\ 8 \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} -0.8\\ 0.2\\ 0.9\\ 2.8 \end{bmatrix} - 4 \begin{bmatrix} -0.2\\ -0.2\\ 0.1\\ 0.2 \end{bmatrix} = \begin{bmatrix} 0\\ 1\\ 0.5\\ 2 \end{bmatrix} \quad \land \quad z^*_i \leftarrow s = 4.\end{split}\]

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{2, 1, 7\} \quad & \quad \mathcal{N} &= \{3, 5, 6, 4\}\\ B &= \begin{bmatrix} 1 & 2 & 0\\ 2 & 2 & 0\\ 1 & 3 & 1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 5 & 1 & 0 & 1\\ 0 & 0 & 1 & 4\\ 2 & 0 & 0 & 0 \end{bmatrix}\\ x^*_\mathcal{B} &= B^{-1} b = \begin{bmatrix} 4\\ 2\\ 8 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \left( B^{-1} N \right)^\top c_\mathcal{B} - c_\mathcal{N} = \begin{bmatrix} 4\\ 1\\ 0.5\\ 2 \end{bmatrix}.\end{split}\]

Iteration 2

Step 1

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

\[\zeta^* = 3 x_1^* + 2 x_2^* + x_3^* + x_4^* = 14.\]

(b)

Changing the original objective function to \(x_1 + 2 x_2 + 0.5 x_3 + x_4\) requires recomputing

\[\begin{split}z^*_\mathcal{N} = \left( B^{-1} N \right)^\top c_\mathcal{B} - c_\mathcal{N} = \left( B^{-1} N \right)^\top \begin{bmatrix} 2\\ 0.5\\ 0 \end{bmatrix} - \begin{bmatrix} 1\\ 0\\ 0\\ 1 \end{bmatrix} = \begin{bmatrix} 1.1\\ 0.1\\ 0.95\\ 2.9 \end{bmatrix}.\end{split}\]

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

\[\zeta^* = x_1^* + 2 x_2^* + 0.5 x_3^* + x_4^* = 12.2.\]

(c)

Changing the original second constraint’s RHS to \(26\) requires recomputing

\[\begin{split}x^*_\mathcal{B} = B^{-1} b = B^{-1} \begin{bmatrix} 8\\ 26\\ 18 \end{bmatrix} = \begin{bmatrix} 13\\ -1\\ 7 \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 = 3 \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 & 0.2 & 1.6\\ 0 & 0.2 & -0.4\\ 0.5 & -0.1 & -0.3\\ 2 & -0.2 & -1.6 \end{bmatrix} \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix} = \begin{bmatrix} -0.2\\ -0.2\\ 0.1\\ 0.2 \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{-0.2}{1.2}, \frac{-0.2}{0.2}, \frac{0.1}{0.9}, \frac{0.2}{2.8} \right\} \right)^{-1} = 9.\]

Step 5

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

Step 6

The primal step direction is

\[\begin{split}\Delta x_\mathcal{B} = B^{-1} N e_j = \begin{bmatrix} 1 & 0 & 0.5 & 2\\ 0.2 & 0.2 & -0.1 & -0.2\\ 1.6 & -0.4 & -0.3 & -1.6 \end{bmatrix} \begin{bmatrix} 0\\ 0\\ 1\\ 0 \end{bmatrix} = \begin{bmatrix} 0.5\\ -0.1\\ -0.3 \end{bmatrix}.\end{split}\]

Step 7

The primal step length is

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

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} 13\\ -1\\ 7 \end{bmatrix} - (10) \begin{bmatrix} 0.5\\ -0.1\\ -0.3 \end{bmatrix} = \begin{bmatrix} 8\\ 0\\ 10 \end{bmatrix} \quad \land \quad x^*_j \leftarrow t = 10\end{split}\]

and

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

Step 9

The current basis is updated to

\[\begin{split}\mathcal{B} &= \{2, 6, 7\} \quad & \quad \mathcal{N} &= \{1, 5, 3, 4\}\\ B &= \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix} \quad & \quad N &= \begin{bmatrix} 2 & 1 & 5 & 1\\ 2 & 0 & 0 & 4\\ 3 & 0 & 2 & 0 \end{bmatrix}\\ x^*_\mathcal{B} &= B^{-1} b = \begin{bmatrix} 8\\ 10\\ 10 \end{bmatrix} \quad & \quad z^*_\mathcal{N} &= \left( B^{-1} N \right)^\top c_\mathcal{B} - c_\mathcal{N} = \begin{bmatrix} 3\\ 2\\ 9\\ 1 \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

\[\begin{split}\zeta^* = c_\mathcal{B}^\top B^{-1} b = \begin{bmatrix} 2 & 0 & 0 \end{bmatrix} B^{-1} \begin{bmatrix} 8\\ 26\\ 18 \end{bmatrix} = 16.\end{split}\]

Exercise 7.2

\(\Delta c = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}^\top\)

Partitioning \(\Delta c\) according to the final optimal basis gives

\[\begin{split}\Delta c_\mathcal{B} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \quad \text{and} \quad \Delta c_\mathcal{N} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}.\end{split}\]

Applying (7.1) yields

\[\begin{split}\Delta z_\mathcal{N} = \left( B^{-1} N \right)^\top \Delta c_\mathcal{B} - \Delta c_\mathcal{N} = \begin{bmatrix} 1 & 0.2 & 1.6\\ 0 & 0.2 & -0.4\\ 0.5 & -0.1 & -0.3\\ 2 & -0.2 & -1.6 \end{bmatrix} \begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix} - \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} -1 \\ 0 \\ 0 \\ 0 \end{bmatrix}\end{split}\]

The current basis will remain optimal as long as (7.2)

\[\begin{split}z^*_\mathcal{N} + t \Delta z_\mathcal{N} = \begin{bmatrix} 1.2\\ 0.2\\ 0.9\\ 2.8 \end{bmatrix} + t \begin{bmatrix} -1 \\ 0 \\ 0 \\ 0 \end{bmatrix} \geq 0 \quad \iff \quad t \leq 1.2.\end{split}\]

\(\Delta c = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}^\top\)

Partitioning \(\Delta c\) according to the final optimal basis gives

\[\begin{split}\Delta c_\mathcal{B} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \quad \text{and} \quad \Delta c_\mathcal{N} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}.\end{split}\]

Applying (7.1) yields

\[\begin{split}\Delta z_\mathcal{N} = \left( B^{-1} N \right)^\top \Delta c_\mathcal{B} - \Delta c_\mathcal{N} = \begin{bmatrix} 1 & 0.2 & 1.6\\ 0 & 0.2 & -0.4\\ 0.5 & -0.1 & -0.3\\ 2 & -0.2 & -1.6 \end{bmatrix} \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} - \begin{bmatrix} 0\\ 0\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0.5 \\ 2 \end{bmatrix}\end{split}\]

The current basis will remain optimal as long as (7.2)

\[\begin{split}z^*_\mathcal{N} + t \Delta z_\mathcal{N} = \begin{bmatrix} 1.2\\ 0.2\\ 0.9\\ 2.8 \end{bmatrix} + t \begin{bmatrix} 1 \\ 0 \\ 0.5 \\ 2 \end{bmatrix} \geq 0 \quad \iff \quad -1.2 \leq t.\end{split}\]

\(\Delta c = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix}^\top\)

Partitioning \(\Delta c\) according to the final optimal basis gives

\[\begin{split}\Delta c_\mathcal{B} = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \quad \text{and} \quad \Delta c_\mathcal{N} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}.\end{split}\]

Applying (7.1) yields

\[\begin{split}\Delta z_\mathcal{N} = \left( B^{-1} N \right)^\top \Delta c_\mathcal{B} - \Delta c_\mathcal{N} = \begin{bmatrix} 1 & 0.2 & 1.6\\ 0 & 0.2 & -0.4\\ 0.5 & -0.1 & -0.3\\ 2 & -0.2 & -1.6 \end{bmatrix} \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix} - \begin{bmatrix} 0\\ 0\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} 0.2 \\ 0.2 \\ -0.1 \\ -0.2 \end{bmatrix}\end{split}\]

The current basis will remain optimal as long as (7.2)

\[\begin{split}z^*_\mathcal{N} + t \Delta z_\mathcal{N} = \begin{bmatrix} 1.2\\ 0.2\\ 0.9\\ 2.8 \end{bmatrix} + t \begin{bmatrix} 0.2 \\ 0.2 \\ -0.1 \\ -0.2 \end{bmatrix} \geq 0 \quad \iff \quad -1 \leq t \leq 9.\end{split}\]

\(\Delta c = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}^\top\)

Partitioning \(\Delta c\) according to the final optimal basis gives

\[\begin{split}\Delta c_\mathcal{B} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \quad \text{and} \quad \Delta c_\mathcal{N} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}.\end{split}\]

Applying (7.1) yields

\[\begin{split}\Delta z_\mathcal{N} = \left( B^{-1} N \right)^\top \Delta c_\mathcal{B} - \Delta c_\mathcal{N} = \begin{bmatrix} 1 & 0.2 & 1.6\\ 0 & 0.2 & -0.4\\ 0.5 & -0.1 & -0.3\\ 2 & -0.2 & -1.6 \end{bmatrix} \begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix} - \begin{bmatrix} 0\\ 0\\ 0\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ 0\\ -1 \end{bmatrix}\end{split}\]

The current basis will remain optimal as long as (7.2)

\[\begin{split}z^*_\mathcal{N} + t \Delta z_\mathcal{N} = \begin{bmatrix} 1.2\\ 0.2\\ 0.9\\ 2.8 \end{bmatrix} + t \begin{bmatrix} 0\\ 0\\ 0\\ -1 \end{bmatrix} \geq 0 \quad \iff \quad t \leq 2.8.\end{split}\]

Exercise 7.3

(a)

The range of optimality is given by

\[\begin{split}\begin{aligned} -1 + 2 \mu &\geq 0, \quad & \quad 3 - \mu &\geq 0,\\ -1 + \mu &\geq 0, \quad & \quad -4 + 3 \mu &\geq 0, \end{aligned} \quad \iff \quad \frac{4}{3} \leq \mu \leq 3.\end{split}\]

(b)

The entering variable is \(x_{j = 3 \in \mathcal{N}}\) because the maximum is \(\mu^* = 3\).

Since

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

and

\[\DeclareMathOperator*{\argmax}{arg\,max} \argmax_{i \in \mathcal{B}} \frac{\Delta x_i}{x^*_i + \mu^* \bar{x}_i} = \argmax_{i \in \mathcal{B}} \left\{ \frac{1}{2}, \frac{2}{5}, \frac{-1}{2} \right\},\]

the leaving variable is \(x_4\).

Exercise 7.4

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 \(x^*_\mathcal{B}\) and \(z^*_\mathcal{N}\) have some negative components, define

\[\begin{split}\bar{x}_\mathcal{B} = \begin{bmatrix} 1\\ 1 \end{bmatrix} \quad \text{and} \quad \bar{z}_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}.\end{split}\]

Iteration 1

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-2}{1}, -\frac{6}{1}, -\frac{0}{1} \right\}, \max\left\{ -\frac{-2}{1}, -\frac{1}{1} \right\} \right\}\\ &= 2\end{split}\]

shows that one can select either \(x_1\) to be the entering variable or \(x_4\) to be the leaving variable. Applying Bland’s rule selects \(x_1\) to be the entering variable.

Step 2

The maximum is achieved by \(j = 1 \in \mathcal{N}\), so do one step of the primal simplex method.

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}\]

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{1 + \mu^*}{2} \right\}\\ &= 5.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{1}{2} = 0.5 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{1}{2} = 0.5\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{-2}{-2} = 1 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{1}{-2} = -0.5.\end{split}\]

Step 4

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} - 0.5 \begin{bmatrix} -1\\ 2 \end{bmatrix} = \begin{bmatrix} -1.5\\ 0 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 0.5\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 1 \end{bmatrix} - 0.5 \begin{bmatrix} -1\\ 2 \end{bmatrix} = \begin{bmatrix} 1.5\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = 0.5\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} &\leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} -2\\ 6\\ 0 \end{bmatrix} - (1) \begin{bmatrix} -2\\ 1\\ -1 \end{bmatrix} = \begin{bmatrix} 0\\ 5\\ 1 \end{bmatrix} \quad & \quad z^*_i &\leftarrow s = 1\\ \bar{z}_\mathcal{N} &\leftarrow \bar{z}_\mathcal{N} - \bar{s} \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} - (-0.5) \begin{bmatrix} -2\\ 1\\ -1 \end{bmatrix} = \begin{bmatrix} 0\\ 1.5\\ 0.5 \end{bmatrix} \quad & \quad \bar{z}_i &\leftarrow \bar{s} = -0.5.\end{split}\]

Step 5

The current basis is updated to

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

Iteration 2

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{5}{3 / 2}, -\frac{1}{1 / 2} \right\}, \max\left\{ -\frac{-3 / 2}{3 / 2}, -\frac{1 / 2}{1 / 2} \right\} \right\}\\ &= 1\end{split}\]

shows that \(x_4\) is the leaving variable.

Step 2

The maximum is achieved by \(i = 4 \in \mathcal{B}\), so do one step of the dual simplex method.

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top e_i = -\begin{bmatrix} 0.5 & 0.5\\ -1.5 & -0.5\\ -0.5 & 0.5 \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix} = \begin{bmatrix} -0.5\\ 1.5\\ 0.5 \end{bmatrix}.\end{split}\]

The index of the entering variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{j \in \mathcal{N}} \left\{ \frac{z^*_j + \mu^* \bar{z}_j}{\Delta z_j} \colon \Delta z_j > 0 \right\} &= \argmin_{j \in \mathcal{N}}\left\{ \frac{5 + \mu^* (1.5)}{1.5}, \frac{1 + \mu^* (0.5)}{0.5} \right\}\\ &= 3.\end{split}\]

The primal step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{-1.5}{-0.5} = 3 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{1.5}{-0.5} = -3\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{1}{0.5} = 2 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{0.5}{0.5} = 1.\end{split}\]

Step 4

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.5\\ 0.5 \end{bmatrix} - (3) \begin{bmatrix} -0.5\\ 0.5 \end{bmatrix} = \begin{bmatrix} 0\\ -1 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 3\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1.5\\ 0.5 \end{bmatrix} - (-3) \begin{bmatrix} -0.5\\ 0.5 \end{bmatrix} = \begin{bmatrix} 0\\ 2 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = -3\end{split}\]

and

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

Step 5

The current basis is updated to

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

Iteration 3

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{2}{1} \right\}, \max\left\{ -\frac{-1}{2} \right\} \right\}\\ &= 0.5\end{split}\]

shows that \(x_1\) is the leaving variable.

Step 2

The maximum is achieved by \(i = 1 \in \mathcal{B}\), so do one step of the dual simplex method.

The dual step direction is

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

The index of the entering variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{j \in \mathcal{N}} \left\{ \frac{z^*_j + \mu^* \bar{z}_j}{\Delta z_j} \colon \Delta z_j > 0 \right\} &= \argmin_{j \in \mathcal{N}}\left\{ \frac{2 + \mu^* (0)}{2} \right\}\\ &= 2.\end{split}\]

The primal step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{-1}{-2} = 0.5 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{2}{-2} = -1\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{2}{2} = 1 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{0}{2} = 0.\end{split}\]

Step 4

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} 3\\ -1 \end{bmatrix} - (0.5) \begin{bmatrix} 3\\ -2 \end{bmatrix} = \begin{bmatrix} 1.5\\ 0 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 0.5\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} -3\\ 2 \end{bmatrix} - (-1) \begin{bmatrix} 3\\ -2 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = -1\end{split}\]

and

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

Step 5

The current basis is updated to

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

Iteration 4

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{3}{1} \right\} \right\}\\ &= -3\end{split}\]

shows that the current solution is optimal. The optimal objective function value is

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

Exercise 7.5

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}\]

Since only \(x^*_\mathcal{B}\) has some negative components, the problem is dual feasible. Nevertheless, define

\[\begin{split}\bar{x}_\mathcal{B} = \begin{bmatrix} 1\\ 1 \end{bmatrix} \quad \text{and} \quad \bar{z}_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}.\end{split}\]

Iteration 1

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{1}{1}, -\frac{3}{1}, -\frac{1}{1} \right\}, \max\left\{ -\frac{-5}{1}, -\frac{4}{1} \right\} \right\}\\ &= 5\end{split}\]

shows that \(x_4\) is the leaving variable.

Step 2

The maximum is achieved by \(i = 4 \in \mathcal{B}\), so do one step of the dual simplex method.

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top 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}\]

The index of the entering variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{j \in \mathcal{N}} \left\{ \frac{z^*_j + \mu^* \bar{z}_j}{\Delta z_j} \colon \Delta z_j > 0 \right\} &= \argmin_{j \in \mathcal{N}}\left\{ \frac{3 + \mu^*}{5} \right\}\\ &= 2.\end{split}\]

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 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{-5}{-5} = 1 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{1}{-5} = -0.2\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{3}{5} = 0.6 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{1}{5} = 0.2.\end{split}\]

Step 4

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 & \quad x^*_j &\leftarrow t = 1\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 1 \end{bmatrix} - (-0.2) \begin{bmatrix} -5\\ -1 \end{bmatrix} = \begin{bmatrix} 0\\ 0.8 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = -0.2\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} &\leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 3\\ 1 \end{bmatrix} - (0.6) \begin{bmatrix} -2\\ 5\\ -1 \end{bmatrix} = \begin{bmatrix} 2.2\\ 0\\ 1.6 \end{bmatrix} \quad & \quad z^*_i &\leftarrow s = 0.6\\ \bar{z}_\mathcal{N} &\leftarrow \bar{z}_\mathcal{N} - \bar{s} \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} - (0.2) \begin{bmatrix} -2\\ 5\\ -1 \end{bmatrix} = \begin{bmatrix} 1.4\\ 0\\ 1.2 \end{bmatrix} \quad & \quad \bar{z}_i &\leftarrow \bar{s} = 0.2.\end{split}\]

Step 5

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} 2.2\\ 0.6\\ 1.6 \end{bmatrix}\\ \bar{x}_\mathcal{B} &= \begin{bmatrix} -0.2\\ 0.8 \end{bmatrix} \quad & \quad \bar{z}_\mathcal{N} &= \begin{bmatrix} 1.4\\ 0.2\\ 1.2 \end{bmatrix}.\end{split}\]

Iteration 2

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{2.2}{1.4}, -\frac{0.6}{0.2}, -\frac{1.6}{1.2} \right\}, \max\left\{ -\frac{5}{0.8} \right\}, \right\}\\ &= -1.\bar{3}\end{split}\]

shows that the current solution is optimal. The optimal objective function value is

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

Exercise 7.6

Rewriting Exercise 2.6 into matrix form yields

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

Since both \(x^*_\mathcal{B}\) and \(z^*_\mathcal{N}\) have some negative components, define

\[\begin{split}\bar{x}_\mathcal{B} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} \quad \text{and} \quad \bar{z}_\mathcal{N} = \begin{bmatrix} 1\\ 1 \end{bmatrix}.\end{split}\]

Iteration 1

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-1}{1}, -\frac{-3}{1} \right\}, \max\left\{ -\frac{-3}{1}, -\frac{-1}{1}, -\frac{2}{1} \right\} \right\}\\ &= 3\end{split}\]

shows that one can select either \(x_2\) to be the entering variable or \(x_3\) to be the leaving variable. Applying Bland’s rule selects \(x_2\) to be the entering variable.

Step 2

The maximum is achieved by \(j = 2 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{-1 + \mu^*}{1}, \frac{2 + \mu^*}{2} \right\}\\ &= 4.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{-1}{1} = -1 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{1}{1} = 1\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{-3}{-1} = 3 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{1}{-1} = -1.\end{split}\]

Step 4

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} -3\\ -1\\ 2 \end{bmatrix} - (-1) \begin{bmatrix} -1\\ 1\\ 2 \end{bmatrix} = \begin{bmatrix} -4\\ 0\\ 4 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = -1\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} - (1) \begin{bmatrix} -1\\ 1\\ 2 \end{bmatrix} = \begin{bmatrix} 2\\ 0\\ -1 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = 1\end{split}\]

and

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

Step 5

The current basis is updated to

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

Iteration 2

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-4}{2} \right\}, \max\left\{ -\frac{-4}{2}, -\frac{-1}{1} \right\}, \right\}\\ &= 2\end{split}\]

shows that one can select either \(x_1\) to be the entering variable or \(x_3\) to be the leaving variable. Applying Bland’s rule selects \(x_1\) to be the entering variable.

Step 2

The maximum is achieved by \(j = 1 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{4 + \mu^* (-1)}{3} \right\}\\ &= 5.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{4}{3} = 1.\bar{3} \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{-1}{3} = -0.\bar{3}\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{-4}{-3} = 1.\bar{3} \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{2}{-3} = -0.\bar{6}.\end{split}\]

Step 4

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} -4\\ -1\\ 4 \end{bmatrix} - (1.\bar{3}) \begin{bmatrix} -2\\ -1\\ 3 \end{bmatrix} = \begin{bmatrix} -1.\bar{3}\\ 0.\bar{3}\\ 0 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 1.\bar{3}\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 2\\ 1\\ -1 \end{bmatrix} - (-0.\bar{3}) \begin{bmatrix} -2\\ -1\\ 3 \end{bmatrix} = \begin{bmatrix} 1.\bar{3}\\ 0.\bar{6}\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = -0.\bar{3}\end{split}\]

and

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

Step 5

The current basis is updated to

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

Iteration 3

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{0.\bar{3}}{0.\bar{3}} \right\}, \max\left\{ -\frac{-1.\bar{3}}{1.\bar{3}}, -\frac{0.\bar{3}}{0.\bar{6}} \right\}, \right\}\\ &= 1\end{split}\]

shows that \(x_3\) is the leaving variable.

Step 2

The maximum is achieved by \(i = 3 \in \mathcal{B}\), so do one step of the dual simplex method.

The dual step direction is

\[\begin{split}\Delta z_\mathcal{N} = -\left( B^{-1} N \right)^\top e_i = -\begin{bmatrix} 0.\bar{6} & 0.\bar{3} & 0.\bar{3}\\ -0.\bar{3} & 0.\bar{3} & -0.\bar{6} \end{bmatrix} \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} -0.\bar{6}\\ 0.\bar{3} \end{bmatrix}.\end{split}\]

The index of the entering variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{j \in \mathcal{N}} \left\{ \frac{z^*_j + \mu^* \bar{z}_j}{\Delta z_j} \colon \Delta z_j > 0 \right\} &= \argmin_{j \in \mathcal{N}}\left\{ \frac{0.\bar{3} + \mu^* (0.\bar{3})}{0.\bar{3}}, \right\}\\ &= 4.\end{split}\]

The primal step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{-1.\bar{3}}{-0.\bar{3}} = 4 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{1.\bar{3}}{-0.\bar{3}} = -4\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{0.\bar{3}}{0.\bar{3}} = 1 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{0.\bar{3}}{0.\bar{3}} = 1.\end{split}\]

Step 4

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.\bar{3}\\ 0.\bar{3}\\ 1.\bar{3} \end{bmatrix} - (4) \begin{bmatrix} -0.\bar{3}\\ 0.\bar{3}\\ -0.\bar{6} \end{bmatrix} = \begin{bmatrix} 0\\ -1\\ 4 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 4\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1.\bar{3}\\ 0.\bar{6}\\ -0.\bar{3} \end{bmatrix} - (-4) \begin{bmatrix} -0.\bar{3}\\ 0.\bar{3}\\ -0.\bar{6} \end{bmatrix} = \begin{bmatrix} 0\\ 2\\ -3 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = -4\end{split}\]

and

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

Step 5

The current basis is updated to

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

Iteration 4

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{1}{1} \right\}, \max\left\{ -\frac{-1}{2} \right\}, \right\}\\ &= 0.5\end{split}\]

shows that \(x_2\) is the leaving variable.

Step 2

The maximum is achieved by \(i = 2 \in \mathcal{B}\), so do one step of the dual simplex method.

The dual step direction is

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

The index of the entering variable is

\[\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{j \in \mathcal{N}} \left\{ \frac{z^*_j + \mu^* \bar{z}_j}{\Delta z_j} \colon \Delta z_j > 0 \right\} = \emptyset.\]

Therefore, the dual is unbounded i.e. the primal is infeasible.

Exercise 7.7

The previous exercises were solved using the proposed tool.

Exercise 7.8

Rewriting the standard form LP into matrix form yields

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

Since both \(x^*_\mathcal{B}\) and \(z^*_\mathcal{N}\) have some negative components, define

\[\begin{split}\bar{x}_\mathcal{B} = \begin{bmatrix} 1\\ 1 \end{bmatrix} \quad \text{and} \quad \bar{z}_\mathcal{N} = \begin{bmatrix} 1\\ 1 \end{bmatrix}.\end{split}\]

Iteration 1

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-3}{1}, -\frac{1}{1} \right\}, \max\left\{ -\frac{1}{1}, -\frac{-4}{1} \right\} \right\}\\ &= 3\end{split}\]

shows that \(x_4\) is the leaving variable.

Step 2

The maximum is achieved by \(i = 4 \in \mathcal{B}\), so do one step of the dual simplex method.

The dual step direction is

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

The index of the entering variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{j \in \mathcal{N}} \left\{ \frac{z^*_j + \mu^* \bar{z}_j}{\Delta z_j} \colon \Delta z_j > 0 \right\} &= \argmin_{j \in \mathcal{N}}\left\{ \frac{-3 + \mu^*}{1} \right\}\\ &= 1.\end{split}\]

The primal step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{-4}{-1} = 4 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{1}{-1} = -1\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{-3}{1} = -3 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{1}{1} = 1.\end{split}\]

Step 4

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\\ -4 \end{bmatrix} - (4) \begin{bmatrix} 1\\ -1 \end{bmatrix} = \begin{bmatrix} -3\\ 0 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 4\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 1 \end{bmatrix} - (-1) \begin{bmatrix} 1\\ -1 \end{bmatrix} = \begin{bmatrix} 2\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = -1\end{split}\]

and

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

Step 5

The current basis is updated to

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

Iteration 2

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-3}{1}, -\frac{-2}{2} \right\}, \max\left\{ -\frac{-3}{2} \right\} \right\}\\ &= 3\end{split}\]

shows that \(x_4\) is the entering variable.

Step 2

The maximum is achieved by \(j = 4 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{-3 + \mu^* (2)}{1} \right\}\\ &= 3.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{-3}{1} = -3 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{2}{1} = 2\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{-3}{-1} = 3 \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{1}{-1} = -1.\end{split}\]

Step 4

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} -3\\ 4 \end{bmatrix} - (-3) \begin{bmatrix} 1\\ -1 \end{bmatrix} = \begin{bmatrix} 0\\ 1 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = -3\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 2\\ -1 \end{bmatrix} - (2) \begin{bmatrix} 1\\ -1 \end{bmatrix} = \begin{bmatrix} 0\\ 1 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = 2\end{split}\]

and

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

Step 5

The current basis is updated to

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

Iteration 3

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-2}{2} \right\}, \max\left\{ -\frac{-3}{2}, -\frac{1}{1} \right\} \right\}\\ &= 1.5\end{split}\]

shows that \(x_4\) is the leaving variable.

Step 2

The maximum is achieved by \(i = 4 \in \mathcal{B}\), so do one step of the dual simplex method.

The dual step direction is

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

The index of the entering variable is

\[\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{j \in \mathcal{N}} \left\{ \frac{z^*_j + \mu^* \bar{z}_j}{\Delta z_j} \colon \Delta z_j > 0 \right\} = \emptyset.\]

Therefore, the dual is unbounded i.e. the primal is infeasible.

Exercise 7.9

Notice that parametric self-dual simplex method assumes perturbations are all strictly positive i.e. \(\bar{x}_\mathcal{B} > 0\) and \(\bar{z}_\mathcal{N} > 0\).

The following is a proof by contradiction. Suppose \(P_\mu\) is infeasible and \(\exists \mu' \leq \mu\) such that \(P_{\mu'}\) is infeasible. These statements translate to

\[x^*_i + \mu \bar{x}_i < 0 \quad \land \quad x^*_i + \mu' \bar{x}_i \geq 0\]

where \(i \in \mathcal{B}\). By inspection,

\[\begin{split}x^*_i + \mu' \bar{x}_i &> x^*_i + \mu \bar{x}_i\\ \mu' \bar{x}_i &> \mu \bar{x}_i\\ 0 &> (\mu - \mu') \bar{x}_i,\end{split}\]

which is a contradiction because neither factors are negative. The analogous proof for the perturbed dual problem can be realized by replacing \(x^*_i\) with \(z^*_j\) and \(\bar{x}_i\) with \(\bar{z}_j\) where \(j \in \mathcal{N}\).

Exercise 7.10

Failing to proceed during the primal simplex step implies that the primal is unbounded and the dual problem is infeasible (i.e. \(z^*_\mathcal{N}\) has some negative components). Likewise, failing to proceed during the dual simplex step implies that the dual is unbounded and the original problem is infeasible i.e. (i.e. \(x^*_\mathcal{B}\) has some negative components). These conditions can be detected when taking the \(\argmin\) gives the \(\emptyset\).

Exercise 7.11

Rewriting the standard form LP into matrix form yields

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

To analyze the one parameter family of LPs, define

\[\begin{split}\bar{x}_\mathcal{B} = \begin{bmatrix} 1\\ 1\\ 1\\ 1 \end{bmatrix} \quad \text{and} \quad \bar{z}_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}.\end{split}\]

Evaluating \(x^*_\mathcal{B} + \bar{x}_\mathcal{B} \mu \geq \boldsymbol{0}\) and \(z^*_\mathcal{N} + \bar{z}_\mathcal{N} \mu \geq \boldsymbol{0}\) reveals the current range for \(\mu\) is

\[4 - 4 \mu' \leq \mu \leq \infty.\]

By inspection, the initial dictionary is optimal as long as \(\mu' \geq 1\).

Iteration 1

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-4 + 4 \mu'}{1}, -\frac{2}{1}, -\frac{2}{1}, -\frac{2}{1}, -\frac{2}{1} \right\} \right\}\\ &= 4 - 4 \mu'\end{split}\]

shows that \(x_0\) is the entering variable for \(\mu' < 1\).

Step 2

The maximum is achieved by \(j = 0 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{1 + \mu^* (1)}{1}, \frac{2 + \mu^* (1)}{1}, \frac{4 + \mu^* (1)}{1}, \frac{8 + \mu^* (1)}{1} \right\}\\ &= 5.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{1}{1} = 1 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{1}{1} = 1\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{-4 + 4 \mu'}{-1} = 4 - 4 \mu' \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{1}{-1} = -1.\end{split}\]

Step 4

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\\ 2\\ 4\\ 8 \end{bmatrix} - (1) \begin{bmatrix} 1\\ 1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 1\\ 3\\ 7 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 1\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 1\\ 1\\ 1 \end{bmatrix} - (1) \begin{bmatrix} 1\\ 1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ 0\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = 1\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} &\leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} -4 + 4 \mu' \\ 2\\ 2\\ 2\\ 2 \end{bmatrix} - (4 - 4 \mu') \begin{bmatrix} -1\\ 1\\ 0\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} 0\\ -2 + 4 \mu'\\ 2\\ 2\\ 2 \end{bmatrix} \quad & \quad z^*_i &\leftarrow s = 4 - 4 \mu'\\ \bar{z}_\mathcal{N} &\leftarrow \bar{z}_\mathcal{N} - \bar{s} \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1 \end{bmatrix} - (-1) \begin{bmatrix} -1\\ 1\\ 0\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} 0\\ 2\\ 1\\ 1\\ 1 \end{bmatrix} \quad & \quad \bar{z}_i &\leftarrow \bar{s} = -1.\end{split}\]

Step 5

The current basis is updated to

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

The current range for \(\mu\) is

\[\frac{2 - 4 \mu'}{2} \leq \mu \leq 4 - 4 \mu'.\]

By inspection, the dictionary is optimal as long as \(0.5 \leq \mu' \leq 1\).

Iteration 2

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{-2 + 4 \mu'}{2}, -\frac{2}{1}, -\frac{2}{1}, -\frac{2}{1} \right\}, \max\left\{ -\frac{1}{1} \right\} \right\}\\ &= 1 - 2 \mu'\end{split}\]

shows that \(x_1\) is the entering variable for \(\mu' < 0.5\).

Step 2

The maximum is achieved by \(j = 1 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{1 + \mu^* (0)}{1}, \frac{3 + \mu^* (0)}{1}, \frac{7 + \mu^* (0)}{1} \right\}\\ &= 6.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{1}{1} = 1 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{0}{1} = 0\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{-2 + 4 \mu'}{-1} = 2 - 4 \mu' \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{2}{-1} = -2.\end{split}\]

Step 4

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\\ 3\\ 7 \end{bmatrix} - (1) \begin{bmatrix} -1\\ 1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 2\\ 0\\ 2\\ 6 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 1\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} - (0) \begin{bmatrix} -1\\ 1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = 0\end{split}\]

and

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

Step 5

The current basis is updated to

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

The current range for \(\mu\) is

\[\frac{-4 \mu'}{3} \leq \mu \leq \frac{2 - 4 \mu'}{2}.\]

By inspection, the dictionary is optimal as long as \(0 \leq \mu' \leq 0.5\).

Iteration 3

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{2}{1}, -\frac{4 \mu'}{3}, -\frac{2}{1}, -\frac{2}{1} \right\}, \max\left\{ -\frac{2}{1} \right\} \right\}\\ &= -\frac{4}{3} \mu'\end{split}\]

shows that \(x_2\) is the entering variable for \(\mu' < 0\).

Step 2

The maximum is achieved by \(j = 2 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{2 + \mu^* (0)}{1}, \frac{6 + \mu^* (0)}{1} \right\}\\ &= 7.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{2}{1} = 2 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{0}{1} = 0\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{4 \mu'}{-1} = -4 \mu' \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{3}{-1} = -3.\end{split}\]

Step 4

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\\ 2\\ 6 \end{bmatrix} - (2) \begin{bmatrix} -1\\ -1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 4\\ 3\\ 0\\ 4 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 2\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} - (0) \begin{bmatrix} -1\\ -1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = 0\end{split}\]

and

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

Step 5

The current basis is updated to

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

The current range for \(\mu\) is

\[\frac{-2 - 4 \mu'}{4} \leq \mu \leq \frac{-4 \mu'}{3}.\]

By inspection, the dictionary is optimal as long as \(-0.5 \leq \mu' \leq 0\).

Iteration 4

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{2}{1}, -\frac{2}{1}, -\frac{-4 \mu'}{4}, -\frac{2 + 4 \mu'}{1} \right\}, \max\left\{ -\frac{4}{1} \right\} \right\}\\ &= -2 - 4 \mu'\end{split}\]

shows that \(x_3\) is the entering variable for \(\mu' < -0.5\).

Step 2

The maximum is achieved by \(j = 3 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} &= \argmin_{i \in \mathcal{B}}\left\{ \frac{4 + \mu^* (0)}{1} \right\}\\ &= 8.\end{split}\]

The dual step direction is

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

Step 3

The step length adjustments are given by

\[\begin{split}t &= \frac{x^*_i}{\Delta x_i} = \frac{4}{1} = 4 \quad & \quad \bar{t} = \frac{\bar{x}_i}{\Delta x_i} = \frac{0}{1} = 0\\ s &= \frac{z^*_j}{\Delta z_j} = \frac{2 + 4 \mu'}{-1} = -2 - 4 \mu' \quad & \quad \bar{s} = \frac{\bar{z}_j}{\Delta z_j} = \frac{4}{-1} = -4.\end{split}\]

Step 4

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} 4\\ 3\\ 2\\ 4 \end{bmatrix} - (4) \begin{bmatrix} -1\\ -1\\ -1\\ 1 \end{bmatrix} = \begin{bmatrix} 8\\ 7\\ 6\\ 0 \end{bmatrix} \quad & \quad x^*_j &\leftarrow t = 4\\ \bar{x}_\mathcal{B} &\leftarrow \bar{x}_\mathcal{B} - \bar{t} \Delta x_\mathcal{B} = \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} - (0) \begin{bmatrix} -1\\ -1\\ -1\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} \quad & \quad \bar{x}_j &\leftarrow \bar{t} = 0\end{split}\]

and

\[\begin{split}z^*_\mathcal{N} &\leftarrow z^*_\mathcal{N} - s \Delta z_\mathcal{N} = \begin{bmatrix} 2 \\ 2\\ -4 \mu'\\ 2 + 4 \mu'\\ 2 \end{bmatrix} - (-2 - 4 \mu') \begin{bmatrix} 0\\ 0\\ 1\\ -1\\ 1 \end{bmatrix} = \begin{bmatrix} 2\\ 2\\ 2\\ 0\\ 4 + 4 \mu' \end{bmatrix} \quad & \quad z^*_i &\leftarrow s = -2 - 4 \mu'\\ \bar{z}_\mathcal{N} &\leftarrow \bar{z}_\mathcal{N} - \bar{s} \Delta z_\mathcal{N} = \begin{bmatrix} 1\\ 1\\ -3\\ 4\\ 1 \end{bmatrix} - (-4) \begin{bmatrix} 0\\ 0\\ 1\\ -1\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ 1\\ 0\\ 5 \end{bmatrix} \quad & \quad \bar{z}_i &\leftarrow \bar{s} = -4.\end{split}\]

Step 5

The current basis is updated to

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

The current range for \(\mu\) is

\[\frac{-4 - 4 \mu'}{5} \leq \mu \leq \frac{-2 - 4 \mu'}{4}.\]

By inspection, the dictionary is optimal as long as \(-1 \leq \mu' \leq -0.5\).

Iteration 5

Step 1

Computing

\[\begin{split}\mu^* &= \max\left\{ \max_{j \in \mathcal{N}, \bar{z}_j > 0} -\frac{z^*_j}{\bar{z}_j}, \max_{i \in \mathcal{B}, \bar{x}_i > 0} -\frac{x^*_i}{\bar{x}_i}, \right\}\\ &= \max\left\{ \max\left\{ -\frac{2}{1}, -\frac{2}{1}, -\frac{2}{1}, -\frac{4 + 4 \mu'}{5} \right\}, \max\left\{ -\frac{4}{1} \right\} \right\}\\ &= -\frac{4 + 4 \mu'}{5}\end{split}\]

shows that \(x_4\) is the entering variable for \(\mu' < -1\).

Step 2

The maximum is achieved by \(j = 4 \in \mathcal{N}\), so do one step of the primal simplex method.

The primal step direction is

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

The index of the leaving variable is

\[\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{i \in \mathcal{B}} \left\{ \frac{x^*_i + \mu^* \bar{x}_i}{\Delta x_i} \colon \Delta x_i > 0 \right\} = \emptyset.\]

Therefore, the primal is unbounded (i.e. the dual is infeasible) when \(\mu' < -1\).

References

Eng

Alexander Engau. Math 5593 linear programming lecture notes. http://www.math.ucdenver.edu/ aengau/math5593/LectureNotes.pdf. Accessed on 2017-02-08.