The tableau: an handy and compact notation for dictionaries

You should read this document before performing the Christmas Assignment. Here, you can find already-solved-exercises as a training for the Christmas Assignment. We will resort on and establish the standard procedures and approaches to derive the solutions. We will also propose the use of the tableau as a convenient way to store and represent dictionaries. The use of the tableau as an handy and compact notation for dictionaries is also the most common standard when teaching LP. Offen, the several theoric and algorithmic aspects of LP are introduced as methods for manipulating and inspecting the tableau entries to get the desired results or seek the answers to the pertinent questions. If you will meet LP again in the future, it is quite likely that you will have to resort on the skill of knowing how to read a tableau. For this reason, it is a good idea to adopt this approach right now and achieve fluency in its language and mastery in its technicality. When performing the Christmas assignment, we recommend you to make use of the tableau since representing all steps in a compact form increases clarity and readability. As a matter of fact, the tableau offers the standard instrument to increase the quality of the document produced when solving LP problems.

Have a nice reading.

The tableau and the Simplex Method

To the following LP problem we associate the corresponding tableau:

$$\begin{array}{l} \max \mbox{\ }6x_1 + 7x_2\\ \left\{ \b... ...& 12 \\ x_4 & 2 & 1 & 8 \\ z & -6 & -7 & 0 \\ \end{array}$$

Where $x_3$ and $x_4$ are the names for the slack variables. Note that the coefficients of the objective function are put in the tableau with opposite signs and that the objective function corresponds (in the most widespread practice) to the last row.

To say it full, the tableau does not really correspond to an LP problem but to a particular dictionary of the problem, that is, to an LP problem as seen from the perspective of a basic solution (feasible or not). Here above, we have just ben lucky: since the problem was in standard form, it was very easy to fill in the corresponding tableau. Moreover, since the constant term in each constraint was non-negative, then the basic solution corresponding to this first tableau is feasible.

Question 1   What is the basic solution associated to the above tableau?

Answer: all the decision variables out of basis are set to 0 ($x_1 = x_2 = 0$), while $x_3=12$ ed $x_4=8$.

On the current solution, the objective function assumes a specific numerical value, which is reported on the right in the last row of the tableau.

In general, the following dictionary is more compactly described as a tableau:

$${\small \begin{array}{lcrrrrrr} x_{n+1} &=& b_1 & -a_{1,1}x_... ... & -c_1 & \ldots & -c_i & \ldots & -c_n & v \\ \end{array} }$$

Here is a second example:

$$\begin{array}{c} \mbox{\sc LP Problem}\\ \begin{array}{l... ... x_2, x_3 \geq 0 \end{array} \right. \end{array} \end{array}$$

$$\begin{array}{c} \mbox{\sc First Dictionary}\\ \\ \begin... ...ox {3}& 2 \\ z & -2 & -7 & 2 & 0 \\ \end{array} \end{array}$$

Question 2   In your opinion, why has the entry in the above tableau been boxed?

Answer: The is the pivot element.

Question 3   How would you choose the pivot element directly from the tableau?

Possible Answer: As pivot column, take any column whose last element $-c_{\bar{\jmath}}$ is as big as possible (positive), since our aim is to minimize. In this case, the winner would be the $+2$ in the third column.

To choose the pivot row, consider those $a_{i,\bar{\jmath}}$ which are positive. Among these, that one which minimizes the ratio $b_i/a_{i,\bar{\jmath}}$, is the pivot element.

Exercise 1   The pivot rule just introduced should not be that new to you? Could you now propose a second rule for the choice of the pivot element in the tableau.

Let us pivot in the dictionary and observe what is pivoting in the tableau.

$$\begin{array}{c} \mbox{\sc Initial Dictionary}\\ \\ \beg... ...1cm} {\Huge\downarrow} {\Large\mbox{ \ $(pivot)$}} \end{array}$$

$$\begin{array}{c} \mbox{\sc New Dictionary}\\ \\ \begin{a... ...}{3} & -\frac{2}{3} & -\frac{4}{3} \\ \end{array} \end{array}$$

In the tableau, let $\bar{\imath}$ be the pivot row and $\bar{\jmath}$ the pivot column. Let $p= a_{\bar{\imath},\bar{\jmath}}$ be the value of the pivot element. Here is the general rule to execute the pivot directly on the tableau:

$$\begin{array}{rrrrrrr} & x_1 \; & \ldots & x_{\bar{\jmath}... ..._{\bar{\jmath}}}{p} & \ldots & \ldots & \ldots \\ \end{array}$$

The entries which we have left unspecified in the second tableau, are modified as follows: $a_{i,j}$ becomes $a_{i,j}-\frac{a_{\bar{\imath},j}a_{i,\bar{\jmath}}}{p}$ and similarly $c_j$ becomes $c_j-\frac{a_{\bar{\imath},j}c_{\bar{\jmath}}}{p}$. Moreover $b_i$ becomes $b_i-\frac{a_{i,\bar{\jmath}}b_{\bar{\imath}}}{p}$ and $v$ becomes $v-\frac{-c_{\bar{\jmath}}b_{\bar{\imath}}}{p}$.

In conclusion, pivoting work as follows.

• The variables associated to the pivot row and column swap.
• The elements contained into the pivot row get divided by $p:= a_{\bar{\imath},\bar{\jmath}}$.
• The elements contained into the pivot row get divided by $-b$.
• The pivot element becomes $\frac{1}{p}$.
• Every element of the tableau outside the pivot row and outside the pivot column is modified as follows: $a_{i,j}$ becomes $a_{i,j}-\frac{a_{\bar{\imath},j}a_{i,\bar{\jmath}}}{p}$ and $c_j$ becomes $c_j-\frac{a_{\bar{\imath},j}c_{\bar{\jmath}}}{p}$. Moreover, $b_i$ becomes $b_i-\frac{a_{i,\bar{\jmath}}b_{\bar{\imath}}}{p}$ and $v$ becomes $v-\frac{-c_{\bar{\jmath}}b_{\bar{\imath}}}{p}$.

The pivot operation is illustrated in Figure 1.

Figure 1: The PIVOT operation.

To practice, let us get back to our LP problem and let us perform the next pivot.

$$\begin{array}{rrrrr} & x_1 & x_2 & x_5 \\ x_4 & \fbox {$... ...& -\frac{45}{7} & -\frac{4}{7} & -\frac{10}{7} \\ \end{array}$$

The elements in the last row are now all negative. We can therefore conclude that the optimal value of our problem was $-\frac{10}{7}$. (Why?) The optimal primal solution is $x_2=x_4=x_5 = 0$ with $x_1=\frac{1}{7}$ and $x_3=\frac{6}{7}$. The optimal dual solution is $y_1 = y_3 = 0$ with $y_2=-\frac{45}{7}$, $y_4=-\frac{2}{7}$ and $y_5=-\frac{4}{7}$. Note that also the dual solution is expressed in the tableau.

As a matter of fact, we can even obtain the tableau for the dual from the tableau of the primal.

$$\begin{array}{c} \mbox{\sc Primal Tableau}\\ \begin{arra... ...{7} & -\frac{2}{7} & -\frac{10}{7} \\ \end{array} \end{array}$$

Where the dual decision variable $y_4$ corresponds to the primal slack variable $x_4$ and is therefore the multiplier of the first primal constraint. The dual variable $y_1$ corresponds to the primal variable $x_1$ which is the multiplier of the first dual constraint; therefore $y_1$ is the surplus variable in the first dual constraint.

Question 4   What is the rule to go from the primal tableau to the dual tableau?

Exercise 2   Verify that the last tableau is the tableau for the dual problem at the optimum.

Question 5   In the last tableau, the product $x_i\cdot y_i$ is zero for each $i$. Can you give a simple reason? Does this property hold only for the last tableau?

Warning!!! 1   Note how under these standard conventions the rule to go from the primal tableau to the dual tableau is not the same as the rule to go from the dual back to the primal. (The rule is not indempotent, that is $R\bigcirc R \neq id$). This is in contrast with the fact that the dual of the dual is the primal. The contrast is only apparent: when going from an LP problem to its dual we must distinguish the inequalities $\leq$ from the inequalities $\geq$.
The standard convention for the tableau breakes this simmetry primal/dual with an arbitrary choice for the signs. The advantage is that of having an unique simple pivot operation which holds both for the primal and the dual.

When we are asked to maximize the objective function, then we follow the same procedure, with the only difference that now our aim is to make the elements of the last row non-negative. For example:

$$\begin{array}{l} \max \mbox{\ }2x_1 + 7x_2 -2x_3\\ \left... ...y} \\ x_1, x_2, x_3 \geq 0 \end{array} \right. \end{array}$$

$$\begin{array}{rrrrr} & x_1 & x_2 & x_3 \\ x_4 & 1 & \fbo... ...{2} & \frac{7}{2} & \frac{11}{2} & \frac{7}{2} \\ \end{array}$$

The optimal value of the objective function is now $\frac{7}{2}$. The optimal primal solution is $x_1=x_3 = 0$ with $x_2=\frac{1}{2}$. The optimal dual solution is $y_2 = 0$ with $y_1 = \frac{3}{2}$.

AN HANDY CHECK

Even with LP we have our check of the nine to make sure that computations did not introduce any mistake until now. Just assign to each variable the value of the coefficient of the same variable in the original objective function. For example, the last tableau becomes:

$$\begin{array}{rrrrrr} & & (2) & (0) & (-2) \\ & & \downa... ...{2} & \frac{7}{2} & \frac{11}{2} & \frac{7}{2} \\ \end{array}$$

For each column the following holds: the value of the coefficient associated to the column plus the value of the last element of the column equals the sum of the other elements of the column each multiplied by the coefficient of the row to which it belongs.

Column 1: $\frac{1}{2}(7) -3(0) = (2) + \frac{3}{2}$.
Column 2: $\frac{1}{2}(7) +1(0) = (0) + \frac{7}{2}$.
Column 3: $\frac{1}{2}(7) +4(0) = (-2) + \frac{11}{2}$.
Column 4: $\frac{1}{2}(7) +3(0) = \frac{7}{2}$.

These relations hold for every tableau, not necessarily optimal.

The tableau and the Dual Simplex Method

Consider an LP maximization problem in standard form. Let us assume that all coefficients in the objective function are non-positive. Therefore, in the last row of the first tableau all coefficients are non-negative, precisely like we would like them to be in the last tableau. Such a tableau is called dual-feasible. If all coefficinets in the last column are non-negative, then the current basic solution is feasible and the problem is already solved. Otherwise we better apply the Dual Simplex Method. An interesting characteristic of the Dual Simplex Method is that the pivot operation is exactly the same as for the (Primal) Simplex Method. The only difference among the two methods is in the choice of the pivot element. As a matter of fact, while the actaul rule is different, the philosophy behind the rule is the same.

Question 6   How would you choose the pivot element directly from the tableau?

Possible Answer: As pivot row take any row $\bar{\jmath}$ having a negative last element $b_{\bar{\imath}}$ (maybe the most negative) since we are striving to get primal feasibility (hence an optimal feasible solution).

The choice of the pivot column is dictated by the necessity of mantaining dual feasibility, which will be the invariant for the Dual Simplex Method, like primal feasibility was the invariant for the (Primal) Simplex Method. Therefore, to choose the pivot column we consider all the negative $a_{\bar{\imath},j}$. Among these, that one that minimizes the ratio $\vert c_j/a_{\bar{\imath},j}\vert$, is the pivot element.

Exercise 3   Could you propose another rule for the choice of the pivot element in the tableau?

Here is an example:

$$\begin{array}{l} \max \mbox{\ }-x_1 - 2x_2 \\ \left\{ \... ...{11}{2} \\ z & \frac{1}{2} & 3 & \frac{7}{2} \\ \end{array}$$

Note 1   The Dual Simplex Method corresponds to solving the dual problem by means of the (Primal) Simplex Method.
The Dual Simplex Method is more convenient when the origin in not primal-feasible but dual-feasible or when in the primal PL problem the number of constraints exceeds the number of decision variables.

How to deal with bounds on the single variables

If instead of having $x_j \geq 0$, we have $x_j \geq l_j$ with $l_j\neq 0$, then we rely on the substitution: $x'_j = x_j - l_j$. If a variable if bounded from above instead that from below, namely $x_j \leq u_j$, but $x_j \geq 0$ is not required, then we substitute $x'_j = u_j - x_j$.

When however a non-negative variable is bounded from above, such condition could be in principle regarded as a linear constraint of the problem. Nevertheless, when all variables are bounded (and in most cases an obvious bound can be produced), then we can take advantage of this special structure by considering both the variable $x_j$ and the variable $x'_j = u_j - x_j$ and deciding to adopt in the writing of the first tableau the one of the two which leads to a dual feasible tableau. We then start with the Dual Simplex Method. We must obviously guarantee that $0\leq x_j,x'_j \leq u_j$. Moreover, through the various phases of the Dual Simplex Method the dual feasibility is kept as an invariant, and if one of the primal variables employed to express the tableau ($x_j$ or $x'_j$) becomes negative, then a pivot step is executed with the effect to get closer to primal feasibility. It can happen however that a basic variable for the tableau exceeds its own bound from above. When this happens, we replace the corresponding row in the tableau as follows:

$\begin{array}{llrrrrl} &x'_j \mbox{ (o $x_j$) \hspace{0.3cm} } & a_{j,1} & a... ...3cm} } & -a_{j,1} & -a_{j,2} & \ldots & -a_{j,n} & \; u_j - b_j\\ \end{array}$

and then we can continue. For example:

$$\begin{array}{l} \max \mbox{\ }3x_1 + 4x_2 \\ \left\{ \... ... \\ 0 \leq x_1, x_2 \leq 5 \end{array} \right. \end{array}$$

After introducing the variables $x'_1 = 5 - x_1$ ed $x'_2 = 5 - x_2$, we choose to employ in the tableau the variables $x'_1$ and $x'_2$ since the coefficients of the objective function were both positive (and so?).

$$\begin{array}{l} \max \mbox{\ } 35 - 3x'_1 - 4x'_2 \\ \l... ...\ 0 \leq x'_1, x'_2 \leq 5 \end{array} \right. \end{array}$$

The sequence of tableax is therefore:

$$\begin{array}{rrrr} & x'_1 & x'_2 \\ x_3 & -1 & \fbox {$... ... z & \frac{7}{3} & \frac{2}{3} & \frac{41}{3} \\ \end{array}$$

Now $\frac{16}{3} > 5$ and therefore the first row of the tableau is substituted introducing $x_2$:

$$\begin{array}{rrrr} & x'_1 & x_3 \\ x_2 & \fbox {$-\frac... ..._3 \\ x'_1 & -6 & -1 & 2 \\ z & 14 & 3 & 9 \\ \end{array}$$

Optimal solution: $x_1 = 3$ ed $x_2 = 0$ with objective function $9$.

Sensitivity Analysis

Assume we are maximizing an objective function which represents a profit or some other form of benefit. The constraints will model limitations in raw materials, goods or availabilities. Then, the optimal values of the dual variables will express the maximum ``price'' that we could pay to increment one unit of the availability to which the dual variable is associated. (From here the name ``shadow price'' or ``marginal value''). We must however remember that the meaning of a shadow price is strictly local: in generale it will not be convenient to keep paying extra-units of availability on the basis of the shadow price for an arbitrary increase in availability. Hence the question: until when is the shadow price meaningful? In other words, what is the maximum increase in a certain facility which we can pursue while paying for it the shadow price? The answer can be easily obtained with reference to the dual tableau.

Assume for example that our target is to maximize the following profit:

$$\begin{array}{l} \max \mbox{\ }2x_1 + 6x_2 +3x_3\\ \left... ...y} \\ x_1, x_2, x_3 \geq 0 \end{array} \right. \end{array}$$

where $x_1, x_2$ and $x_3$ express non-negative levels of activity, whereas the constant terms in the constraints express bounds on specific availabilities. The tableau associated to the basic optimal solution is the following.

$$\begin{array}{rrrrr} & x_1 & x_2 & x_3 \\ x_4 & 1 & \fbo... ...}{2} & 2 & \frac{7}{2} \\ z & 1 & 3 & 3 & 15 \\ \end{array}$$

Therefore we can consider paying (certainly not more than) $1$ for increasing by one unit the availability on the first constraint. But how much of this availability can we buy at the price of $1$ for each extra-unit? Consider the dual of the last tableau:

$$\begin{array}{rrrr} & y_2 & y_5 \\ y_1 & -\frac{1}{2} & ... ... & 3 \\ z & -\frac{5}{2} & -\frac{7}{2} & 15 \\ \end{array}$$

Assume we increment by $D$ the availability on the first constraint. The advantage in considering the dual is that the only row which is affected by this change is the last one (corresponding to the last column in the primal tableau). The next row can be produced by substitution or we can make use of the HANDY CHECK seen above.

$$\begin{array}{rrrrr} & & (0) & (6) \\ & & \downarrow \;&... ... 3 \\ & z & -\frac{5}{2} & -\frac{7}{2} & 15 \\ \end{array}$$

Remember that for each column the following holds: the value of the last element of the column is obtained by summing up the other elements of the column, each multiplied by the coefficient of the row to which it belongs, and subtracting the value of the coefficient associated to the column.

Column 1: $-\frac{1}{2}(0)-\frac{1}{2}(5+D)-1(0)-(0)=-\frac{5+D}{2}$
Column 2: $-\frac{3}{2}(0)+\frac{1}{2}(5+D)-2(0)-(6)= \frac{-7+D}{2}$
Column 3: $1(0)+3(5+D)+3(0) = 15+3D$

Therefore, the last row is:

$$\begin{array}{lll} -\frac{5+D}{2} & \frac{-7+D}{2} & 15+3D \\ \end{array}$$

We can now easily discover that the tableau remains optimal as long ad $D$ does not exceed $7$. We conclude that $7$ is the maximum increment in availability for the first constraint that we are willing to buy by paying $1$ for each extra unit. If we are interested in determining the price that we should be considering to pay for bigger increments (the new shadow prices), then we must execute a new pivot.