Simplex tableau

Consider the following linear programming problem: $$\begin{array}{rrcrcrcrcr}min& x_1& +& 2x_2& & & -& 2x_4& -& x_5\\ (P)\text{s.t.}& x_1& -& x_2& +& x_3& & & +& 2x_5& =& 1\\ & x_1& +& x_2& +& 2x_3& -& 2x_4& +& 2x_5& =& 3\\ & x_1& ,& x_2& ,& x_3& ,& x_4& ,& x_5& \ge & 0.\end{array}$$

Is the basic feasible solution ${\mathbf{x}}^{\ast }=\left[\begin{array}{c}2\\ 1\\ 0\\ 0\\ 0\end{array}\right]$ determined by the basis $B=\{1,2\}$ an optimal solution to $(P)$?

Let us see if complementary slackness will help us answer this question. The dual of $(P)$ is $$\begin{array}{rrcr}max& y_1& +& 3y_2\\ (D)\text{s.t.}& y_1& +& y_2& \le & 1\\ & -y_1& +& y_2& \le & 2\\ & y_1& +& 2y_2& \le & 0\\ & & & -2y_2& \le & -2\\ & 2y_1& +& 2y_2& \le & -1.\end{array}$$ Then ${\mathbf{x}}^{\ast }$ is optimal if and only if there exists ${\mathbf{y}}^{\ast }$ feasible to $(D)$ satisfying the complementary slackness conditions with ${\mathbf{x}}^{\ast }$. As the first two components of ${\mathbf{x}}^{\ast }$ are positive, such a ${\mathbf{y}}^{\ast }$ must satisfy $$\begin{array}{r}{y}_1^{\ast }+y_2^{\ast }=1\\ -y_1^{\ast }+y_2^{\ast }=2\end{array}$$ Solving gives the unique solution $\left[\begin{array}{c}{y}_1^{\ast }\\ y_2^{\ast }\end{array}\right]=\left[\begin{array}{c}-\frac{1}{2}\\ \frac{3}{2}\end{array}\right]$. However, this is not a feasible solution to $(D)$. (It violates the third constraint, for example.) Hence, ${\mathbf{x}}^{\ast }$ is not an optimal solution.

The question we now ask is, “How do we search for a solution with a better objective function value using existing information?”

Note that solving $(P)$ is equivalent to finding a solution to the following system with the minimum $z$ value, if it exists: $$\begin{array}{rcrcrcccccccc}z& -& x_1& -& 2x_2& & & +& 2x_4& +& x_5& =& 0\\ & & x_1& -& x_2& +& x_3& & & +& 2x_5& =& 1\\ & & x_1& +& x_2& +& 2x_3& -& 2x_4& +& 2x_5& =& 3\\ & & x_1& ,& x_2& ,& x_3& ,& x_4& ,& x_5& \ge & 0.\end{array}$$ The first equation comes from setting $z$ to the objective function. If we now focus on the equations and perform elementary row operations to the system of equations to turn $z$, $x_1$, $x_2$ into pivot variables, we obtain the equivalent system $$\begin{array}{rcrcrcccccccc}z& & & & & +& \frac{5}{2}{x}_3& -& x_4& +& 3x_5& =& 4\\ & & x_1& & & +& \frac{3}{2}{x}_3& -& x_4& +& 2x_5& =& 2\\ & & & & x_2& +& \frac{1}{2}{x}_3& -& x_4& & & =& 1\end{array}$$ This system is called the simplex tableau (or simply tableau) associated with the basis $B=\{1,2\}$.

Note that we will refer to each equation in a tableau by its associated pivot variable. For the tableau above, the $z$-row refers to the equation $z+\frac{5}{2}{x}_3-x_4+3x_5=4$, the $x_1$-row refers to the equation $x_1+\frac{3}{2}{x}_3-x_4+2x_5=2$ and the $x_2$-row refers to the equation $x_2+\frac{1}{2}{x}_3-x_4=1$.

In general, for the LP problem $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ (P)\text{s.t.}& \mathbf{A}\mathbf{x}=\mathbf{b}\\ & \mathbf{x}\ge \mathbf{0}.\end{array}$$ where $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ has rank $m$, $\mathbf{b}\in {\mathbb{R}}^m$, $\mathbf{c}\in {\mathbb{R}}^n$, and $\mathbf{x}=\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right]$ is a tuple of variables, the simplex tableau associated with a basis $B$ is obtained from row reducing the system $$\begin{array}{rcl}z-{\mathbf{c}}^{\mathsf{T}}\mathbf{x}& =& 0\\ \mathbf{A}\mathbf{x}& =& \mathbf{b}\end{array}$$ using elementary row operations so that the pivot variables are $z$ and the basic variables. The tableau can be written in a compact form provided we use the following notation: For a subset $C$ of $\{1,\dots ,n\}$, let ${\mathbf{A}}_C$ be obtained from $\mathbf{A}$ by removing the columns not indexed by elements of $C$, let ${\mathbf{c}}_C$ be obtained from $\mathbf{c}$ by removing the components not indexed by elements of $C$, and let ${\mathbf{x}}_C$ be obtained from $\mathbf{x}$ by removing the components not indexed by elements of $C$. Then, if $N=\{1,\dots ,n\}\setminus B$, the tableau can be represented by $$\begin{array}{rcl}z-({\mathbf{c}}_N^{\mathsf{T}}-{\mathbf{y}}^{\mathsf{T}}{\mathbf{A}}_N){\mathbf{x}}_N& =& {\mathbf{y}}^{\mathsf{T}}\mathbf{b}\\ {\mathbf{x}}_B+{\mathbf{A}}_B^{-1}{\mathbf{A}}_N{\mathbf{x}}_N& =& {\mathbf{A}}_B^{-1}\mathbf{b}\end{array}$$ where ${\mathbf{y}}^{\mathsf{T}}={\mathbf{c}}_B^{\mathsf{T}}{\mathbf{A}}_B^{-1}$. Note that from the simplex tableau, one can easily read off from the right-hand side the values of the basic variables in the basic solution determined by $B$.

The equation containing the variable $z$ is called the $z$-row. For each $i\in B$, the equation in the tableau containing the pivot variable $x_i$ is called the $x_i$-row.

If $B$ happens to determine a basic feasible solution, then the tableau is said to be a feasible tableau.

Going back to the example, note that for any feasible solution $\mathbf{x}$, the first equation in the tableau shows that its objective function value is given by $4-\frac{5}{2}{x}_3+x_4-3x_5$. Hence, any feasible solution with $x_3=x_4=x_5=0$ will give $4$ for the $z$ value. But if we could find a feasible solution $\mathbf{x}$ with $x_4=0$, and $x_3>0$ or $x_5>0$, the $z$ value will be less than 4, thus giving a feasible solution with lower objective function value.

Now, if we choose to keep $x_4=x_5=0$, then $x_1,x_2,x_3$ must satisfy $$\begin{array}{rcrccllll}& & x_1& & & +& \frac{3}{2}{x}_3& =& 2\\ & & & & x_2& +& \frac{1}{2}{x}_3& =& 1,\end{array}$$ or equivalently $$\begin{array}{r}{x}_1=2-\frac{3}{2}{x}_3\\ x_2=1-\frac{1}{2}{x}_3.\end{array}$$ To obtain a feasible solution, we need $x_1,x_2\ge 0$. Therefore, to obtain the largest possible improvement in objective function value subject to the above constraints, we want $x_3$ to be as large as possible. The largest value for $x_3$ so that $x_1,x_2\ge 0$ is $\frac{4}{3}$. Setting $x_3=\frac{4}{3}$ gives us the solution $\left[\begin{array}{c}0\\ \frac{1}{3}\\ \frac{4}{3}\\ 0\\ 0\end{array}\right]$ with objective function value $\frac{2}{3}$. Note that this solution is a basic feasible solution determined by the basis $B=\{2,3\}$.

To obtain the tableau associated with $B=\{2,3\}$, we need to make $x_3$ a pivot variable and keep $z$ and $x_2$ as pivot variables. We can make use of the second equation to eliminate $x_3$ from the $z$-row and the last row to obtain: $$\begin{array}{rcrcrcccccccc}z& -& \frac{5}{3}{x}_1& & & & & +& \frac{2}{3}{x}_4& -& \frac{1}{3}{x}_5& =& \frac{2}{3}\\ & & \frac{2}{3}{x}_1& & & +& x_3& -& \frac{2}{3}{x}_4& +& \frac{4}{3}{x}_5& =& \frac{4}{3}\\ & & -\frac{1}{3}{x}_1& +& x_2& & & -& \frac{2}{3}{x}_4& -& \frac{2}{3}{x}_5& =& \frac{1}{3}\end{array}$$ As before, if we can increase $x_4$ while holding $x_1=x_5=0$, we can obtain a feasible solution with lower objective function value provided that: $$\begin{array}{rcl}{x}_3=\frac{4}{3}+\frac{2}{3}{x}_4& \ge & 0\\ x_2=\frac{1}{3}+\frac{2}{3}{x}_4& \ge & 0.\end{array}$$ But these inequalities are satisfied for all $x_4\ge 0$. Thus, $\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right]=\left[\begin{array}{c}0\\ \frac{1}{3}+\frac{2}{3}t\\ \frac{4}{3}+\frac{2}{3}t\\ t\\ 0\end{array}\right]$ is a feasible solution for all $t\ge 0$ with objective function value $\frac{2}{3}-\frac{2}{3}t\to -\mathrm{\infty }$ as $t\to \mathrm{\infty }$. Hence, the problem is unbounded.

Tableau method

Summarize the ideas illustrated above gives the tableau method for solving $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ (P)\text{s.t.}& \mathbf{A}\mathbf{x}=\mathbf{b}\\ & \mathbf{x}\ge \mathbf{0}.\end{array}$$ where $\mathbf{A}$ has full row rank.

Input: The problem $(P)$ and a basis $B$ determining a basic feasible solution.
Steps:

1. Obtain the tableau associated with $B$.

2. Let ${\mathbf{x}}^{\ast }\in {\mathbb{R}}^n$ be such that for each $i\in B$, $x_i^{\ast }$ equals ${\overline{b}}_i$, the right-hand side value of the $x_i$-row, and $x_i^{\ast }=0$ for each $i\notin B$. (That is, ${\mathbf{x}}^{\ast }$ is the basic feasible solution determined by $B$.)

3. Find an index $k$ such that $x_k$ is a nonbasic variable with a positive coefficient in the $z$-row. If no such $k$ exists, then stop; ${\mathbf{x}}^{\ast }$ is an optimal solution.

4. For each $i\in B$, let ${\overline{a}}_{ik}$ denote the coefficient of $x_k$ in the $x_i$-row. Let $R=\{i\in B:{\overline{a}}_{ik}>0\}$. If $R=\mathrm{\varnothing }$, then stop; the problem is unbounded.

5. Let $r\in R$ be such that $$\frac{{\overline{b}}_r}{{\overline{a}}_{rk}}=min\{\frac{{\overline{b}}_i}{{\overline{a}}_{ik}}:i\in R\}.$$

6. Replace $B$ with $(B\cup \{k\})\setminus \{r\}$ and go to step 1.

Remarks

1. Within an iteration, the variable $x_k$ is called the entering variable and $x_r$ is called the leaving variable.

2. As seen in the example above, going from step 6 to step 1 does not require one to compute the tableau from scratch from $$\begin{array}{rcl}z-{\mathbf{c}}^{\mathsf{T}}\mathbf{x}& =& 0\\ \mathbf{A}\mathbf{x}& =& \mathbf{b}.\end{array}$$ One simply multiplies the $x_r$-row by $\frac{1}{{\overline{a}}_{rk}}$ and the uses the resulting equation to eliminate $x_k$ in the other equations. This operation is sometimes called pivoting.

3. Note that if the right-hand sides are positive, the new solution will have a strictly better objective function value.

4. It is possible to have more than one choice for $k$ and more than one choice for $r$. A rule due to Robert Bland, known as Bland's anti-cycling rule states that we always choose the smallest index that works. Doing so will prevent cycling, a topic that we will discuss later.

Worked examples

1. Consider the following linear programming problem: $$\begin{array}{rrcrcrcrc}min& x_1& -& 2x_2& +& x_3& & & \\ (P)\text{s.t.}& x_1& -& 2x_2& +& x_3& +& x_4& =& 0\\ & x_1& +& x_2& +& 2x_3& -& 2x_4& =& 3\\ & x_1& ,& x_2& ,& x_3& ,& x_4& \ge & 0.\end{array}$$ Give the simplex tableau associated with the basis $B=\{1,2\}$ and show that the problem is unbounded.

   We need to perform row reduction to the system $$\begin{array}{rcrcrcrcrcl}z& -& x_1& +& 2x_2& -& x_3& & & =& 0\\ & & x_1& -& 2x_2& +& x_3& +& x_4& =& 0\\ & & x_1& +& x_2& +& 2x_3& -& 2x_4& =& 3.\end{array}$$ so that the pivot variables are $z$, $x_1$, and $x_2$. Subtracting the second equation from the third gives: $$\begin{array}{rcrcrcrcrcl}z& -& x_1& +& 2x_2& -& x_3& & & =& 0\\ & & x_1& -& 2x_2& +& x_3& +& x_4& =& 0\\ & & & & 3x_2& +& x_3& -& 3x_4& =& 3.\end{array}$$ Adding the second equation to the first equation and multiplying the third equation by $\frac{1}{3}$gives: $$\begin{array}{rcrcrcrcrcl}z& & & & & & & +& x_4& =& 0\\ & & x_1& -& 2x_2& +& x_3& +& x_4& =& 0\\ & & & & x_2& +& \frac{1}{3}{x}_3& -& x_4& =& 1.\end{array}$$ Adding twice the third equation to the second equation gives: $$\begin{array}{rcrcrcrcrcl}z& & & & & & & +& x_4& =& 0\\ & & x_1& & & +& \frac{5}{3}{x}_3& -& x_4& =& 2\\ & & & & x_2& +& \frac{1}{3}{x}_3& -& x_4& =& 1.\end{array}$$ This is the tableau associated with the basis $B=\{1,2\}$.

   Now, if we set $x_3=0$, then $$\begin{array}{rcl}z& =& -x_4\\ x_1& =& 2+x_4\\ x_2& =& 1+x_4.\end{array}$$ Note that $x_1,x_2\ge 0$ for all $x_4\ge 0$ but $z\to -\mathrm{\infty }$ as $x_4\to \mathrm{\infty }$. Hence, the problem is unbounded because for all $t\ge 0$, $\left[\begin{array}{c}2+t\\ 1+t\\ 0\\ t\end{array}\right]$ is a feasible solution with objective function value $-t$.

2. Use the tableau method to solve the following linear programming problem: $$\begin{array}{rrcrcrc}min& x_1& -& 4x_2& +& 2x_3& \\ (P)\text{s.t.}& x_1& -& x_2& +& x_3& =& 2\\ & & & x_2& +& x_3& =& 1\\ & x_1& ,& x_2& ,& x_3& \ge & 0.\end{array}$$ Begin with the basis $B=\{1,3\}$.

   Iteration 1

   1. The tableau associated with $B=\{1,3\}$ is $$\begin{array}{rcrcrcrcl}z& & & +& 4x_2& & & =& 3\\ & & x_1& -& 2x_2& & & =& 1\\ & & & & x_2& +& x_3& =& 1.\end{array}$$

   2. ${\mathbf{x}}^{\ast }=\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right].$

   3. Choose $k=2$ since the coefficient of $x_2$ in the $z$-row is positive.

   4. $R=\{3\}$ since the $x_3$-row is the only equation (other than the $z$-row) in which the coefficient of $x_2$ is positive.

   5. $r=3$ since $R$ contains only one element.

   6. New basis is $B=\{1,2\}$.

   Iteration 2

   1. The tableau associated with $B=\{1,2\}$ is $$\begin{array}{rcrcrcrcl}z& & & & & -& 4x_3& =& -1\\ & & x_1& & & +& 2x_3& =& 3\\ & & & & x_2& +& x_3& =& 1.\end{array}$$

   2. ${\mathbf{x}}^{\ast }=\left[\begin{array}{c}3\\ 1\\ 0\end{array}\right].$

   3. No coefficient of a nonbasic variable in the $z$-row is positive. Hence, ${\mathbf{x}}^{\ast }=\left[\begin{array}{c}3\\ 1\\ 0\end{array}\right]$ is an optimal solution.