29.3 The simplex algorithm

29.3-1

Complete the proof of Lemma 29.4 by showing that it must be the case that $c = c'$ and $v = v'$.

We subtract equation $\text{(29.81)}$ from equation $\text{(29.79)}$.

$$z = v + \sum_{j \in N} c_j x_j, \tag{29.79}$$

$$z = v' + \sum_{j \in N} c_j' x_j. \tag{29.81}$$

Thus we have,

$$ \begin{aligned} 0 & = v - v' + \sum_{j \in N} (c_j - c_j') x_j. \\ \sum_{j \in N} c_j' x_j & = v - v' + \sum_{j \in N} c_j x_j. \end{aligned} $$

By Lemma 29.3, we have $c_j = c_j'$ for every $j$ and $v = v'$ since $v - v' = 0$.

29.3-2

Show that the call to $\text{PIVOT}$ in line 12 of $\text{SIMPLEX}$ never decreases the value of $v$.

The only time $v$ is updated in $\text{PIVOT}$ is line 14, so it will suffice to show that $c_e \hat b_e \ge 0$. Prior to making the call to $\text{PIVOT}$, we choose an index $e$ such that $c_e > 0$, and this is unchanged in $\text{PIVOT}$. We set $\hat b_e$ in line 3 to be $b_l / a_{le}$.

The loop invariant proved in Lemma 29.2 tells us that $b_l \ge 0$. The if-condition of line 6 of $\text{SIMPLEX}$ tells us that only the noninfinite $\delta_i$ must have $a_{ie} > 0$, and we choose $l$ to minimize $\delta_l$, so we must have $a_{le} > 0$. Thus, $c_e \hat b_e \ge 0$, which implies $v$ can never decrease.

29.3-3

Prove that the slack form given to the $\text{PIVOT}$ procedure and the slack form that the procedure returns are equivalent.

To show that the two slack forms are equivalent, we will show both that they have equal objective functions, and their sets of feasible solutions are equal.

First, we'll check that their sets of feasible solutions are equal. Basically all we do to the constraints when we pivot is take the non-basic variable, $e$, and solve the equation corresponding to the basic variable $l$ for $e$. We are then taking that expression and replacing $e$ in all the constraints with this expression we got by solving the equation corresponding to $l$. Since each of these algebraic operations are valid, the result of the sequence of them is also algebraically equivalent to the original.

Next, we'll see that the objective functions are equal. We decrease each $c_j$ by $c_e \hat a_{ej}$, which is to say that we replace the non-basic variable we are making basic with the expression we got it was equal to once we made it basic.

Since the slack form returned by $\text{PIVOT}$, has the same feasible region and an equal objective function, it is equivalent to the original slack form passed in.

29.3-4

Suppose we convert a linear program $(A, b, c)$ in standard form to slack form. Show that the basic solution is feasible if and only if $b_i \ge 0$ for $i = 1, 2, \ldots, m$.

First suppose that the basic solution is feasible. We set each $x_i = 0$ for $1 \le i \le n$, so we have $x_{n + i} = b_i - \sum_{j = 1}^n a_{ij}x_j = b_i$ as a satisfied constraint. Since we also require $x_{n + i} \ge 0$ for all $1 \le i \le m$, this implies $b_i \ge 0$.

Now suppose $b_i \ge 0$ for all $i$. In the basic solution we set $x_i = 0$ for $1 \le i \le n$ which satisfies the nonnegativity constraints. We set $x_{n + i} = b_i$ for $1 \le i \le m$ which satisfies the other constraint equations, and also the nonnegativity constraints on the basic variables since $b_i \ge 0$. Thus, every constraint is satisfied, so the basic solution is feasible.

29.3-5

Solve the following linear program using $\text{SIMPLEX}$:

$$ \begin{array}{lrcrcrl} \text{maximize} & 18x_1 & + & 12.5x_2 \\ \text{subject to} & \\ & x_1 & + & x_2 & \le & 20 \\ & x_1 & & & \le & 12 \\ & & & x_2 & \le & 16 \\ & & x_1, x_2 & & \ge & 0 & . \end{array} $$

First, we rewrite the linear program into it's slack form

$$ \begin{array}{lrl} \text{maximize} & 18x_1 + 12.5x_2 \\ \text{subject to} & \\ & x_3 & = 20 - x_1 - x_2 \\ & x_4 & = 12 - x_1 \\ & x_5 & = 16 - x_2 \\ & x_1, x_2, x_3, x_4, x_5 & \ge 0. \end{array} $$

We now stop since no more non-basic variables appear in the objective with a positive coefficient. Our solution is $(12, 8, 0, 0, 8)$ and has a value of $316$. Going back to the standard form we started with, we just disregard the values of $x_3$ through $x_5$ and have the solution that $x_1 = 12$ and $x_2 = 8$. We can check that this is both feasible and has the objective achieve $316$.

29.3-6

Solve the following linear program using $\text{SIMPLEX}$:

$$ \begin{array}{lrcrcrl} \text{maximize} & 5x_1 & - & 3x_2 \\ \text{subject to} & \\ & x_1 & - & x_2 & \le & 1 \\ & 2x_1 & + & x_2 & \le & 2 \\ & & x_1, x_2 & & \ge & 0 & . \end{array} $$

First, we convert the linear program into it's slack form

$$ \begin{array}{rcrcrcrl} z & = & & & 5x_1 & - & 3x_2 \\ x_3 & = & 1 & - & x_1 & + & x_2 \\ x_4 & = & 2 & - & 2x_1 & - & x_2 & . \end{array} $$

The nonbasic variables are $x_1$ and $x_2$. Of these, only $x_1$ has a positive coefficient in the objective function, so we must choose $x_e = x_1$. Both equations limit $x_1$ by $1$, so we'll choose the first one to rewrite $x_1$ with. Using $x_1 = 1 − x_3 + x_2$ we obtain the new system

$$ \begin{array}{rcrcrcrl} z & = & 5 & - & 5x_3 & + & 2x_2 & \\ x_1 & = & 1 & - & x_3 & + & x_2 & \\ x_4 & = & & & 2x_3 & - & 3x_2 & . \end{array} $$

Now $x_2$ is the only nonbasic variable with positive coefficient in the objective function, so we set $x_e = x_2$. The last equation limits $x_2$ by $0$ which is most restrictive, so we set $x_2 = \frac{2}{3} x_3 − \frac{1}{3} x_4$. Rewriting, our new system becomes

$$ \begin{array}{rcrcrcrl} z & = & 5 & - & \frac{11}{3} x_3 & - & \frac{2}{3} x_4 \\ x_1 & = & 1 & - & \frac{1}{3} x_3 & - & \frac{1}{3} x_4 \\ x_2 & = & & & \frac{2}{3} x_3 & - & \frac{1}{3} x_4 & . \end{array} $$

Every nonbasic variable now has negative coefficient in the objective function, so we take the basic solution $(x_1, x_2, x_3, x_4) = (1, 0, 0, 0)$. The objective value this achieves is $5$.

29.3-7

Solve the following linear program using $\text{SIMPLEX}$:

$$ \begin{array}{lrcrcrcrl} \text{minimize} & x_1 & + & x_2 & + & x_3 \\ \text{subject to} & \\ & 2x_1 & + & 7.5x_2 & + & 3x_3 & \ge & 10000 \\ & 20x_1 & & 5x_2 & + & 10x_3 & \ge & 30000 \\ & & x_1, x_2, x_3 & & & & \ge & 0 & . \end{array} $$

First, we convert this equation to the slack form. Doing so doesn't change the objective, but the constraints become

$$ \begin{array}{rcrcrcrcr} z & = & & - & x_1 & - & x_2 & - & x_3 \\ x_4 & = & -10000 & + & 2x_1 & + & 7.5x_2 & + & 3x_3 \\ x_5 & = & -30000 & + & 20x_1 & + & 5x_2 & + & 10x_3 \\ x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

Also, since the objective is to minimize a given function, we'll change it over to maximizing the negative of that function. In particular maximize $−x_1 − x_2 − x_3$. Now, we note that the initial basic solution is not feasible, because it would leave $x_4$ and $x_5$ being negative. This means that finding an initial solution requires using the method of section 29.5. The auxiliary linear program in slack form is

$$ \begin{array}{rcrcrcrcrcr} z & = & & - & x_0 \\ x_4 & = & -10000 & + & x_0 & + & 2x_1 & + & 7.5x_2 & + & 3x_3 \\ x_5 & = & -30000 & + & x_0 & + & 20x_1 & + & 5x_2 & + & 10x_3 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

We choose $x_0$ as the entering variable and $x_5$ as the leaving variable, since it is the basic variable whose value in the basic solution is most negative. After pivoting, we have the slack form

$$ \begin{array}{rcrcrcrcrcr} z & = & -30000 & + & 20x_1 & + & 5x_2 & + & 10x_3 & - & x_5 \\ x_0 & = & 30000 & - & 20x_1 & - & 5x_2 & - & 10x_3 & + & x_5 \\ x_4 & = & 20000 & - & 18x_1 & + & 2.5x_2 & - & 7x_3 & + & x_5 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

The associated basic solution is feasible, so now we just need to repeatedly call $\text{PIVOT}$ until we obtain an optimal solution to $L_{aux}$. We'll choose $x_2$ as our entering variable. This gives

$$ \begin{array}{rcrcrcrcrcr} z & = & & - & x_0 \\ x_2 & = & 6000 & - & 0.2x_0 & - & 4x_1 & - & 2x_3 & + & 0.2x_5 \\ x_4 & = & 35000 & - & 0.5x_0 & - & 28x_1 & - & 12x_3 & + & 1.5x_5 \\ x_0, x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

This slack form is the final solution to the auxiliary problem. Since this solution has $x_0 = 0$, we know that our initial problem was feasible. Furthermore, since $x_0 = 0$, we can just remove it from the set of constraints. We then restore the original objective function, with appropriate substitutions made to include only the nonbasic variables. This yields

$$ \begin{array}{rcrcrcrcr} z & = & -6000 & + & 3x_1 & + & x_3 & - & 0.2x_5 \\ x_2 & = & 6000 & - & 4x_1 & - & 2x_3 & + & 0.2x_5 \\ x_4 & = & 35000 & - & 28x_1 & - & 12x_3 & + & 1.5x_5 \\ x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

This slack form has a feasible basic solution, and we can return it to $\text{SIMPLEX}$. We choose $x_1$ as our entering variable. This gives

$$ \begin{array}{rcrcrcrcr} z & = & -2250 & - & \frac{2}{7} x_3 & - & \frac{3}{28} x_4 & - & \frac{11}{280} x_5 \\ x_1 & = & 1250 & - & \frac{3}{7} x_3 & - & \frac{1}{28} x_4 & + & \frac{15}{280} x_5 \\ x_2 & = & 1000 & - & \frac{2}{7} x_3 & + & \frac{4}{28} x_4 & - & \frac{4}{280} x_5 \\ x_1, x_2, x_3, x_4, x_5 & \ge & 0 & . \end{array} $$

At this point, all coefficients in the objective function are negative, so the basic solution is an optimal solution. This solution is $(x_1, x_2, x_3) = (1250, 1000, 0)$.

29.3-8

In the proof of Lemma 29.5, we argued that there are at most $\binom{m + n}{n}$ ways to choose a set $B$ of basic variables. Give an example of a linear program in which there are strictly fewer than $\binom{m + n}{n}$ ways to choose the set $B$.

Consider the simple program

$$ \begin{array}{rcrcrl} z & = & & - & x_1 \\ x_2 & = & 1 & - & x_1 & . \end{array} $$

In this case, we have $m = n = 1$, so $\binom{m + n}{n} = \binom{2}{1} = 2$, however, since the only coefficients of the objective function are negative, we can't make any other choices for basic variable. We must immediately terminate with the basic solution $(x_1, x_2) = (0, 1)$, which is optimal.