| Prev | Next | Top | Bland |
\newcommand{\notin}{
\mathml{ <mi mathvariant='normal'> &\#x02209; </mi> }
}
\[
\begin{array}{rcl}
{\rm maximize} &
z = v^k + \sum_{j=1}^n c_j^k x_j &
{\rm w.r.t} \; x \in \R_+^n
\\
{\rm subject \; to} &
\sum_{j=1}^n A_{i,j}^k x_j = b_i^k &
{\rm for} \; i = 1 , \ldots , m
\end{array}
\]
These representations are such that
a pair
x \in R^n
,
z \in \R
satisfies
the equations above for one value of
k
if and only if
it satisfies the equations for all values of
k
.
D^k : \{ 1 , \ldots , m \} \rightarrow \{ 1 , \ldots , n \}
to denote the basis function corresponding to the k-th iteration
of the simplex algorithm; i.e.,
D^k (i)
is the
basis variable index corresponding to row
i
in the equations above.
We use
B^k
to denote the range of
D^k
; i.e.
\[
B^k = \left. \left\{ D^k (i) \; \right| \; i = 1 , \ldots , m \right\}
\]
Using this notation,
the equations in the k-th iteration of the
simplex algorithm can be written as
\[
\begin{array}{rcl}
x_{D^k (i)} & = & b^k_i - \sum_{j \notin B^k} A^k_{i,j} x_j
\hspace{1cm}
(i = 1 , \ldots , m)
\\
z & = & v^k + \sum_{j \notin B^k} c^k_j x_j
\end{array}
\]
B^1
is equal to
B^k
,
v^1 = v^k
.
x \in \R^n
is the basic solution
corresponding to
D^1
; i.e.
\[
x_j = \left\{ \begin{array}{ll}
0 & {\rm if} \; j \notin B^1
\\
b_i & {\rm if} \; j = D^1 (i) \; {\rm for \; some} \;
i \in \{1 , \ldots , m \}
\end{array} \right.
\]
It follows that
\[
\begin{array}{rcl}
z = v^1 + \sum_{j \notin B^1} c^1_j x_j
& {\rm and} &
v^k + \sum_{j \notin B^k} c^k_j x_j = z
\\
v^1 + \sum_{j \notin B^1} c^1_j x_j
& = &
v^k + \sum_{j \notin B^1} c^k_j x_j
\\
v^1 & = & v^k
\end{array}
\]
k
,
choose the index of the variable to enter the basis
E(k)
using the minimum index
\[
E(k) = \min \left[
\left. \left\{ j \; \right| \;
j \notin B^k \; {\rm and} \; c^k_j > 0
\right\}
\right]
\]
We note that
E(k) \notin B^k
and
E(k) \in B^{k+1}
.
We also note that if the set for this minimum is empty,
the current basic solution is optimal.
k
,
define the minimum ratio
R(k)
by
\[
R(k) = \min \left[
\left\{ b_i / A^k_{i, E(k)} \; \left| \;
i \in \{ 1 , \ldots , m \} \; {\rm and} \;
A^k_{i, E(k)} > 0
\right. \right\} \right]
\]
We note that if the set for this minimum is empty,
the problem is unbounded.
k
,
choose the index of the variable to leave the basis
L(k)
using the minimum index
\[
L(k) = \min \left[
\left\{ D^k (i) \; \left| \;
i \in \{ 1 , \ldots , m \} \; {\rm and} \;
A^k_{i, E(k)} > 0 \; {\rm and} \;
b_i / A^k_{i, E(k)} = R(k)
\right. \right\} \right]
\]
We note that
L(k) \in B^k
and
L(k) \notin B^{k+1}
.
B^k
to be the same as
B^{k+\ell}
for some positive integer
\ell
.
B^k
from the basis
function
D^k
.
\ell
; i.e.,
B^1
is the same as
B^\ell
.
We will prove the theorem by showing that this leads to a contradiction.
B^1
is equal to the set
B^\ell
(by assumption). Hence the set of variables that
leave a basis during iterations 1 through
\ell
must be the
same as the set of those that enter a basis during those iterations; i.e.,
the following two sets of variable indices are equal
\[
\{ L(k) : k = 1 , \ldots , \ell \}
=
\{ E(k) : k = 1 , \ldots , \ell \}
\]
We refer to this as the set of fickle indices.
p
as the one
in with the leaving index is the maximum value for the set
fickle indices; i.e.,
\[
\begin{array}{rcl}
L(p) & = & \max \{ L(k) : k = 1 , \ldots , \ell \}
\\
& = & \max \{ E(k) : k = 1 , \ldots , \ell \}
\end{array}
\]
L
that
L(p) \in B^p
and
L(p) \notin B^{p+1}
.
Thus there is an iteration
q
such that
L(p) = E(q)
; i.e.,
L(p) \notin B^q
and
L(p) \in B^{q+1}
.
X : \R \rightarrow \R^n
by
\[
X_j ( \lambda ) = \left\{ \begin{array}{ll}
\lambda
& {\rm if} \; j \notin B^p \; {\rm and} \; j = E(p)
\\
0
& {\rm if} \; j \notin B^p \; {\rm and} \; j \neq E(p)
\\
b_i^p - A^p_{i , E(p)} \lambda
& {\rm if} \; j = D^p (i) \; {\rm for \; some} \; i
\end{array} \right.
\]
It follows that for
i = 1 , \ldots m
,
\[
X_{D^p (i)} ( \lambda )
=
b_i^p - A^p_{i , E(p)} \lambda
=
b^p_i - \sum_{j \notin B^p} A^p_{i,j} X_j ( \lambda )
\]
X
that,
for all
\lambda \in \R
,
the vector
X( \lambda ) \in \R^n
satisfies
the constraint equations (excluding the one with
z
in it).
We therefore conclude that for all
\lambda \in \R
,
\[
v^p + \sum_{j \notin B^p} c^p_j X_j ( \lambda )
=
z
=
v^q + \sum_{j \notin B^q} c^q_j X_j ( \lambda )
\]
The basic solution at iteration
k
is defined
\[
x_j = \left\{ \begin{array}{ll}
0 & {\rm if} \; j \notin B^k
\\
b_i & {\rm if} \; j = D^k (i) \; {\rm for \; some} \;
i \in \{1 , \ldots , m \}
\end{array} \right.
\]
The objective function value corresponding to this solution is
z = v^k
.
In addition, the simplex algorithm ensures that
v^{k+1} \geq v^k
.
On the other hand, the fact that
B^1 = B^\ell
ensures
that
v^1 = v^\ell
(see the lemma
above).
It follows that
v^1 = v^k
for all
k
and hence
\[
\sum_{j \notin B^p} c^p_j X_j ( \lambda )
=
\sum_{j \notin B^q} c^q_j X_j ( \lambda )
\]
X_j ( \lambda )
is a non-zero component of
X( \lambda )
,
either
j \in B^p
or
j = E(p)
.
Thus we have
\[
\begin{array}{rcl}
c^p_{E(p)} X_{E(p)} ( \lambda )
& = &
c^q_{E(p)} X_{E(p)} ( \lambda )
+
\sum_{j \in B^p} c^q_j X_j ( \lambda )
\\
c^p_{E(p)} \lambda
& = &
c^q_{E(p)} \lambda
+
\sum_{i = 1}^m c^q_{D^p (i)} ( b_i^p - A^p_{i , E(p)} \lambda )
\\
\sum_{i = 1}^m c^q_{D^p (i)} b_i^p
& = &
\left(
c^p_{E(p)}
-
c^q_{E(p)}
+
\sum_{i = 1}^m c^q_{D^p (i)} A^p_{i , E(p)}
\right) \lambda
\end{array}
\]
This equation holds for all
\lambda \in \R
, hence
\[
c^p_{E(p)} - c^q_{E(p)}
+
\sum_{i = 1}^m c^q_{D^p (i)} A^p_{i , E(p)}
=
0
\]
c^p_{E(p)} > 0
(see definition of
E(k)
).
We choose the iteration
q
so that
L(p) = E(q)
(see Choose q
).
The choice of iteration
p
ensures that
E(p) < L(p)
(see Choose p
).
Thus
E(p) < E(q) = L(p)
and hence,
from the definition of
E
,
c^q_{E(p)} \leq 0
.
It now follows from the equation above that
the is an index
i
with
\[
c^q_{D^p (i)} A^p_{i , E(p)} < 0 \hspace{1cm}(*)
\]
It follows that
c^q_{D^p (i)} \neq 0
.
Hence,
D^p (i) \in B^p
and
D^p (i) \notin B^q
.
Thus
D^p (i)
is a
fickle
index and
D^p (i) \leq L(p)
(see definition of Choose p
).
Thus we only have the two possible cases below:
D^p (i) = L(p) = E(q)
.
It follows that
c^q_{D^p(i)} > 0
because
D^p (i) = E(q)
.
Furthermore
A^p_{i , E(p)} > 0
because
D^p (i) = L(p)
.
\[
c^q_{D^p (i)} A^p_{i , E(p)} > 0
\]
which contradicts the equation
(*)
above.
D^p (i) < L(p) = E(q)
.
It follows that
c^q_{D^p(i)} \leq 0
because
D^p (i) < E(q)
.
It follows from equation
(*)
above that
\[
A^p_{i , E(p)} > 0
\]
In this case we would have picked
D^p (i)
to leave the
basis
B^p
and this contradicts the definition of
Choose p
.