📂Optimization

Simplex Method's Bland's Rule

Theorem

A system of equations of the following form for Dictionary: $i = 1 , \cdots , m$ is called a Dictionary. $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$ Variables on the left side of $\zeta$, excluding the one variable, are called basic variables, and variables on the right side are called nonbasic variables. Their indices are denoted as follows. $$ \begin{align*} \mathcal{B} :=& \left\{ n+1 , n+2 , \cdots , n+m \right\} \\ \mathcal{N} :=& \left\{ 1 , 2 , \cdots , n \right\} \end{align*} $$

In the Simplex Method of Linear Programming, selecting the index of the entering variable as the smallest one from $\mathcal{N}$, and selecting the index of the leaving variable as the smallest one from $\mathcal{B}$ is called Brand’s Rule. According to Brand’s Rule, the simplex method does not fall into a cycle.

Explanation

Although there are other methods to solve a linear programming problem besides the Simplex Method, and there is not only one pivot rule for updating the dictionary in the simplex method, the existence of Brand’s Rule guarantees that the simplex method can always solve linear programming problems. Understanding this theorem means that you can consider mastering the two most important concepts in linear programming, including the simplex method itself.

Proof ¹

Strategy: It’s not easy. It will be shown that it is a contradiction to fall into a cycle when pivoting with Brand’s rule.

---

Part 1. $\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}$

Without loss of generality, let’s start the proof from the point where cycling occurs. For some $k \in \mathbb{N}$, the dictionary cycles as follows. $$ D_{0} , D_{1} , \cdots, D_{k-1} , D_{0} , D_{1} , \cdots $$ In this dictionary, variables that are basic in some and nonbasic in others are called fickle. Let the fickle with the largest index be $x_{t}$, and when the dictionary that has $x_{t}$ as the leaving variable is $D$, without loss of generality let it be so that $D$ can be written with respect to $\forall i \in \mathcal{B}$ as follows. $$ \begin{align*} \zeta &=& v &+& \sum_{j \in \mathcal{N}} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j \in \mathcal{N}} a_{ij} x_{j} \end{align*} $$ Here, if $x_{s}$ is the entering variable, then $x_{t}$ is the leaving one, and still $t \in \mathcal{B}$ and $s \in \mathcal{N}$. Now let $D^{\ast}$ be the dictionary where $x_{t}$ enters the basis, and suppose it can be written with respect to $\forall i \in \mathcal{B}^{\ast}$ as follows. $$ \begin{align*} \zeta &=& v^{\ast} &+& \sum_{j \in \mathcal{N}^{\ast}} c_{j}^{\ast} x_{j} \\ x_{n+i} &=& b_{i}^{\ast} &-& \sum_{j \in \mathcal{N}^{\ast}} a_{ij}^{\ast} x_{j} \end{align*} $$ The fact that the simplex method has fallen into a cycle means that all $D_{1} , \cdots, D_{k-1}$ are degenerated, and because of $v^{\ast} = v$, for the objective function $\zeta$, by setting it as $c_{j}^{\ast} = 0$ for $j \in \mathcal{B}^{\ast}$, it can be written as follows. $$ \zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j} $$

---

Part 2. $\zeta = v + c_{s} y$

As in the form of the equation, let’s consider the situation where the entering variable $x_{s}$ increases and the other variables in $\mathcal{N}$ are fixed at $0$, so that no variable becomes negative. In terms of equations, it’s $$ \begin{align*} x_{s} =& y \\ x_{j} =& 0 & , j \in \mathcal{N} \setminus \left\{ s \right\} \\ x_{i} =& b_{i} - a_{is} y & , i \in \mathcal{B} \end{align*} $$ and this is about increasing $y$. By rewriting the objective function $\zeta$ with respect to this, the following can be obtained. $$ \zeta = v + c_{s} y $$

---

Part 3.

Rewriting Part 1’s $\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}$ with respect to $y$, $$ \zeta = v + c_{s}^{\ast} y + \sum_{i \in \mathcal{B}} c_{i}^{\ast} \left( b_{i} - a_{is} y \right) $$ and substituting the left side for part 2’s $\zeta = v + c_{s} y$, gives $$ \left( c_{s} - c_{s}^{\ast} + \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} \right) y = \sum_{i \in \mathcal{B}} c_{i}^{\ast} b_{i} $$ This equation always holds for all $y$, regardless of what’s on the right side, so from this, it’s understood that what’s inside the parenthesis is always $0$. $$ \begin{equation} c_{s} - c_{s}^{\ast} + \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} = 0 \end{equation} $$ In other words, if the entering variable is $x_{s}$, $$ \begin{equation} c_{s} > 0 \end{equation} $$ Moreover, since $x_{t}$ is the fickle with the largest index and $x_{s}$ was also a fickle, $s < t$ follows. Since the entering variable for $D^{\ast}$ was $x_{t}$, $x_{s}$ is not an entering variable, $$ \begin{equation} c_{s}^{\ast} \le 0 \end{equation} $$

According to $(1), (2), (3)$, $$ \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} < 0 $$ and there must exist a $r \in \mathcal{B}$ that satisfies the following. $$ c_{r}^{\ast} a_{rs} < 0 $$ As a result, $c_{r}^{\ast} \ne 0$ and $r \in \mathcal{N}^{\ast}$, thus $x_{r}$ is a fickle and $r \le t$ follows.

---

Part 4. $r < t$

Since we are considering the simplex method, we can say two things:

• Since $x_{t}$ is the entering variable for $D^{\ast}$, $c_{t}^{\ast} > 0$ follows.
• Since $x_{t}$ is the leaving variable for $D$, $a_{ts} > 0$ follows.

Therefore, $c_{t}^{\ast} a_{ts} > 0$, but since $c_{r}^{\ast} a_{rs} < 0$, $r \ne t$, that is, up to $r < t$ can be asserted.

---

Part 5.

If it’s $r < t$, then it must be $c_{r}^{\ast} \le 0$, because if it wasn’t and was $c_{r}^{\ast} > 0$ instead, then according to Part 3, $r$ must have been the entering variable for $D^{\ast}$. According to this and Part 3’s $c_{r}^{\ast} a_{rs} < 0$, $$ \begin{equation} a_{rs} > 0 \end{equation} $$ On the other hand, that dictionaries have fallen into a cycle means that they all essentially represent the same solution, hence all fickle variables are $0$ in that dictionary, and especially $x_{r} = 0$. However, since $x_{r}$ is a basic variable in $D$, $$ \begin{equation} b_{r} = 0 \end{equation} $$ Following $(4)$ and $(5)$, $x_{r}$ is one of the candidates for the leaving variable in $D$, and since it is $r < t$ according to Part 4, following Brand’s rule, it should have been selected (left) instead of $x_{t}$ much earlier. This contradiction reveals that the assumption that the dictionary has fallen into a cycle even when using Brand’s rule is false.

■

See Also

Fundamental Theorem of Linear Programming

This theorem is used in the proof of the fundamental theorem of linear programming.