Efficiency of the Simplex Method
Exercise 4.1
Table 8 Pivots
Largest-Coefficient Rule |
Smallest-Index Rule |
|---|
\(x_2 \leftrightarrow w_3\) |
\(x_1 \leftrightarrow w_2\) |
\(x_1 \leftrightarrow w_1\) |
\(x_2 \leftrightarrow w_1\) |
|
\(w_2 \leftrightarrow w_3\) |
Exercise 4.2
Table 9 Pivots
Largest-Coefficient Rule |
Smallest-Index Rule |
|---|
\(x_1 \leftrightarrow w_1\) |
\(x_1 \leftrightarrow w_1\) |
\(x_2 \leftrightarrow x_1\) |
\(x_2 \leftrightarrow x_1\) |
Exercise 4.3
Table 10 Pivots
Largest-Coefficient Rule |
Smallest-Index Rule |
|---|
\(x_2 \leftrightarrow w_3\) |
\(x_1 \leftrightarrow w_2\) |
\(x_1 \leftrightarrow w_1\) |
\(x_2 \leftrightarrow w_1\) |
\(w_3 \leftrightarrow w_2\) |
|
Exercise 4.4
\[\begin{split}\begin{aligned}
\text{maximize} \quad
\zeta &= 100 x_1 + 10 x_2 + x_3\\
\text{subject to} \quad
w_1 &= 1 - x_1\\
w_2 &= 100 - 20 x_1 - x_2\\
w_3 &= 10000 - 200 x_1 - 20 x_2 - 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 = 1, \quad
w_2 = 100, \quad
w_3 = 10000.\]
Choose \(x_3\) and \(w_3\) as the entering and leaving variable
respectively where
\[x_3 = \min\left\{ w_3 \right\}_{\geq 0}
= \min\left\{ 10000 \right\}_{\geq 0}.\]
Update the current dictionary’s feasible solution to
\[x_1 = 0, \quad
x_2 = 0, \quad
x_3 = 10000, \quad
w_1 = 1, \quad
w_2 = 100, \quad
w_3 = 0.\]
Pivot dictionary to
\[\begin{split}\begin{aligned}
\text{maximize} \quad
\zeta &= 10000 - 100 x_1 - 10 x_2 - w_3\\
\text{subject to} \quad
w_1 &= 1 - x_1\\
w_2 &= 100 - 20 x_1 - x_2\\
x_3 &= 10000 - 200 x_1 - 20 x_2 - w_3\\
x_i &\geq 0 \quad i = 1, 2, 3\\
w_i &\geq 0 \quad i = 1, 2, 3
\end{aligned}\end{split}\]
Exercise 4.5
\[\begin{split}\begin{aligned}
\text{maximize} \quad
\zeta &= -4 b_1 - 2 b_2 - b_3 + 8 x_1 + 4 x_2 + 2 x_3 + x_4\\
\text{subject to} \quad
w_1 &= b_1 - x_1\\
w_2 &= 2 b_1 + b_2 - 4 x_1 - x_2\\
w_3 &= 4 b_1 + 2 b_2 + b_3 - 8 x_1 - 4 x_2 - x_3\\
w_4 &= 8 b_1 + 4 b_2 + 2 b_3 + b_4 - 16 x_1 - 8 x_2 - 4 x_3 - x_4\\
x_i &\geq 0 \quad i = 1, 2, 3, 4\\
w_i &\geq 0 \quad i = 1, 2, 3, 4
\end{aligned}\end{split}\]
\[\begin{split}x_1 &\leftrightarrow w_1\\
x_2 &\leftrightarrow w_2\\
w_1 &\leftrightarrow x_1\\
x_3 &\leftrightarrow w_3\\
x_1 &\leftrightarrow w_1\\
w_2 &\leftrightarrow x_2\\
w_1 &\leftrightarrow x_1\\
x_4 &\leftrightarrow w_4\\
x_1 &\leftrightarrow w_1\\
x_2 &\leftrightarrow w_2\\
w_1 &\leftrightarrow x_1\\
w_3 &\leftrightarrow x_3\\
x_1 &\leftrightarrow w_1\\
w_2 &\leftrightarrow x_2\\
w_1 &\leftrightarrow x_1\\\end{split}\]
Exercise 4.6
Since \(w_{i < k}\) do not contain \(x_k\), pivoting
\(x_k \leftrightarrow w_k\) will only affect \(x_k\), \(w_k\),
\(\zeta\), and \(w_{k < i \leq n}\):
\[\begin{split}x_k &= \sum_{j = 1}^{k - 1} \epsilon_k \epsilon_j 10^{k - j} (b_j - 2 x_j) +
(b_k - w_k)
= \sum_{j = 1}^{k - 1} \epsilon'_k \epsilon'_j 10^{k - j} (b_j - 2 x_j) +
(b_k - w_k)\\
\\
w_{i < k} &=
\sum_{j = 1}^{i - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j) +
(b_k - x_i)
= \sum_{j = 1}^{i - 1} \epsilon'_i \epsilon'_j 10^{i - j} (b_j - 2 x_j) +
(b_k - x_i)\end{split}\]
\[\begin{split}\zeta &= -\sum_{j = 1}^n \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right)\\
&= -\epsilon_k 10^{n - k} \left( \frac{1}{2} b_k - x_k \right) -
\sum_{j = 1}^{k - 1} \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right) -
\sum_{j = k + 1}^n \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right)\\
&= -\epsilon_k 10^{n - k} \frac{1}{2} b_k + \epsilon_k 10^{n - k}
\left[
\sum_{j = 1}^{k - 1} \epsilon_k \epsilon_j 10^{k - j} (b_j - 2 x_j) +
(b_k - w_k)
\right] -
\sum_{j = 1}^{k - 1} \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right) -
\sum_{j = k + 1}^n \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right)\\
&= -\epsilon_k 10^{n - k} \frac{1}{2} b_k +
\epsilon_k 10^{n - k} (b_k - w_k) +
\sum_{j = 1}^{k - 1} \epsilon_j 10^{n - j} (b_j - 2 x_j) -
\sum_{j = 1}^{k - 1} \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right) -
\sum_{j = k + 1}^n \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right)
& \quad & \text{since}\ \epsilon_k^2 = 1\\
&= \left[
\sum_{j = 1}^{k - 1} \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right)
\right] +
\epsilon_k 10^{n - k} \left( \frac{1}{2} b_k - w_k \right) -
\sum_{j = k + 1}^n \epsilon_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right)\\
&= -\epsilon'_k 10^{n - k} \left( \frac{1}{2} b_k - w_k \right) -
\sum_{j = 1, j \neq k}^n \epsilon'_j 10^{n - j}
\left( \frac{1}{2} b_j - x_j \right)\end{split}\]
\[\begin{split}w_{i > k} &=
\sum_{j = 1}^{i - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j) +
(b_k - x_i)\\
&= (b_k - x_i) +
\epsilon_i \epsilon_k 10^{i - k} (b_k - 2 x_k) +
\sum_{j = 1}^{k - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j) +
\sum_{j = k + 1}^{i - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j)\\
&= (b_k - x_i) +
\epsilon_i \epsilon_k 10^{i - k} b_k -
2 \epsilon_i \epsilon_k 10^{i - k} \left[
(b_k - w_k) +
\sum_{j = 1}^{k - 1} \epsilon_k \epsilon_j 10^{k - j} (b_j - 2 x_j)
\right] +
\sum_{j = 1}^{k - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j) +
\sum_{j = k + 1}^{i - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j)\\
&= (b_k - x_i) -
\epsilon_i \epsilon_k 10^{i - k} (b_k - 2 w_k) -
2 \sum_{j = 1}^{k - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j) +
\sum_{j = 1}^{k - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j) +
\sum_{j = k + 1}^{i - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j)
& \quad & \text{since}\ \epsilon_k^2 = 1\\
&= \left[
-\sum_{j = 1}^{k - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j)
\right] -
\epsilon_i \epsilon_k 10^{i - k} (b_k - 2 w_k) +
\left[
\sum_{j = k + 1}^{i - 1} \epsilon_i \epsilon_j 10^{i - j} (b_j - 2 x_j)
\right] + (b_k - x_i)\\
&= \epsilon'_i \epsilon'_k 10^{i - k} (b_k - 2 w_k) +
\sum_{j = 1, j \neq k}^{i - 1}
\epsilon'_i \epsilon'_j 10^{i - j} (b_j - 2 x_j) +
(b_k - x_i)\end{split}\]
where \(\epsilon'_{i < k} = -\epsilon_{i < k}\),
\(\epsilon'_k = -\epsilon_k\), and
\(\epsilon'_{i > k} = \epsilon_{i > k}\).
Exercise 4.7
Let \(\epsilon_i^t\) denote the relationship between the
\(\epsilon_i\)’s before and after each pivot. Evidently,
\(\epsilon_i^{t = 0} = 1\) for all \(1 \leq i \leq n\).
As shown in Exercise 4.6, pivoting between
\(x_k\) and \(w_k\) results in a dictionary that is of the same form as
before. The only significant differences are the sign changes of
\(\epsilon_i\)’s:
\[\begin{split}\epsilon_i^{t + 1} =
\begin{cases}
-\epsilon_i^t & \text{if}\ i \leq k\\
\epsilon_i^t & \text{otherwise.}
\end{cases}\end{split}\]
Observe that applying the simplex method’s largest-coefficient rule in this case
is equivalent to picking the first positive \(\epsilon_k^t\) where \(k\)
is the smallest subscript over the ordered sequence
\(\left[ \epsilon_1^t, \epsilon_2^t, \ldots, \epsilon_n^t \right]\).
Let \(T(n)\) denote the number of iterations (i.e. pivots) needed before
selecting the variable associated with \(\epsilon_{n + 1}\) as the entering
variable for the first time.
From the initial conditions, obviously \(T(0) = 1\). Now that
\(\epsilon_1^{t = 1}\) is negative, \(\epsilon_2^{t = 1}\) is chosen
as the next entering variable. Pivoting will make \(\epsilon_1^{t = 2}\)
eligible as an entering variable again, which means the same sequence of pivots
\(T(0)\) needs to occur before \(\epsilon_3\) can even be considered as
the next entering variable. Thus, \(T(1) = 1 + T(0) = 2\). This process
generalizes to the following geometric series
\[T(n) = 1 + \sum_{i = 0}^{n - 1} T(i) = 1 + 2 + 4 + 8 + \cdots
= a \frac{1 - r^n}{1 - r}\]
where \(a = 1\) and \(r = 2\). Therefore, the Klee-Minty problem
requires \(2^n - 1\) iterations.
Exercise 4.8
Rewriting the Klee-Minty problem with \(b_i = \beta^{i - 1}\) where
\(\beta > 1\) yields
\[\sum_{j = 1}^{i - 1} 10^{i - j} b_j + b_i =
\sum_{j = 1}^{i - 1} 10^{i - j} \beta^{j - 1} + \beta^{i - 1}\]
and
\[\begin{split}\begin{array}{*{5}{@{}c@{}}}
0 & \leq & x_1 & \leq & 1\\
0 & \leq & x_2 & \leq & 10 + \beta\\
0 & \leq & x_3 & \leq & 10^2 + 10 \beta + \beta^2\\
0 & \leq & x_4 & \leq & 10^3 + 10^2 \beta + 10 \beta^2 + \beta^3\\
& & \vdots & &\\
0 & \leq & x_n & \leq &
\sum_{j = 1}^{n - 1} 10^{n - j} \beta^{j - 1} + \beta^{n - 1}.
\end{array}\end{split}\]
In order to force the simplex method to proceed as in
Exercise 4.7, \(\beta\) needs to be chosen such that
the leaving variable’s subscript matches the entering variable’s subscript.
Suppose the entering variable’s index is \(e \in \mathcal{N}\) and let
\(l \in \mathcal{B}\) denote the leaving variable’s index. From the
definition of the Klee-Minty problem, \(l \geq e\). Out of the remaining
possible candidates, the minimum ratio test chooses one according to:
\[\frac{\hat{b}_l}{\hat{a}_{le}} =
\min\left\{
\frac{\hat{b}_i}{\hat{a}_{ie}}
\colon
i \in \mathcal{B},
\hat{b}_i \in
\left[
\beta^{i - 1} - \sum_{j = 1}^{i - 1} 10^{i - j} \beta^{j - 1},
\beta^{i - 1} + \sum_{j = 1}^{i - 1} 10^{i - j} \beta^{j - 1}
\right]_{\geq 0},
\hat{a}_{ie} =
\epsilon'_i \epsilon'_e \cdot 2^{1 - \delta_{i - e}} \cdot 10^{i - e} > 0
\right\}.\]
Observe that for \(l = k > e\) to be even feasible where \(k\)
represents another leaving variable, the intervals represented by
\(\frac{\hat{b}_e}{\hat{a}_{ee}}\) and
\(\frac{\hat{b}_k}{\hat{a}_{ke}}\) need to intersect. Since each
constraint’s upper bound (i.e. the right hand side of each inequality) grows
exponentially in terms of \(\beta\) and
each pivot only induces sign changes, if the
pair of intervals indexed by \(e = 1\) and \(l = n \neq e\) never
overlaps, no pair of intervals in between them will intersect. Therefore, the
infimum (a.k.a. greatest lower bound) satisfies
\[\begin{split}\frac{\hat{b}_e}{\hat{a}_{ee}} &< \frac{\hat{b}_l}{\hat{a}_{le}}\\
1 &< \frac{
\beta^{n - 1} - \sum_{j = 1}^{n - 1} 10^{n - j} \beta^{j - 1}
}{
2^{1 - \delta_{n - 1}} \cdot 10^{n - 1}
}\\
2 \cdot 10^{n - 1} &<
\beta^{n - 1} - \sum_{j = 1}^{n - 1} 10^{n - j} \beta^{j - 1}.\end{split}\]
Exercise 4.9
Recall that Stirling’s approximation is
\[n! \approx \left( \frac{n}{e} \right)^n \sqrt{2 \pi n}.\]
A crude estimate for the desired binomial coefficient is then
\[{2n \choose n} = \frac{(2n)!}{n! (2n - n)!} \approx
\frac{2^{2n} (n / e)^{2n} \cdot 2 \sqrt{\pi n}}{(n / e)^{2n} \cdot 2 \pi n} =
\frac{2^{2n}}{\sqrt{\pi n}}.\]
From inspection,
\[\frac{2^{2n}}{2n} \leq \frac{2^{2n}}{2 \sqrt{n}} \leq
{2n \choose n} \leq 2^{2n}\]
holds for any positive integer \(n\).
Exercise 4.10
Recall that a feasible solution satisfies all of the constraints. If that is
no longer a requirement, Exercise 2.15
has illustrated the desired dictionary can be arrived at in exactly
\(k\) pivots via the following process.
Pivot all the non-zero elements that have the matching indices first
i.e. \(x_i \leftrightarrow w_i\).
The remaining pivots are degenerate and require adopting the convention
of treating \(\frac{0}{0} = 0\).