3.5. An Extended Example and Tableaux

Once you fully grasp how the Simplex Algorithm works, it is a very simple algorithm. Given the rather formal discussion so far, on the other hand, it may seem like a fairly complex algorithm that requires you to remember many bits and pieces. In this section, we walk through solving a simple LP using the Simplex Algorithm, and you will learn about tableaux as convenient tabular representations of LPs that make it easy to perform the elementary row operations needed to implement pivoting steps.

So consider the following LP:

\[\begin{gathered} \text{Maximize } x_1 - 2x_2 + x_3\\ \begin{array}{r<{\ }r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r} \text{s.t.} & x_1 & + & 2x_2 & + & 2x_3 & \ge & 3\\ & 3x_1 & + & 2x_2 & + & x_3 & \ge & 5\\ & x_1 & & & + & 3x_3 & \le & 10\\ & x_1 & + & x_2 & + & x_3 & \le & 9\\ & & & & & \llap{x_1, x_2, x_3} & \ge & 0 \end{array} \end{gathered}\tag{3.3}\]

To solve it using the Simplex Algorithm, we first need to convert it into canonical form and then into standard form. To obtain an LP in canonical form, we need to replace the first two constraints with upper bound constraints:

\[\begin{gathered} \text{Maximize } x_1 - 2x_2 + x_3\\ \begin{array}{r<{\ }r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r} \text{s.t.} & -x_1 & - & 2x_2 & - & 2x_3 & \le & -3\\ & -3x_1 & - & 2x_2 & - & x_3 & \le & -5\\ & x_1 & & & + & 3x_3 & \le & 10\\ & x_1 & + & x_2 & + & x_3 & \le & 9\\ & & & & & \llap{x_1, x_2, x_3} & \ge & 0 \end{array} \end{gathered}\tag{3.4}\]

To convert this into standard form, we introduce slack variables \(y_1, \ldots, y_4\) and convert the upper bound constraints into equality constraints:

\[\begin{gathered} \text{Maximize } x_1 - 2x_2 + x_3\\ \begin{array}{r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r} \text{s.t.}\ y_1 & = & -3 & + & x_1 & + & 2x_2 & + & 2x_3\\ y_2 & = & -5 & + & 3x_1 & + & 2x_2 & + & x_3\\ y_3 & = & 10 & - & x_1 & & & - & 3x_3\\ y_4 & = & 9 & - & x_1 & - & x_2 & - & x_3\\ x_1, x_2, x_3, y_1, y_2, y_3, y_4 & \ge & 0 \end{array} \end{gathered}\tag{3.5}\]

This is the LP \(P\) we want to solve using the Simplex Algorithm.

Our alternative way of writing an LP in standard form (2.23),

\[\begin{gathered} \text{Maximize } x_1 - 2x_2 + x_3\\ \begin{array}{r@{\ }r@{\ }r@{\ }r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r>{{}}c<{{}}r} \text{s.t.}\ y_1 & & & & - & x_1 & - & 2x_2 & - & 2x_3 & = & -3\\ & y_2 & & & - & 3x_1 & - & 2x_2 & - & x_3 & = & -5\\ & & y_3 & & + & x_1 & & & + & 3x_3 & = & 10\\ & & & y_4 & + & x_1 & + & x_2 & + & x_3 & = & 9\\ &&&&&&&&& \llap{x_1, x_2, x_3, y_1, y_2, y_3, y_4} & \ge & 0, \end{array} \end{gathered}\]

where the basic variables are \(y_1, y_2, y_3, y_4\), is very useful in the next step, which is the conversion of this LP into a tableau:

\[\begin{array}{|r|rrrr|rrr|} \hline & \rlap{\textbf{Basic}}\phantom{y_1} &&&& \rlap{\textbf{Non-basic}}\phantom{-1}\\ & y_1 & y_2 & y_3 & y_4 & x_1 & x_2 & x_3\\ \hline -3 & 1 & 0 & 0 & 0 & -1 & -2 & -2\\ -5 & 0 & 1 & 0 & 0 & -3 & -2 & -1\\ 10 & 0 & 0 & 1 & 0 & 1 & 0 & 3\\ 9 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ \hline 0 & 0 & 0 & 0 & 0 & 1 & -2 & 1\\ \hline \end{array}\]

In the tableau, the first \(m\) rows represent the equality constraints of the LP. As an example, consider the first constraint,

\[y_1 - x_1 - 2x_2 - 2x_3 = -3.\]

The leftmost entry in the first row of the tableau is \(b_1 = -3\). The remaining columns represent the variables of the LP as indicated by their labels at the top of the tableau. Correspondingly, the entries in the first row are \(1\), \(0\), \(0\), \(0\), \(-1\), \(-2\), and \(-2\), the coefficients of \(y_1\), \(y_2\), \(y_3\), \(y_4\), \(x_1\), \(x_2\), and \(x_3\) in the first constraint. The rows corresponding to the other constraints are obtained analogously.

The last row of the tableau represents the objective function, again listing the coefficients of all variables in the objective function. The bottom-left entry of the last row is the negation \(-d\) of the additive term \(d\) in our general-form objective function \(cz + d\). Here, the objective function is \(x_1 - 2x_2 + x_3\), so \(d = 0\), \(y_1\), \(y_2\), \(y_3\), and \(y_4\) have coefficient \(0\), and \(x_1\), \(x_2\), and \(x_3\) have coefficients \(1\), \(-2\), and \(1\), respectively.

The ordering of the columns is such that the first \(m\) columns are always the basic variables in the current basis; the remaining variables are the non-basic variables. The basic variables are ordered so that the \(i\)th basic variable is the one corresponding to the \(i\)th equality constraint. Non-negativity constraints are not represented explicitly in the tableau because we know that all variables in an LP in standard form need to be non-negative.

Given this structure of the tableau, the coefficients of the basic variables in the equality constraints always form an identity matrix and the coefficients of the basic variables in the objective function are always \(0\). This becomes more apparent if we omit entries of the tableau that are \(0\), except entries in the leftmost column. Given the understanding that the leftmost \(m\) columns represent basic variables, we can also omit the labelling of the column groups as representing basic or non-basic variables. This gives the following more compact representation of a tableau:

\[\begin{array}{|r|rrrr|rrr|} \hline & y_1 & y_2 & y_3 & y_4 & x_1 & x_2 & x_3\\ \hline -3 & 1 & & & & -1 & -2 & -2\\ -5 & & 1 & & & -3 & -2 & -1\\ 10 & & & 1 & & 1 & & 3\\ 9 & & & & 1 & 1 & 1 & 1\\ \hline 0 & & & & & 1 & -2 & 1\\ \hline \end{array}\]

In summary, the tableau encodes

• The current LP;
• Its basis, \((y_1, y_2, y_3, y_4)\) in this example;
• Its basic solution, \(y_1 = b_1 = -3\), \(y_2 = b_2 = -5\), \(y_3 = b_3 = 10\), \(y_4 = b_4 = 9\), and \(x_1 = x_2 = x_3 = 0\); and
• The objective function value \(d\) of the basic solution, here \(d = 0\). (Remember, the entry in the bottom-left corner of the tableau is \(-d\), not \(d\).)

Now let's solve this LP.