The Simplex Method

The Simplex Method Tool and the Simplex Pivot Tool were useful in the exercises.

Transformation to Standard Form

[Bur] provides a step-by-step procedure for transforming any LP to one in standard form.

Exercise 2.1

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 6 x_1 + 8 x_2 + 5 x_3 + 9 x_4\\ \text{subject to} \quad w_1 &= 5 - 2 x_1 - x_2 - x_3 - 3 x_4\\ w_2 &= 3 - x_1 - 3 x_2 - x_3 - 2 x_4\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 4\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 0, \quad w_1 = 5, \quad w_2 = 3.\]

Choose \(x_4\) as the entering variable and \(w_2\) as the leaving variable, based on the pivot rules in the section after (2.6) and (2.7), where

\[x_4 = \min\left\{ w_1, w_2 \right\}_{\geq 0} = \min\left\{ \frac{5}{3}, \frac{3}{2} \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = \frac{3}{2}, \quad w_1 = \frac{1}{2}, \quad w_2 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 0.5 \left( 27 + 3 x_1 - 11 x_2 + x_3 - 9 w_2 \right)\\ \text{subject to} \quad w_1 &= 0.5 \left( 1 - x_1 + 7 x_2 + x_3 + 3 w_2 \right)\\ x_4 &= 0.5 \left( 3 - x_1 - 3 x_2 - x_3 - w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 4\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Choose \(x_1\) and \(w_1\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ w_1, x_4 \right\}_{\geq 0} = \min\left\{ 1, 3 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 1, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 1, \quad w_1 = 0, \quad w_2 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 15 - 3 w_1 + 5 x_2 + 2 x_3\\ \text{subject to} \quad x_1 &= 1 + 7 x_2 + x_3 - 2 w_1 + 3 w_2\\ x_4 &= 1 - 5 x_2 - x_3 + w_1 - 2 w_2\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 4\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Choose \(x_2\) and \(x_4\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_4 \right\}_{\geq 0} = \frac{1}{5}.\]

Update the current dictionary’s feasible solution to

\[x_1 = \frac{12}{5}, \quad x_2 = \frac{1}{5}, \quad x_3 = 0, \quad x_4 = 0, \quad w_1 = 0, \quad w_2 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 16 + x_3 - x_4 - 2 w_1 - 2 w_2\\ \text{subject to} \quad x_1 &= 0.2 \left( 12 - 2 x_3 - 7 x_4 - 3 w_1 + w_2 \right)\\ x_2 &= 0.2 \left( 1 - x_3 - x_4 + w_1 - 2 w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 4\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Choose \(x_3\) and \(x_2\) as the entering and leaving variable respectively where

\[x_3 = \min\left\{ x_1, x_2 \right\}_{\geq 0} = \min\left\{ 6, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 2, \quad x_2 = 0, \quad x_3 = 1, \quad x_4 = 0, \quad w_1 = 0, \quad w_2 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 17 - 5 x_2 - 2 x_4 - w_1 - 4 w_2\\ \text{subject to} \quad x_1 &= 2 + 2 x_2 - x_4 - w_1 + w_2\\ x_3 &= 1 - 5 x_2 - x_4 + w_1 - 2 w_2\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 4\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Exercise 2.2

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 2 x_1 + x_2\\ \text{subject to} \quad w_1 &= 4 - 2 x_1 - x_2\\ w_2 &= 3 - 2 x_1 - 3 x_2\\ w_3 &= 5 - 4 x_1 - x_2\\ w_4 &= 1 - x_1 - 5 x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 4 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad w_1 = 4, \quad w_2 = 3, \quad w_3 = 5, \quad w_4 = 1.\]

Choose \(x_1\) and \(w_4\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ w_1, w_2, w_3, w_4 \right\}_{\geq 0} = \min\left\{ 2, \frac{3}{2}, \frac{5}{4}, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 1, \quad x_2 = 0, \quad w_1 = 2, \quad w_2 = 1, \quad w_3 = 1, \quad w_4 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 2 - 9 x_2 - 2 w_4\\ \text{subject to} \quad x_1 &= 1 - 5 x_2 - w_4\\ w_1 &= 2 + 9 x_2 + 2 w_4\\ w_2 &= 1 + 7 x_2 + 2 w_4\\ w_3 &= 1 + 19 x_2 + 4 w_4\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 4 \end{aligned}\end{split}\]

Exercise 2.3

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 2 x_1 - 6 x_2\\ \text{subject to} \quad w_1 &= -2 + x_1 + x_2 + x_3\\ w_2 &= 1 - 2 x_1 + x_2 - x_3\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial infeasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = -2, \quad w_2 = 1.\]

The auxiliary problem is

\[\begin{split}\begin{aligned} \text{maximize} \quad -x_0 &\\ \text{subject to} \quad -x_1 - x_2 - x_3 - x_0 &\leq -2\\ 2 x_1 - x_2 + x_3 - x_0 &\leq 1\\ x_i &\geq 0 \quad i = 0, 1, 2, 3 \end{aligned}\end{split}\]

and its initial infeasible dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad w_1 &= -2 + x_1 + x_2 + x_3 + x_0\\ w_2 &= 1 - 2 x_1 + x_2 - x_3 + x_0\\ x_i &\geq 0 \quad i = 0, 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial infeasible solution for auxiliary problem:

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = -2, \quad w_2 = 1.\]

Pivot the infeasible dictionary with \(x_0\) as the entering variable and \(w_1\), the most infeasible variable, as the leaving variable. The resulting dictionary is then

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -2 + x_1 + x_2 + x_3 - w_1\\ \text{subject to} \quad x_0 &= 2 - x_1 - x_2 - x_3 + w_1\\ w_2 &= 3 - 3 x_1 - 2 x_3 + w_1\\ x_i &\geq 0 \quad i = 0, 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

and its feasible solution is updated to

\[x_0 = 2, \quad x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 3.\]

Choose \(x_1\) and \(w_2\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ x_0, w_2 \right\}_{\geq 0} = \min\left\{ 2, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = 1, \quad x_1 = 1, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 0.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{3} \left( -3 + 3 x_2 + x_3 - 2 w_1 - w_2 \right)\\ \text{subject to} \quad x_0 &= \frac{1}{3} \left( 3 - 3 x_2 - x_3 + 2 w_1 + w_2 \right)\\ x_1 &= \frac{1}{3} \left( 3 - 2 x_3 + w_1 + w_2 \right)\\ x_i &\geq 0 \quad i = 0, 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Choose \(x_2\) and \(x_0\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_0 \right\}_{\geq 0} = \min\left\{ 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = 0, \quad x_1 = 1, \quad x_2 = 1, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 0.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad x_1 &= \frac{1}{3} \left( 3 - 2 x_3 + w_1 - w_2 \right)\\ x_2 &= \frac{1}{3} \left( 3 - 3 x_0 - x_3 + 2 w_1 + w_2 \right)\\ x_i &\geq 0 \quad i = 0, 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

The dictionary is optimal for the auxiliary problem, so \(x_0\) can be dropped and the original objective function can be reintroduced with the basic variables substituted appropriately:

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -4 + \frac{2}{3} x_3 - \frac{10}{3} w_1 - \frac{8}{3} w_2\\ \text{subject to} \quad x_1 &= \frac{1}{3} \left( 3 - 2 x_3 + w_1 - w_2 \right)\\ x_2 &= \frac{1}{3} \left( 3 - x_3 + 2 w_1 + w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 1, \quad x_2 = 1, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 0.\]

Choose \(x_3\) and \(x_1\) as the entering and leaving variable respectively where

\[x_3 = \min\left\{ x_1, x_2 \geq 0 \right\}_{\geq 0} = \min\left\{ \frac{3}{2}, 3 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 0, \quad x_2 = \frac{1}{2}, \quad x_3 = \frac{3}{2}, \quad w_1 = 0, \quad w_2 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -3 - x_1 - 3 w_1 - 3 w_2\\ \text{subject to} \quad x_2 &= \frac{1}{2} \left( 1 + x_1 + w_1 + w_2 \right)\\ x_3 &= \frac{1}{2} \left( 3 - 3 x_1 + w_1 - w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Exercise 2.4

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_1 - 3 x_2 - x_3\\ \text{subject to} \quad w_1 &= -5 - 2 x_1 + 5 x_2 - x_3\\ w_2 &= 4 - 2 x_1 + x_2 - 2 x_3\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial infeasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = -5, \quad w_2 = 4.\]

The auxiliary problem is

\[\begin{split}\begin{aligned} \text{maximize} \quad -x_0 &\\ \text{subject to} \quad 2 x_1 - 5 x_2 + x_3 - x_0 &\leq -5\\ 2 x_1 - x_2 + 2 x_3 - x_0 &\leq 4\\ x_i &\geq 0 \quad i = 0, 1, 2, 3 \end{aligned}\end{split}\]

and its initial infeasible dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad w_1 &= -5 - 2 x_1 + 5 x_2 + x_3 + x_0\\ w_2 &= 4 - 2 x_1 + x_2 + 2 x_3 + x_0\\ x_i &\geq 0 \quad i = 0, 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial infeasible solution for auxiliary problem:

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = -5, \quad w_2 = 4.\]

Pivot the infeasible dictionary with \(x_0\) as the entering variable and \(w_1\), the most infeasible variable, as the leaving variable. The resulting dictionary is then

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -5 - 2 x_1 + 5 x_2 + x_3 - w_1\\ \text{subject to} \quad x_0 &= 5 + 2 x_1 - 5 x_2 - x_3 + w_1\\ w_2 &= 9 - 4 x_2 + x_3 + w_1\\ x_i &\geq 0 \quad i = 0, 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

and its feasible solution is updated to

\[x_0 = 5, \quad x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 9.\]

Choose \(x_2\) and \(x_0\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_0, w_2 \right\}_{\geq 0} = \min\left\{ 1, \frac{9}{4} \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 1, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 5.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad x_2 &= \frac{1}{5} \left( 5 + 2 x_1 - x_0 - x_3 + w_1 \right)\\ w_2 &= \frac{1}{5} \left( 25 - 8 x_1 + 4 x_0 + 9 x_3 + w_1 \right)\\ x_i &\geq 0 \quad i = 0, 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

The dictionary is optimal for the auxiliary problem, so \(x_0\) can be dropped and the original objective function can be reintroduced with the basic variables substituted appropriately:

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{5} \left( -15 - 8 x_1 - 2 x_3 - 3 w_1 \right)\\ \text{subject to} \quad x_2 &= \frac{1}{5} \left( 5 + 2 x_1 - x_3 + w_1 \right)\\ w_2 &= \frac{1}{5} \left( 25 - 8 x_1 + 9 x_3 + w_1 \right)\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 0, \quad x_2 = 1, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 5,\]

which happens to be the optimal solution since all the coefficients in \(\zeta\) are negative.

Exercise 2.5

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= x_1 + 3 x_2\\ \text{subject to} \quad w_1 &= -3 + x_1 + x_2\\ w_2 &= -1 + x_1 - x_2\\ w_3 &= 4 - x_1 - 2 x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial infeasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad w_1 = -3, \quad w_2 = -1, \quad w_3 = 4.\]

The auxiliary problem is

\[\begin{split}\begin{aligned} \text{maximize} \quad -x_0 &\\ \text{subject to} \quad -x_1 - x_2 - x_0 &\leq -3\\ -x_1 + x_2 - x_0 &\leq -1\\ x_1 + 2 x_2 - x_0 &\leq 4\\ x_i &\geq 0 \quad i = 0, 1, 2 \end{aligned}\end{split}\]

and its initial infeasible dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad w_1 &= -3 + x_0 + x_1 + x_2\\ w_2 &= -1 + x_0 + x_1 - x_2\\ w_3 &= 4 + x_0 - x_1 - 2 x_2\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial infeasible solution for auxiliary problem:

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 0, \quad w_1 = -3, \quad w_2 = -1, \quad w_3 = 4.\]

Pivot the infeasible dictionary with \(x_0\) as the entering variable and \(w_1\), the most infeasible variable, as the leaving variable. The resulting dictionary is then

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -3 + x_1 + x_2 - w_1\\ \text{subject to} \quad x_0 &= 3 - x_1 - x_2 + w_1\\ w_2 &= 2 - 2 x_2 + w_1\\ w_3 &= 7 - 2 x_1 - 3 x_2 + w_1\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

and its feasible solution is updated to

\[x_0 = 3, \quad x_1 = 0, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 7.\]

Choose \(x_1\) and \(x_0\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ x_0, w_3 \right\}_{\geq 0} = \min\left\{ 3, \frac{7}{2} \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = 0, \quad x_1 = 3, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 1.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad x_1 &= 3 - x_0 - x_2 + w_1\\ w_2 &= 2 - 2 x_2 + w_1\\ w_3 &= 1 + 2 x_0 - x_2 - w_1\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

The dictionary is optimal for the auxiliary problem, so \(x_0\) can be dropped and the original objective function can be reintroduced with the basic variables substituted appropriately:

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 3 + 2 x_2 + w_1\\ \text{subject to} \quad x_1 &= 3 - x_2 + w_1\\ w_2 &= 2 - 2 x_2 + w_1\\ w_3 &= 1 - x_2 - w_1\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 3, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 1.\]

Unbounded Solution

Choose \(x_2\) and \(w_2\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_1, w_2, w_3 \right\}_{\geq 0} = \min\left\{ 3, 1, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 2, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 5 + 2 w_1 - w_2\\ \text{subject to} \quad x_1 &= \frac{1}{2} \left( 4 + w_1 + w_2 \right)\\ x_2 &= \frac{1}{2} \left( 2 + w_1 - w_2 \right)\\ w_3 &= \frac{1}{2} \left( -3 w_1 + w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Since the entering variable

\[w_1 = \min\left\{ x_1, x_2, w_3 \right\}_{\geq 0} = \min\left\{ -4, -2, 0 \right\},\]

the problem is unbounded.

Bounded Solution

Choose \(x_2\) and \(w_3\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_1, w_2, w_3 \right\}_{\geq 0} = \min\left\{ 3, 1, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 2, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 5 - w_1 - 2 w_3\\ \text{subject to} \quad x_1 &= 2 + 2 w_1 + w_3\\ x_2 &= 1 - w_1 - w_3\\ w_2 &= 3 w_1 + 2 w_3\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Exercise 2.6

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= x_1 + 3 x_2\\ \text{subject to} \quad w_1 &= -3 + x_1 + x_2\\ w_2 &= -1 + x_1 - x_2\\ w_3 &= 2 - x_1 - 2 x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial infeasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad w_1 = -3, \quad w_2 = -1, \quad w_3 = 2.\]

The auxiliary problem is

\[\begin{split}\begin{aligned} \text{maximize} \quad -x_0 &\\ \text{subject to} \quad -x_1 - x_2 - x_0 &\leq -3\\ -x_1 + x_2 - x_0 &\leq -1\\ x_1 + 2 x_2 - x_0 &\leq 2\\ x_i &\geq 0 \quad i = 0, 1, 2 \end{aligned}\end{split}\]

and its initial infeasible dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad w_1 &= -3 + x_0 + x_1 + x_2\\ w_2 &= -1 + x_0 + x_1 - x_2\\ w_3 &= 2 + x_0 - x_1 - 2 x_2\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial infeasible solution for auxiliary problem:

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 0, \quad w_1 = -3, \quad w_2 = -1, \quad w_3 = 2.\]

Pivot the infeasible dictionary with \(x_0\) as the entering variable and \(w_1\), the most infeasible variable, as the leaving variable. The resulting dictionary is then

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -3 + x_1 + x_2 - w_1\\ \text{subject to} \quad x_0 &= 3 - x_1 - x_2 + w_1\\ w_2 &= 2 - 2 x_2 + w_1\\ w_3 &= 5 - 2 x_1 - 3 x_2 + w_1\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

and its feasible solution is updated to

\[x_0 = 3, \quad x_1 = 0, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 5.\]

Notice that either \(x_1\) or \(x_2\) can be selected. As shown below, both routes will lead to a negative optimal solution. Thus, the original problem is infeasible.

Route 1

Choose \(x_2\) and \(w_2\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ x_0, w_2, w_3 \right\}_{\geq 0} = \min\left\{ 3, 1, \frac{5}{3} \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = 2, \quad x_1 = 0, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 2.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{2} \left( -4 + 2 x_1 - w_1 - w_2 \right)\\ \text{subject to} \quad x_0 &= \frac{1}{2} \left( 4 - 2 x_1 + w_1 + w_2 \right)\\ x_2 &= \frac{1}{2} \left( 2 + w_1 + w_2 \right)\\ w_3 &= \frac{1}{2} \left( 6 - 4 x_1 + 2 w_2 \right)\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Choose \(x_1\) and \(w_3\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ x_0, w_3 \right\}_{\geq 0} = \min\left\{ 2, \frac{3}{2} \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = \frac{1}{2}, \quad x_1 = \frac{3}{2}, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{2} \left( -1 - w_1 - w_3 \right)\\ \text{subject to} \quad x_0 &= \frac{1}{2} \left( 1 + w_1 + w_3 \right)\\ x_1 &= \frac{1}{2} \left( 3 + w_2 - w_3 \right)\\ x_2 &= \frac{1}{2} \left( 2 + w_1 - w_2 \right)\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Route 2

Choose \(x_1\) and \(w_3\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ x_0, w_3 \right\}_{\geq 0} = \min\left\{ 3, \frac{5}{2} \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = \frac{1}{2}, \quad x_1 = \frac{5}{2}, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 0.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{2} \left( -1 - w_1 - w_3 \right)\\ \text{subject to} \quad x_0 &= \frac{1}{2} \left( 1 + w_1 + w_3 \right)\\ x_1 &= \frac{1}{2} \left( 5 - 2 x_2 + w_1 - w_3 \right)\\ w_2 &= \frac{1}{2} \left( 4 - 4 x_2 + 2 w_1 \right)\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Exercise 2.7

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= x_1 + 3 x_2\\ \text{subject to} \quad w_1 &= -3 + x_1 + x_2\\ w_2 &= -1 + x_1 - x_2\\ w_3 &= 2 + x_1 - 2 x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial infeasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad w_1 = -3, \quad w_2 = -1, \quad w_3 = 2.\]

The auxiliary problem is

\[\begin{split}\begin{aligned} \text{maximize} \quad -x_0 &\\ \text{subject to} \quad -x_1 - x_2 - x_0 &\leq -3\\ -x_1 + x_2 - x_0 &\leq -1\\ -x_1 + 2 x_2 - x_0 &\leq 2\\ x_i &\geq 0 \quad i = 0, 1, 2 \end{aligned}\end{split}\]

and its initial infeasible dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad w_1 &= -3 + x_0 + x_1 + x_2\\ w_2 &= -1 + x_0 + x_1 - x_2\\ w_3 &= 2 + x_0 + x_1 - 2 x_2\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial infeasible solution for auxiliary problem:

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 0, \quad w_1 = -3, \quad w_2 = -1, \quad w_3 = 2.\]

Pivot the infeasible dictionary with \(x_0\) as the entering variable and \(w_1\), the most infeasible variable, as the leaving variable. The resulting dictionary is then

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -3 + x_1 + x_2 - w_1\\ \text{subject to} \quad x_0 &= 3 - x_1 - x_2 + w_1\\ w_2 &= 2 - 2 x_2 + w_1\\ w_3 &= 5 - x_2 + w_1\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

and its feasible solution is updated to

\[x_0 = 3, \quad x_1 = 0, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 5.\]

Choose \(x_1\) and \(x_0\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ x_0 \right\}_{\geq 0} = \min\left\{ 3 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = 0, \quad x_1 = 3, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 5.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad x_1 &= 3 - x_0 - x_2 + w_1\\ w_2 &= 2 - 2 x_2 + w_1\\ w_3 &= 5 - x_2 + w_1\\ x_i &\geq 0 \quad i = 0, 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

The dictionary is optimal for the auxiliary problem, so \(x_0\) can be dropped and the original objective function can be reintroduced with the basic variables substituted appropriately:

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 3 + 2 x_2 + w_1\\ \text{subject to} \quad x_1 &= 3 - x_2 + w_1\\ w_2 &= 2 - 2 x_2 + w_1\\ w_3 &= 1 - x_2 + w_1\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 3, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 2, \quad w_3 = 1.\]

Notice that as long as \(w_1 \geq 2 x_2\), the constraints are satisfied. As shown below, the original problem is feasible but has an unbounded objective.

Route 1

Choose \(x_2\) and \(w_2\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_1, w_2, w_3 \right\}_{\geq 0} = \min\left\{ 3, 1, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 2, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 5 + 2 w_1 - w_2\\ \text{subject to} \quad x_1 &= \frac{1}{2} \left( 4 + w_1 + w_2 \right)\\ x_2 &= \frac{1}{2} \left( 2 + w_1 - w_2 \right)\\ w_3 &= \frac{1}{2} \left( w_1 + w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Since the entering variable

\[w_1 = \min\left\{ x_1, x_2, w_3 \right\}_{\geq 0} = \min\left\{ -4, -2, 0 \right\},\]

the problem is unbounded.

Route 2

Choose \(x_2\) and \(w_3\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_1, w_2, w_3 \right\}_{\geq 0} = \min\left\{ 3, 1, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 2, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 5 + 3 w_1 - 2 w_3\\ \text{subject to} \quad x_1 &= 2 + w_3\\ x_2 &= 1 + w_1 - w_3\\ w_2 &= -w_1 + 2 w_3\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Since the entering variable

\[w_1 = \min\left\{ x_2, w_2 \right\}_{\geq 0} = \min\left\{ -1, 0 \right\}_{\geq 0},\]

the problem is unbounded.

Exercise 2.8

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 3 x_1 + 2 x_2\\ \text{subject to} \quad w_1 &= 1 - x_1 + 2 x_2\\ w_2 &= 2 - x_1 + x_2\\ w_3 &= 6 - 2 x_1 + x_2\\ w_4 &= 5 - x_1\\ w_5 &= 16 - 2 x_1 - x_2\\ w_6 &= 12 - x_1 - x_2\\ w_7 &= 21 - x_1 - 2 x_2\\ w_8 &= 10 - x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, \ldots, 8 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad w_1 = 1, \quad w_2 = 2, \quad w_3 = 6, \quad w_4 = 5, \quad w_5 = 16, \quad w_6 = 12, \quad w_7 = 21, \quad w_8 = 10.\]

Choose \(x_1\) and \(w_1\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ w_i \geq 0 \right\}_{i = 1}^7 = \min\left\{ 1, 2, 3, 5, 8, 12, 21 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 1, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 1, \quad w_3 = 4, \quad w_4 = 4, \quad w_5 = 14, \quad w_6 = 11, \quad w_7 = 20, \quad w_8 = 10.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 3 - 3 w_1 + 8 x_2\\ \text{subject to} \quad x_1 &= 1 - w_1 + 2 x_2\\ w_2 &= 1 + w_1 - x_2\\ w_3 &= 4 + 2 w_1 - 3 x_2\\ w_4 &= 4 + w_1 - 2 x_2\\ w_5 &= 14 + 2 w_1 - 5 x_2\\ w_6 &= 11 + w_1 - 3 x_2\\ w_7 &= 20 + w_1 - 4 x_2\\ w_8 &= 10 - x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, \ldots, 8 \end{aligned}\end{split}\]

Choose \(x_2\) and \(w_2\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_1, \left\{ w_i \right\}_{i = 2}^8 \right\}_{\geq 0} = \min\left\{ -\frac{1}{2}, 1, \frac{4}{3}, 2, \frac{14}{5}, \frac{11}{3}, 5, 10 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 3, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 1, \quad w_4 = 2, \quad w_5 = 9, \quad w_6 = 8, \quad w_7 = 16, \quad w_8 = 9.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 3 + 5 w_1 - 8 w_2\\ \text{subject to} \quad x_1 &= 3 + w_1 - 2 w_2\\ x_2 &= 1 + w_1 - w_2\\ w_3 &= 1 - w_1 + 3 w_2\\ w_4 &= 2 - w_1 + 2 w_2\\ w_5 &= 9 - 3 w_1 + 5 w_2\\ w_6 &= 8 - 2 w_1 + 3 w_2\\ w_7 &= 16 - 3 w_1 + 4 w_2\\ w_8 &= 9 - w_1 + w_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, \ldots, 8 \end{aligned}\end{split}\]

Choose \(w_1\) and \(w_3\) as the entering and leaving variable respectively where

\[w_1 = \min\left\{ x_1, x_2, \left\{ w_i \right\}_{i = 3}^8 \right\}_{\geq 0} = \min\left\{ -3, -1, 1, 2, 3, 4, \frac{16}{3}, 9 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 4, \quad x_2 = 2, \quad w_1 = 1, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 1, \quad w_5 = 6, \quad w_6 = 6, \quad w_7 = 13, \quad w_8 = 8.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 3 - 5 w_3 + 7 w_2\\ \text{subject to} \quad x_1 &= 4 - w_3 + w_2\\ x_2 &= 2 - w_3 + 2 w_2\\ w_1 &= 1 - w_3 + 3 w_2\\ w_4 &= 1 + w_3 - w_2\\ w_5 &= 6 + 3 w_3 - 4 w_2\\ w_6 &= 6 + 2 w_3 - 3 w_2\\ w_7 &= 13 + 3 w_3 - 5 w_2\\ w_8 &= 8 + w_3 - 2 w_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, \ldots, 8 \end{aligned}\end{split}\]

Choose \(w_2\) and \(w_4\) as the entering and leaving variable respectively where

\[w_2 = \min\left\{ x_1, x_2, w_1, \left\{ w_i \right\}_{i = 4}^8 \right\}_{\geq 0} = \min\left\{ -4, -1, -\frac{1}{3}, 1, \frac{3}{2}, 2, \frac{13}{5}, 4 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 5, \quad x_2 = 4, \quad w_1 = 4, \quad w_2 = 1, \quad w_3 = 0, \quad w_4 = 0, \quad w_5 = 2, \quad w_6 = 3, \quad w_7 = 8, \quad w_8 = 6.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 23 + 2 w_3 - 7 w_4\\ \text{subject to} \quad x_1 &= 5 - w_4\\ x_2 &= 4 + w_3 - 2 w_4\\ w_1 &= 4 + 2 w_3 - 3 w_4\\ w_2 &= 1 + w_3 - w_4\\ w_5 &= 2 - w_3 + 4 w_4\\ w_6 &= 3 - w_3 + 3 w_4\\ w_7 &= 8 - 2 w_3 + 5 w_4\\ w_8 &= 6 - w_3 + 2 w_4\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, \ldots, 8 \end{aligned}\end{split}\]

Choose \(w_3\) and \(w_5\) as the entering and leaving variable respectively where

\[w_3 = \min\left\{ x_2, w_1, w_2, w_5, w_6, w_7, w_8 \right\}_{\geq 0} = \min\left\{ -4, -2, -1, 2, 3, 4, 6 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 5, \quad x_2 = 6, \quad w_1 = 8, \quad w_2 = 3, \quad w_3 = 2, \quad w_4 = 0, \quad w_5 = 0, \quad w_6 = 1, \quad w_7 = 4, \quad w_8 = 4.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 27 - 2 w_5 + w_4\\ \text{subject to} \quad x_1 &= 5 - w_4\\ x_2 &= 6 - w_5 + 2 w_4\\ w_1 &= 8 - 2 w_5 + 5 w_4\\ w_2 &= 3 - w_5 + 3 w_4\\ w_3 &= 2 - w_5 + 4 w_4\\ w_6 &= 1 + w_5 - w_4\\ w_7 &= 4 + 2 w_5 - 3 w_4\\ w_8 &= 4 + w_5 - 2 w_4\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, \ldots, 8 \end{aligned}\end{split}\]

Choose \(w_4\) and \(w_6\) as the entering and leaving variable respectively where

\[w_4 = \min\left\{ x_1, x_2, w_1, w_2, w_3, w_6, w_7, w_8 \right\}_{\geq 0} = \min\left\{ 5, -3, -\frac{8}{5}, -1, -\frac{1}{2}, 1, \frac{4}{3}, 2 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 4, \quad x_2 = 8, \quad w_1 = 13, \quad w_2 = 6, \quad w_3 = 6, \quad w_4 = 1, \quad w_5 = 0, \quad w_6 = 0, \quad w_7 = 1, \quad w_8 = 2.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 28 - w_5 - w_6\\ \text{subject to} \quad x_1 &= 4 - w_5 + w_6\\ x_2 &= 8 + w_5 - 2 w_6\\ w_1 &= 13 + 3 w_5 - 5 w_6\\ w_2 &= 6 + 2 w_5 - 3 w_6\\ w_3 &= 6 + 3 w_5 - 4 w_6\\ w_4 &= 1 + w_5 - w_6\\ w_7 &= 1 - w_5 + 3 w_6\\ w_8 &= 2 - w_5 + 2 w_6\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, \ldots, 8 \end{aligned}\end{split}\]

Exercise 2.9

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 2 x_1 + 3 x_2 + 4 x_3\\ \text{subject to} \quad w_1 &= 5 - 2 x_2 - 3 x_3\\ w_2 &= 4 - x_1 - x_2 - 2 x_3\\ w_3 &= 7 - x_1 - 2 x_2 - 3 x_3\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad w_1 = 5, \quad w_2 = 4, \quad w_3 = 7.\]

Choose \(x_3\) and \(w_1\) as the entering and leaving variable respectively where

\[x_3 = \min\left\{ w_1, w_2, w_3 \right\}_{\geq 0} = \min\left\{ \frac{5}{3}, 2, \frac{7}{3} \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = \frac{5}{3}, \quad w_1 = 0, \quad w_2 = \frac{2}{3}, \quad w_3 = 2.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{3} \left( 20 + 6 x_1 + x_2 - 4 w_1 \right)\\ \text{subject to} \quad x_3 &= \frac{1}{3} \left( 5 - 2 x_2 - w_1 \right)\\ w_2 &= \frac{1}{3} \left( 2 - 3 x_1 + x_2 + 2 w_1 \right)\\ w_3 &= 2 - x_1 + w_1\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Choose \(x_1\) and \(w_2\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ w_2, w_3 \right\}_{\geq 0} = \min\left\{ \frac{2}{3}, 2 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = \frac{2}{3}, \quad x_2 = 0, \quad x_3 = \frac{5}{3}, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = \frac{4}{3}.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 8 + x_2 - 2 w_2\\ \text{subject to} \quad x_1 &= \frac{1}{3} \left( 2 + x_2 + 2 w_1 - 3 w_2 \right)\\ x_3 &= \frac{1}{3} \left( 5 - 2 x_2 - w_1 \right)\\ w_3 &= \frac{1}{3} \left( 4 - x_2 + w_1 + 3 w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Choose \(x_2\) and \(x_3\) as the entering and leaving variable respectively where

\[x_2 = \min\left\{ x_1, x_3, w_3 \right\}_{\geq 0} = \min\left\{ -2, \frac{5}{2}, 4 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = \frac{3}{2}, \quad x_2 = \frac{5}{2}, \quad x_3 = 0, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = \frac{1}{2}.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{2} \left( 21 - 3 x_3 - w_1 - 4 w_2 \right)\\ \text{subject to} \quad x_1 &= \frac{1}{2} \left( 3 - x_3 + w_1 - w_2 \right)\\ x_2 &= \frac{1}{2} \left( 5 - 3 x_3 - w_1 \right)\\ w_3 &= \frac{1}{2} \left( 1 + x_3 + w_1 + w_2 \right)\\ x_i &\geq 0 \quad i = 1, 2, 3\\ w_i &\geq 0 \quad i = 1, 2, 3 \end{aligned}\end{split}\]

Exercise 2.10

Rewriting the LP in standard form yields

\[\begin{split}\begin{aligned} \text{maximize} \quad 6 x_1 + 8 x_2 + 5 x_3 + 9 x_4 &\\ \text{subject to} \quad x_1 + x_2 + x_3 + x_4 &\leq 1\\ -x_1 - x_2 - x_3 - x_4 &\leq -1\\ x_i &\geq 0 \quad i = 1, 2, 3, 4. \end{aligned}\end{split}\]

An equivalent representation with slack variables is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 6 x_1 + 8 x_2 + 5 x_3 + 9 x_4\\ \text{subject to} \quad w_1 &= 1 - x_1 - x_2 - x_3 - x_4\\ w_2 &= 1 + x_1 + x_2 + x_3 + x_4\\ x_i &\geq 0 \quad i = 1, 2, 3, 4\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 0, \quad w_1 = 1, \quad w_2 = 1.\]

Choose \(x_4\) and \(w_1\) as the entering and leaving variable respectively since that’s the only choice.

Update the current dictionary’s feasible solution to

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 1, \quad w_1 = 0, \quad w_2 = 2.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 9 - 3 x_1 - x_2 - 4 x_3 - 9 w_1\\ \text{subject to} \quad x_4 &= 1 - x_1 - x_2 - x_3 - w_1\\ w_2 &= 2 - w_1\\ x_i &\geq 0 \quad i = 1, 2, 3, 4\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Exercise 2.11

Rewriting the LP in standard form yields

\[\begin{split}\begin{aligned} -\text{maximize} \quad -x_1 - 8 x_2 - 9 x_3 - 2 x_4 - 7 x_5 - 3 x_6 &\\ \text{subject to} \quad -x_1 - x_2 - x_3 &\leq -1\\ -x_1 + x_4 + x_4 &\leq 0\\ x_1 - x_4 - x_4 &\leq 0\\ -x_2 - x_4 + x_6 &\leq 0\\ x_2 + x_4 - x_6 &\leq 0\\ x_3 + x_5 + x_6 &\leq 1\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

An equivalent representation with slack variables is

\[\begin{split}\begin{aligned} -\text{maximize} \quad \zeta &= -x_1 - 8 x_2 - 9 x_3 - 2 x_4 - 7 x_5 - 3 x_6\\ \text{subject to} \quad w_1 &= -1 + x_1 + x_2 + x_3\\ w_2 &= x_1 - x_4 - x_5\\ w_3 &= -x_1 + x_4 + x_5\\ w_4 &= x_2 + x_4 - x_6\\ w_5 &= -x_2 - x_4 + x_6\\ w_6 &= 1 - x_3 - x_5 - x_6\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

Initial infeasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 0, \quad x_5 = 0, \quad x_6 = 0, \quad w_1 = -1, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 0, \quad w_5 = 0, \quad w_6 = 1.\]

The auxiliary problem is

\[\begin{split}\begin{aligned} \text{maximize} \quad -x_0 &\\ \text{subject to} \quad -x_1 - x_2 - x_3 - x_0 &\leq -1\\ -x_1 + x_4 + x_4 - x_0 &\leq 0\\ x_1 - x_4 - x_4 - x_0 &\leq 0\\ -x_2 - x_4 + x_6 - x_0 &\leq 0\\ x_2 + x_4 - x_6 - x_0 &\leq 0\\ x_3 + x_5 + x_6 - x_0 &\leq 1\\ x_i &\geq 0 \quad i = 0, 1, \ldots, 6 \end{aligned}\end{split}\]

and its initial infeasible dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad w_1 &= -1 + x_1 + x_2 + x_3 + x_0\\ w_2 &= x_1 - x_4 - x_5 + x_0\\ w_3 &= -x_1 + x_4 + x_5 + x_0\\ w_4 &= x_2 + x_4 - x_6 + x_0\\ w_5 &= -x_2 - x_4 + x_6 + x_0\\ w_6 &= 1 - x_3 - x_5 - x_6 + x_0\\ x_i &\geq 0 \quad i = 0, 1, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

Initial infeasible solution for auxiliary problem:

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 0, \quad x_5 = 0, \quad x_6 = 0, \quad w_1 = -1, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 0, \quad w_5 = 0, \quad w_6 = 1.\]

Pivot the infeasible dictionary with \(x_0\) as the entering variable and \(w_1\), the most infeasible variable, as the leaving variable. The resulting dictionary is then

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -1 + x_1 + x_2 + x_3 - w_1\\ \text{subject to} \quad x_0 &= 1 - x_1 - x_2 - x_3 + w_1\\ w_2 &= 1 - x_2 - x_3 - x_4 - x_5 + w_1\\ w_3 &= 1 - 2 x_1 - x_2 - x_3 + x_4 + x_5 + w_1\\ w_4 &= 1 - x_1 - x_3 + x_4 - x_6 + w_1\\ w_5 &= 1 - x_1 - 2 x_2 - x_3 - x_4 + x_6 + w_1\\ w_6 &= 2 - x_1 - x_2 - 2 x_3 - x_5 - x_6 + w_1\\ x_i &\geq 0 \quad i = 0, 1, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

and its feasible solution is updated to

\[x_0 = 1, \quad x_1 = 0, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 0, \quad x_5 = 0, \quad x_6 = 0, \quad w_1 = 0, \quad w_2 = 1, \quad w_3 = 1, \quad w_4 = 1, \quad w_5 = 1, \quad w_6 = 2.\]

Even though \(x_1\) and \(x_2\) are valid choices, selecting \(x_3\) will make phase two much easier. Choose \(x_3\) and \(x_0\) as the entering and leaving variable respectively where

\[x_3 = \min\left\{ x_0, w_2, w_3, w_4, w_5, w_6 \right\}_{\geq 0} = \min\left\{ 1, 1, 1, 1, 1, 1 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_0 = 0, \quad x_1 = 0, \quad x_2 = 0, \quad x_3 = 1, \quad x_4 = 0, \quad x_5 = 0, \quad x_6 = 0, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 0, \quad w_5 = 0, \quad w_6 = 0.\]

Pivot auxiliary dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= -x_0\\ \text{subject to} \quad x_3 &= 1 - x_0 - x_1 - x_2 + w_1\\ w_2 &= x_0 + x_1 - x_4 - x_5\\ w_3 &= x_0 - x_1 + x_4 + x_5\\ w_4 &= x_0 + x_2 + x_4 - x_6\\ w_5 &= x_0 - x_2 - x_4 + x_6\\ w_6 &= 2 x_0 + x_1 + x_2 - x_5 - x_6 - w_1\\ x_i &\geq 0 \quad i = 0, 1, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

The dictionary is optimal for the auxiliary problem, so \(x_0\) can be dropped and the original objective function can be reintroduced with the basic variables substituted appropriately:

\[\begin{split}\begin{aligned} -\text{maximize} \quad \zeta &= -9 + 8 x_1 + x_2 - 2 x_4 - 7 x_5 - 3 x_6 - 9 w_1\\ \text{subject to} \quad x_3 &= 1 - x_1 - x_2 + w_1\\ w_2 &= x_1 - x_4 - x_5\\ w_3 &= -x_1 + x_4 + x_5\\ w_4 &= x_2 + x_4 - x_6\\ w_5 &= -x_2 - x_4 + x_6\\ w_6 &= x_1 + x_2 - x_5 - x_6 - w_1\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

Initial feasible solution:

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 1, \quad x_4 = 0, \quad x_5 = 0, \quad x_6 = 0, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 0, \quad w_5 = 0, \quad w_6 = 0.\]

Choose \(x_1\) and \(w_3\) as the entering and leaving variable respectively where

\[x_1 = \min\left\{ x_3, w_3 \right\}_{\geq 0} = \min\left\{ 1, 0 \right\}_{\geq 0}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 1, \quad x_4 = 0, \quad x_5 = 0, \quad x_6 = 0, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 0, \quad w_5 = 0, \quad w_6 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} -\text{maximize} \quad \zeta &= -9 + x_2 + 6 x_4 + x_5 - 3 x_6 - 9 w_1 - 8 w_3\\ \text{subject to} \quad x_1 &= x_4 + x_5 - w_3\\ x_3 &= 1 - x_2 - x_4 - x_5 + w_1 + w_3\\ w_2 &= -w_3\\ w_4 &= x_2 + x_4 - x_6\\ w_5 &= -x_2 - x_4 + x_6\\ w_6 &= x_2 + x_4 - x_6 - w_1 - w_3\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

Choose \(x_4\) and \(w_5\) as the entering and leaving variable respectively where

\[x_4 = \min\left\{ x_3, w_5 \right\}_{\geq 0} = \min\left\{ 0 \right\}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 0, \quad x_2 = 0, \quad x_3 = 1, \quad x_4 = 0, \quad x_5 = 0, \quad x_6 = 0, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} -\text{maximize} \quad \zeta &= -9 - 5 x_2 + x_5 + 3 x_6 - 9 w_1 - 8 w_3 - 6 w_5\\ \text{subject to} \quad x_1 &= -x_2 + x_6 - w_3\\ x_3 &= 1 - x_5 - x_6 + w_1 + w_3 + w_5\\ x_4 &= -x_2 + x_6 - w_5\\ w_2 &= -w_3\\ w_4 &= -w_5\\ w_6 &= -w_1 - w_3 - w_5\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

Choose \(x_6\) and \(x_3\) as the entering and leaving variable respectively where

\[x_6 = \min\left\{ x_3 \right\}_{\geq 0} = \min\left\{ 1, 0 \right\}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 1, \quad x_2 = 0, \quad x_3 = 0, \quad x_4 = 1, \quad x_5 = 0, \quad x_6 = 1, \quad w_1 = 0, \quad w_2 = 0, \quad w_3 = 0, \quad w_4 = 0, \quad w_5 = 0, \quad w_6 = 0.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} -\text{maximize} \quad \zeta &= -6 - 5 x_2 - 3 x_3 - 2 x_5 - 6 w_1 - 5 w_3 - 3 w_5\\ \text{subject to} \quad x_1 &= 1 - x_2 - x_3 - x_5 + w_1 + w_5\\ x_4 &= 1 - x_2 - x_3 - x_5 + w_1 + w_3\\ x_6 &= 1 - x_3 - x_5 + w_1 + w_3 + w_5\\ w_2 &= -w_3\\ w_4 &= -w_5\\ w_6 &= -w_1 - w_3 - w_5\\ x_i &\geq 0 \quad i = 1, 2, \ldots, 6\\ w_i &\geq 0 \quad i = 1, 2, \ldots, 6 \end{aligned}\end{split}\]

Since no other coefficients are positive, the solution is optimal.

Exercise 2.12 and Exercise 2.13

The previous exercises were solved using the proposed tool.

Exercise 2.14

Choose \(x_6\) and \(w_1\) as the entering and leaving variable respectively where

\[x_6 = \min\left\{ w_1, w_2 \right\}_{\geq 0} = \min\left\{ 1, \frac{5}{3} \right\}.\]

Update the current dictionary’s feasible solution to

\[x_1 = 0, \quad x_2 = 1, \quad w_1 = 0, \quad w_2 = 2.\]

Pivot dictionary to

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 9 + 7 x_1 - 6 w_1\\ \text{subject to} \quad x_2 &= 1 + x_1 - w_1\\ w_2 &= 2 - 5 x_1 + 3 w_1\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Exercise 2.15

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 4 - w_1 - 2 x_2\\ \text{subject to} \quad x_1 &= 3 - 2 x_2\\ w_2 &= 1 + w_1 - x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Suppose the optimal solution for the above dictionary \(D_0\) is

\[x_1 = 3, \quad x_2 = 0, \quad w_1 = 0, \quad w_2 = 1.\]

Since pivot operations are reversible, one can mechanically trace back to original problem where \(w_1\) and \(w_2\) are the initial slack variables. As shown in Exercise 2.17 and Exercise 2.18, reverse pivots only need to examine the variables whose coefficient is negative in the objective function.

Even though the following dictionaries are still feasible with the proposed optimal solution, none of them have \(w_1\) and \(w_2\) as the initial slack variables:

• \(D_{1 \mapsto 0}\) cannot be pivoted to \(D_0\) with one iteration.

• \(D_{6 \mapsto 3} = D_{4 \mapsto 2}\), but \(D_{4 \mapsto 2}\) cannot be pivoted to \(D_{6 \mapsto 3}\) with one iteration.

• \(D_{5 \mapsto 2} = D_{1 \mapsto 0}\), but \(D_{1 \mapsto 0}\) cannot be pivoted to \(D_{5 \mapsto 2}\) with one iteration.

• \(D_{7 \mapsto 4}\) cannot be pivoted to \(D_{4 \mapsto 2}\) with one iteration.

If feasibility preservation of intermediate dictionaries are no longer necessary, then choose \(w_1\) and \(x_1\) as the entering and leaving variable respectively where

\[w_1 = \frac{3 - x_1 - 2 x_2}{0}.\]

Adopting the convention where \(\frac{0}{0}\) is treated as a zero, the corrresponding pivoted dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 4 - \frac{3 - x_1 - 2 x_2}{0} - 2 x_2\\ \text{subject to} \quad w_1 &= \frac{3 - x_1 - 2 x_2}{0}\\ w_2 &= 1 + \frac{3 - x_1 - 2 x_2}{0} - x_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

\(D_{1 \mapsto 0}\)

Let \(w_1\) be the previous leaving variable and \(w_2\) be the previous entering variable.

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 5 - 3 x_2 - w_2\\ \text{subject to} \quad x_1 &= 3 - 2 x_2\\ w_1 &= -1 + x_2 + w_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

No need to continue along this path since the reverse pivot is not reversible.

\(D_{2 \mapsto 0}\)

Let \(x_2\) be the previous leaving variable and \(w_2\) be the previous entering variable.

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 2 - 3 w_1 + 2 w_2\\ \text{subject to} \quad x_1 &= 1 - 2 w_1 + 2 w_2\\ x_2 &= 1 + w_1 - w_2\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

\(D_{3 \mapsto 0}\)

Let \(x_2\) be the previous leaving variable and \(x_1\) be the previous entering variable.

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 1 + x_1 - w_1\\ \text{subject to} \quad x_2 &= \frac{1}{2} (3 - x_1)\\ w_2 &= \frac{1}{2} (-1 + x_1 + 2 w_1)\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

\(D_{4 \mapsto 2}\)

Let \(w_1\) be the previous leaving variable and \(x_1\) be the previous entering variable.

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{2} (1 + 3 x_1 - 2 w_2)\\ \text{subject to} \quad x_2 &= \frac{1}{2} (3 - x_1)\\ w_1 &= \frac{1}{2} (1 - x_1 + 2 w_2)\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

\(D_{5 \mapsto 2}\)

Let \(w_1\) be the previous leaving variable and \(x_2\) be the previous entering variable. The resulting dictionary is equal to \(D_{1 \mapsto 0}\).

\(D_{6 \mapsto 3}\)

Let \(w_1\) be the previous leaving variable and \(w_2\) be the previous entering variable. The resulting dictionary is equal to \(D_{4 \mapsto 2}\).

\(D_{7 \mapsto 4}\)

Let \(w_2\) be the previous leaving variable and \(w_1\) be the previous entering variable.

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{1}{2} (3 + x_1 - 4 w_1)\\ \text{subject to} \quad x_2 &= \frac{1}{2} (3 - x_1)\\ w_2 &= \frac{1}{2} (-1 + x_1 + 2 w_1)\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

No need to continue along this path since the reverse pivot is not reversible. The only choice for a pivot is choosing \(x_1\) and \(x_2\) as the entering and leaving variable respectively resulting in

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= 3 - x_2 - 2 w_1\\ \text{subject to} \quad x_1 &= 3 - 2 x_2\\ w_2 &= 1 - x_2 + w_1\\ x_i &\geq 0 \quad i = 1, 2\\ w_i &\geq 0 \quad i = 1, 2 \end{aligned}\end{split}\]

Exercise 2.16

The sequence of basic solutions produced by the simplex method starts at \((0, 0)\) and advances counter-clockwise along the perimeter of the plot until the vertex \((4, 8)\) is encountered.

from sympy import symbols
from sympy import plot_implicit, And

x1, x2 = symbols('x_1 x_2')

c1 = x1 - 2 * x2 <= 1
c2 = And(c1, x1 - x2 <= 2)
c3 = And(c2, 2 * x1 - x2 <= 6)
c4 = And(c3, x1 <= 5)
c5 = And(c4, 2 * x1 + x2 <= 16)
c6 = And(c5, x1 + x2 <= 12)
c7 = And(c6, x1 + 2 * x2 <= 21)
c8 = And(c7, x2 <= 10)
c9 = And(c8, x1 >= 0)
c10 = And(c9, x2 >= 0)

plot_implicit(c10, (x1, 0, 5.5), (x2, 0, 11),
              title='Feasible Region', xlabel='$x_1$', ylabel='$x_2$');

<Figure size 640x480 with 1 Axes>

Exercise 2.17

See Exercise 2.9.

Exercise 2.18

The general linear programming problem with slack variables is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \sum_{j \in \mathcal{N}} c_j x_j\\ \text{subject to} \quad w_i &= b_i - \sum_{j \in \mathcal{N}}^n a_{ij} x_j \quad i \in \mathcal{B}\\ x_j &\geq 0 \quad j = 1, 2, \ldots, n\\ w_i &\geq 0 \quad i = 1, 2, \ldots, m \end{aligned}\end{split}\]

Without loss of generality, the entering variable \(x_e\) will be chosen from \(\{j \in \mathcal{N} \colon c_j > 0 \}\); consequently, the leaving variable \(w_l\) will be chosen from \(\{i \in \mathcal{B} \colon a_{ie} > 0 \text{ and } \frac{b_i}{a_{ie}} \text{is minimal}\}\).

Pivoting will result in

\[\begin{split}x_e &= a_{le}^{-1} \left( b_l - w_l - \sum_{j \in \mathcal{N} \setminus e}^n a_{lj} x_j \right)\\ \\ \zeta &= c_e x_e + \sum_{j \in \mathcal{N} \setminus e}^n c_j x_j = \frac{c_e}{a_{le}} b_l - \frac{c_e}{a_{le}} w_l + \sum_{j \in \mathcal{N} \setminus e}^n \left( c_j - \frac{c_e a_{lj}}{a_{le}} \right) x_j\end{split}\]

where the other constraints are replaced appropriately, but is not essential to the conclusion of this proof.

Since \(-\frac{c_e}{a_{le}}\) must be negative, the nonbasic variable \(w_l\) cannot be selected in the next iteration.

Exercise 2.19

The equivalent problem with slack variables is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \sum_{j = 1}^n p_j x_j\\ \text{subject to} \quad w_0 &= \beta - \sum_{j = 1}^n q_j x_j\\ w_j &= 1 - x_j\\ x_j &\geq 0 \quad j = 1, 2, \ldots, n\\ w_j &\geq 0 \quad j = 1, 2, \ldots, n\\ w_0 &\geq 0 \end{aligned}\end{split}\]

where the initial feasible solution is

\[x_j = 0 \qquad \land \qquad w_0 = \beta \qquad \land \qquad w_j = 1.\]

Suppose \(x_1\) is the first entering variable. Pivoting requires determining

\[x_1 = \min\left\{ w_0, w_1 \right\}_{\geq 0} = \min\left\{ \frac{\beta}{q_1}, 1 \right\}.\]

In order to make progress and simplify the analysis, assume

\[\beta \geq q_1 + q_2 + \cdots + q_{k - 2} + q_{k - 1}\]

where \(k \in [0, n]\) is the largest possible index. This will cause the simplex algorithm to swap \(x_j\) and \(w_j\) in each constraint where \(1 \leq j < k\) resulting in

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \sum_{j = 1}^{k - 1} p_j (1 - w_j) + \sum_{j = k}^n p_j x_j\\ \text{subject to} \quad w_0 &= \beta - \sum_{j = 1}^{k - 1} q_j (1 - w_j) - \sum_{j = k}^n q_j x_j\\ x_j &= 1 - w_j \quad j < k\\ w_j &= 1 - x_j \quad j \geq k\\ x_j &\geq 0 \quad j = 1, 2, \ldots, n\\ w_j &\geq 0 \quad j = 1, 2, \ldots, n\\ w_0 &\geq 0 \end{aligned}\end{split}\]

Now pivot \(x_k \leftrightarrow w_0\) since

\[x_k = \min\left\{ w_0, w_k \right\}_{\geq 0} = \min\left\{ \frac{\beta - \sum_{j = 1}^{k - 1} q_j}{q_k}, 1 \right\}.\]

Update the current dictionary’s feasible solution to

\[\begin{split}x_j &= 1 \quad j < k,\\ x_k &= \frac{\beta - \sum_{j = 1}^{k - 1} q_j}{q_k},\\ x_j &= 0 \quad j > k,\\ w_0 &= 0,\\ w_j &= 0 \quad j < k,\\ w_k &= 1 - \frac{\beta - \sum_{j = 1}^{k - 1} q_j}{q_k},\\ w_j &= 1 \quad j > k.\end{split}\]

The resulting dictionary is

\[\begin{split}\begin{aligned} \text{maximize} \quad \zeta &= \frac{p_k}{q_k} (\beta - w_0) + \sum_{j = 1}^{k - 1} p_j - \frac{p_k}{q_k} q_j + \left( \frac{p_k}{q_k} q_j - p_j \right) w_j + \sum_{j = k + 1}^n \left( p_j - \frac{p_k}{q_k} q_j \right) x_j\\ \text{subject to} \quad x_k &= \frac{1}{q_k} \left( \beta - \sum_{j = 1}^{k - 1} q_j (1 - w_j) - w_0 - \sum_{j = k + 1}^n q_j x_j \right)\\ x_j &= 1 - w_j \quad j < k\\ w_k &= 1 - \frac{1}{q_k} \left( \beta - \sum_{j = 1}^{k - 1} q_j (1 - w_j) - w_0 - \sum_{j = k + 1}^n q_j x_j \right)\\ w_j &= 1 - x_j \quad j > k\\ x_j &\geq 0 \quad j = 1, 2, \ldots, n\\ w_j &\geq 0 \quad j = 1, 2, \ldots, n\\ w_0 &\geq 0 \end{aligned}\end{split}\]

This dictionary is optimal if all objective coefficients are non-positive since that would make the set of entering variables empty. This is the case if the following assumption

\[\frac{p_1}{q_1} > \cdots > \frac{p_{k - 1}}{q_{k - 1}} > \frac{p_k}{q_k} > \frac{p_{k + 1}}{q_{k + 1}} > \cdots > \frac{p_n}{q_n}\]

holds since that would make \(\frac{p_k}{q_k} q_j - p_j < 0\) for \(j < k\) and \(p_j - \frac{p_k}{q_k} q_j < 0\) for \(j > k\).

Note that if one applies the book’s proposed assumption, the optimal solution is the reverse order. The derivation would start with \(x_n\) instead of \(x_1\) and \(\beta \geq q_{k + 1} + q_{k + 2} + \cdots + q_{n - 1} + q_n\) where \(k \in [0, n]\) is the smallest possible index.

References

Bur

Jim Burke. Introduction. https://www.math.washington.edu/ burke/crs/407/notes/section1.pdf. Section 1.5.1 accessed on 2016-11-27.