For the sake of notation, we denote the initial tableau:
|
\(x_1\) |
\(x_2\) |
\(\cdots\) |
\(x_m\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(\cdots\) |
\(a_{1m}\) |
\(b_1\) |
\(=-x_{m+1}\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(\cdots\) |
\(a_{2m}\) |
\(b_2\) |
\(=-x_{m+2}\) |
|
\(\vdots\) |
\(\vdots\) |
\(\ddots\) |
\(\vdots\) |
\(\vdots\) |
\(\vdots\) |
|
\(a_{n1}\) |
\(a_{n2}\) |
\(\cdots\) |
\(a_{nm}\) |
\(b_n\) |
\(=-x_{m+n}\) |
|
\(c_1\) |
\(c_2\) |
\(\cdots\) |
\(c_m\) |
\(d\) |
\(=f\) |
and order the variables in the associated way. Suppose we follow Bland’s rules and still have cycling. That is, there is a sequence of pivots and bases (set of basic variables)
\(B_1\to B_2\to \cdots B_\ell \to B_1\text{.}\) We call a variable
\(x_j\) fickle if
\(x_j\) is in one, but not all of the bases. That is, it leaves a basis, and reenters it later during the cycle.
Note that in order for cycling to occur, each pivot must be degenerate (ask yourself why?). So if
\(x_j\) is fickle,
\(x_j=0\) for each basic solution during the cycle.
Since the number of variables is finite, the set of fickle variables is also finite, and let
\(x_t\) denote the fickle variable with largest subscript. Suppose that
\(x_t \in B_i, x_t\not\in B_{i+1}\) (why must such a
\(B_i\) exist?). Denote the entering variable from
\(B_i\to B_{i+1}\) with
\(x_s\text{.}\)
|
\(\cdots\) |
\(x_s\) |
\(\cdots\) |
\(-1\) |
|
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\vdots\) |
\(a_{ts}\) |
\(\vdots\) |
\(0\) |
\(=-x_{t}\) |
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\cdots\) |
\(c_s\) |
\(\cdots\) |
\(d\) |
\(=f\) |
|
\(\cdots\) |
\(x_t\) |
\(\cdots\) |
\(-1\) |
|
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\vdots\) |
\(?\) |
\(\vdots\) |
\(0\) |
\(=-x_{s}\) |
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\cdots\) |
\(?\) |
\(\cdots\) |
\(d\) |
\(=f\) |
Note that
\(x_s\) must also be fickle (why?) and so
\(s\lt t\text{.}\)
We call the dictionary for a basis the system of equations corresponding to that basis. So the dictionary for \(B_i\) is \(D_i\) which we can write with constraint equalities:
\begin{equation*}
x_k = b_k - \displaystyle\sum_{x_j\not\in B_i} a_{kj}x_j\text{ for }k\in B_i
\end{equation*}
and objective function equality:
\begin{equation*}
f = \displaystyle\sum_{x_j\not\in B_i} c_{j}x_j -d.
\end{equation*}
Note that since the above pivot was valid, we must have that \(c_s>0, a_{ts}>0\) and since the pivot was degenerate, we have \(b_t=0\text{.}\)
Now, because we have cycling, we must have that
\(x_t\) reenters the basis at some point:
|
\(\cdots\) |
\(x_t\) |
\(\cdots\) |
\(-1\) |
|
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\vdots\) |
\(?\) |
\(\vdots\) |
\(0\) |
\(=-x_{?}\) |
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\cdots\) |
\(c_t^*\) |
\(\cdots\) |
\(d\) |
\(=f\) |
|
\(\cdots\) |
\(x_?\) |
\(\cdots\) |
\(-1\) |
|
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\vdots\) |
\(?\) |
\(\vdots\) |
\(0\) |
\(=-x_{t}\) |
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\cdots\) |
\(?\) |
\(\cdots\) |
\(d\) |
\(=f\) |
Note that for this pivot to be valid, we must have that \(c_t^*>0\text{.}\) If we let \(D_\ell\) denote the dictionary before \(x_t\) re-enters the basis, we have:
\begin{equation*}
f = \displaystyle\sum_{x_j\not\in B_\ell} c_{j}^*x_j -d
\end{equation*}
So note that the solution space to the system of equations for both these dictionaries are the same. So we have a solution for \(D_i\) (not necessarily feasible ie nonnegativity may fail) that must also be a solution to \(D_\ell\text{:}\)
\begin{align*}
x_s \amp = Z \\
x_j \amp = 0\text{ for }x_j\not\in B_i, x_j\neq x_s \\
x_k \amp = b_k-a_{ks}Z \text{ for }x_k\in B_i\\
f \amp = c_sZ-d.
\end{align*}
So we have
\begin{equation*}
c_sZ-d =f =c_s^*Z-d+\displaystyle\sum_{x_k\in B_i} c_{k}^*(b_k-a_{ks}Z)
\end{equation*}
where \(c_k^*=0\) for \(x_k\in B_\ell\text{.}\) So via algebra:
\begin{equation*}
\left( c_s-c_s^* + \displaystyle\sum_{x_k\in B_i} c_{k}^*a_{ks} \right)Z = \displaystyle\sum_{x_k\in B_i} c_{k}^*b_k.
\end{equation*}
The above equation holds true no matter what \(Z\) is. Thus:
\begin{equation*}
c_s-c_s^* + \displaystyle\sum_{x_k\in B_i} c_{k}^*a_{ks}=0.
\end{equation*}
Note that \(x_t\text{,}\) NOT \(x_s\) is entering the basis. If \(x_s\) is already in the basis, \(c_s^*=0\text{.}\) Otherwise, \(c_s^*\leq0\text{,}\) otherwise \(s\) would have entered by Bland’s Anticyling rules. We’ve also shown \(c_s>0\text{.}\) Thus
\begin{equation*}
\displaystyle\sum_{x_k\in B_i} c_{k}^*a_{ks} \lt 0
\end{equation*}
which is only possible if there is some \(x_r\in B_i\) such that
\begin{equation*}
c_r^*a_{rs}\lt 0.
\end{equation*}
From this, we know that
\(c_r^*\neq 0\text{.}\) So
\(x_r\not\in B_\ell\text{,}\) but
\(x_r\in B_i\text{,}\) so
\(x_r\) is fickle. Since
\(t\) is the largest index of a fickle variable,
\(r\lt t\text{.}\) Note that
\(x_r\) is not entering from
\(B_\ell\text{,}\) so
\(c_r^*\leq 0\text{.}\) Thus
\(a_{rs}>0\text{.}\)
But
\(x_r\) is fickle, so
\(b_r=0\) in
\(D_i\text{.}\) But then, we would have picked
\(x_r\text{,}\) not
\(x_t\) to leave.
|
\(\cdots\) |
\(x_s\) |
\(\cdots\) |
\(-1\) |
|
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\vdots\) |
\(a_{ts}\) |
\(\vdots\) |
\(0\) |
\(=-x_{t}\) |
|
\(\vdots\) |
\(a_{rs}\) |
\(\vdots\) |
\(0\) |
\(=-x_{r}\) |
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
|
|
\(\cdots\) |
\(c_s\) |
\(\cdots\) |
\(d\) |
\(=f\) |
which is a contradiction.
