Consider the following linear programming problem: \[\begin{array}{rrcrcrcrcrcl} \min & x_1 & + & 2x_2 & & & - & 2x_4 & - & x_5\\ (P)~~~~~\mbox{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 & \geq & 0. \end{array}\]
Is the basic feasible solution \(\mathbf{x}^* = \begin{bmatrix} 2 \\ 1\\ 0 \\ 0\\ 0\end{bmatrix}\) 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}{rrcrcc} \max & y_1 & + & 3y_2 \\ (D)~~~~~\mbox{s.t.} & y_1 & + & y_2 & \leq & 1 \\ & -y_1 & + & y_2 & \leq & 2 \\ & y_1 & + & 2y_2 & \leq & 0 \\ & & & -2y_2 & \leq & -2 \\ & 2y_1 & + & 2y_2 & \leq & -1. \end{array}\] Then \(\mathbf{x}^*\) is optimal if and only if there exists \(\mathbf{y}^*\) feasible to \((D)\) satisfying the complementary slackness conditions with \(\mathbf{x}^*\). As the first two components of \(\mathbf{x}^*\) are positive, such a \(\mathbf{y}^*\) must satisfy \begin{eqnarray*} y^*_1 + y^*_2 = 1 \\ -y^*_1 + y^*_2 = 2 \\ \end{eqnarray*} Solving gives the unique solution \( \begin{bmatrix} y^*_1 \\ y^*_2 \end{bmatrix} = \begin{bmatrix} -\frac{1}{2} \\ \frac{3}{2}\end{bmatrix}\). However, this is not a feasible solution to \((D)\). (It violates the third constraint, for example.) Hence, \(\mathbf{x}^*\) 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}{rcrcrcc} 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 & \geq & 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}{rcrcrcc} 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}{rlcrl} \min & \mathbf{c}^\mathsf{T}\mathbf{x} \\ (P)~~~~~\mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \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} = \begin{bmatrix} x_1 \\ \vdots \\ x_n\end{bmatrix}\) is a tuple of variables, the simplex tableau associated with a basis \(B\) is obtained from row reducing the system \begin{eqnarray*} z- \mathbf{c}^\mathsf{T} \mathbf{x} & = & 0\\ \mathbf{A}\mathbf{x} & = & \mathbf{b} \end{eqnarray*} 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,\ldots,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,\ldots,n\}\setminus B\), the tableau can be represented by \begin{eqnarray*} z- (\mathbf{c}^\mathsf{T}_N - \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{eqnarray*} where \(\mathbf{y}^\mathsf{T} = \mathbf{c}^\mathsf{T}_B\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 \gt 0\) or \(x_5 \gt 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}{rcrccl} & & x_1 & & & + & \frac{3}{2} x_3 & = & 2 \\ & & & & x_2 & + & \frac{1}{2}x_3 & = & 1, \end{array}\] or equivalently \begin{eqnarray*} x_1 = 2-\frac{3}{2} x_3 \\ x_2 = 1- \frac{1}{2}x_3. \end{eqnarray*} To obtain a feasible solution, we need \(x_1,x_2 \geq 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\geq 0\) is \(\frac{4}{3}\). Setting \(x_3 = \frac{4}{3}\) gives us the solution \(\begin{bmatrix} 0 \\ \frac{1}{3} \\ \frac{4}{3} \\ 0 \\ 0 \end{bmatrix} \) 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}{rcrcrcc} 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{eqnarray*} x_3 = \frac{4}{3} + \frac{2}{3}x_4 & \geq & 0 \\ x_2 = \frac{1}{3} + \frac{2}{3}x_4 & \geq & 0. \\ \end{eqnarray*} But these inequalities are satisfied for all \(x_4\geq 0\). Thus, \( \begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix} = \begin{bmatrix} 0 \\ \frac{1}{3} + \frac{2}{3}t \\ \frac{4}{3} + \frac{2}{3}t \\ t \\ 0\end{bmatrix}\) is a feasible solution for all \(t \geq 0\) with objective function value \(\frac{2}{3} - \frac{2}{3} t \rightarrow -\infty\) as \(t \rightarrow \infty\). Hence, the problem is unbounded.
Summarize the ideas illustrated above gives the tableau method for solving \[\begin{array}{rlcrl} \min & \mathbf{c}^\mathsf{T}\mathbf{x} \\ (P)~~~~~\mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \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:
Obtain the tableau associated with \(B\).
Let \(\mathbf{x}^*\in \mathbb{R}^n\) be such that for each \(i \in B\), \(x^*_i\) equals \(\bar{b}_i\), the right-hand side value of the \(x_i\)-row, and \(x^*_i = 0\) for each \(i \notin B\). (That is, \(\mathbf{x}^*\) is the basic feasible solution determined by \(B\).)
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}^*\) is an optimal solution.
For each \(i \in B\), let \(\bar{a}_{ik}\) denote the coefficient of \(x_k\) in the \(x_i\)-row. Let \(R = \{ i \in B : \bar{a}_{ik} \gt 0\}\). If \(R = \emptyset\), then stop; the problem is unbounded.
Let \(r \in R\) be such that \[\frac{\bar{b}_r}{\bar{a}_{rk}} = \min \left\{ \frac{\bar{b}_i}{\bar{a}_{ik}} : i \in R \right\}.\]
Replace \(B\) with \((B\cup \{k\})\setminus \{r\}\) and go to step 1.
Within an iteration, the variable \(x_k\) is called the entering variable and \(x_r\) is called the leaving variable.
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{eqnarray*} z- \mathbf{c}^\mathsf{T} \mathbf{x} & = & 0\\ \mathbf{A}\mathbf{x} & = & \mathbf{b}. \end{eqnarray*} One simply multiplies the \(x_r\)-row by \(\frac{1}{\bar{a}_{rk}}\) and the uses the resulting equation to eliminate \(x_k\) in the other equations. This operation is sometimes called pivoting.
Note that if the right-hand sides are positive, the new solution will have a strictly better objective function value.
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.
Example. We illustrate the steps of the tableau method on the example introduced at the beginning: \[\begin{array}{rrcrcrcrcrcl} \min & x_1 & + & 2x_2 & & & - & 2x_4 & - & x_5\\ (P)~~~~~\mbox{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 & \geq & 0. \end{array}\] We will take \(B = \{1,2\}\) as the starting basis.
As we saw earlier, the tableau associated with \(B\) is \[\begin{array}{rcrcrcc} 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}\]
The basic solution determined by \(B\) is \(\mathbf{x}^* = \begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ 0\end{bmatrix}.\) (Note that \(\mathbf{x}^*\) is in fact a basic feasible solution. If it were not feasible, we would not be able to continue with this method.)
Note that the coefficient of \(x_3\) and that of \(x_5\) are positive in the \(z\)-row. Therefore, we can set \(k\) to \(3\) or \(5\). We use Bland's anti-cycling rule and choose the smaller index. Hence, \(k = 3\) and so \(x_3\) is the entering variable.
In this step, we need to obtain \(R = \{ i \in B : \bar{a}_{ik} \gt 0\}\) where \(\bar{a}_{ik}\) denote the coefficient of \(x_k\) in the \(x_i\)-row. We can see from the tableau that \[\bar{a}_{1,3} = \frac{3}{2},~\bar{a}_{2,3} = \frac{1}{2}.\] Since both coefficients are positive, we have \(R = \{1,2\}\).
Now, \(\bar{b}_1 = 2\) and \(\bar{b}_2 = 1\). (Recall that \(\bar{b}_i\) refers to the right-hand side value of the \(x_i\)-row for all \(i \in B\).) Hence, \[\min \left\{ \frac{\bar{b}_i}{\bar{a}_{ik}} : i \in R \right\}= \min \left\{ \frac{\bar{b}_1}{\bar{a}_{1,3}}, \frac{\bar{b}_2}{\bar{a}_{2,3}} \right\} = \min \left\{ \dfrac{2}{\frac{3}{2}}, \dfrac{1}{\frac{1}{2}}\right\} = \frac{4}{3}\] which is attained by \(\frac{\bar{b}_1}{\bar{a}_{1,3}}.\) Hence, \(r = 1\).
The new \(B\) is \(\{1,2\}\cup\{3\}\setminus \{1\} = \{2,3\}\).
We can now proceed to perform another iteration starting with the new basis \(B = \{2,3\}\).
Consider the following linear programming problem: \[\begin{array}{rrcrcrcrcl} \min & x_1 & - & 2x_2 & +& x_3 & & & \\ (P)~~~~~\mbox{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 & \geq & 0. \end{array}\] Give the simplex tableau associated with the basis \(B = \{1,2\}\) and show that the problem is unbounded.
Use the tableau method to solve the following linear programming problem: \[\begin{array}{rrcrcrcl} \min & x_1 & - & 4x_2 & + & 2x_3 & \\ (P)~~~~~\mbox{s.t.} & x_1 & - & x_2 & + & x_3 & = & 2 \\ & & & x_2 & + & x_3 & = & 1 \\ & x_1 & , & x_2 & , & x_3 & \geq & 0. \end{array}\] Begin with the basis \(B = \{1,3\}\).