Objectives
-
Write down a tableau for a LOP
-
Perform a matrix pivot on a tableau.
-
Develop an algorithm on the tableau to optimize the tableau.
-
Use software to perform pivots to the simplex tableau.
Section 3.2 Tableaus and the Simplex Method
In Section 3.1, we walked through how to solve a Linear Optimization Problem (LOP) using the dictionary. It was a bit cumbersome to solve the problem this way in terms of solving for variables and substitute that into all other equations and simplifying.
We see in this section that since all of the equations are linear, we can use a matrix to organize the equations and perform the operations.
Subsection 3.2.1 Introduction to tableaus
\begin{align*}
4x_1 + 3x_2 + x_3 \amp = 120\\
x_1 + 2x_2 + x_4 \amp = 40\\
x_2 + x_5 \amp = 16
\end{align*}
and also the objective function can be written as \(-x_1 -3x_2 + z = 0\text{.}\) These four equations can be put into a matrix as
\begin{equation}
\left[ \begin{array}{rr|rrrr|r} 4 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 120 \\ 1 \amp 2 \amp 0 \amp 1 \amp 0 \amp 0 \amp 40 \\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 16 \\ \hline -1 \amp -3 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \end{array} \right]\tag{3.2.1}
\end{equation}
The first two columns are the variables \(x_1\) and \(x_2\text{,}\) the original variables, the next block of four columns are \(x_3, x_4, x_5\) and \(z\) and the last column is the \(b\)-column of right hand sides. Also, the last row is the objective row. It is standard to write the tableau with vertical lines that separate the original variables from the slack and objective variables and the last (constant) column, as well as a horizontal line to separate out the objective function.
Also, recall that the dictionary has the basis of \(\beta = \{3, 4, 5\}\) and parameters \(\pi = \{1,2\}\text{.}\) We can see this from the tableau by looking at the columns. Columns 3 through 6 are columns of an identity matrix and these are the basic variables (except for \(z\)). The remaining columns 1 and 2 are thus the parameters.
Knowing this, we can read the basic solution by setting the parameters to zero. Doing this, results in the matrix:
\begin{equation*}
\left[ \begin{array}{rrrr|r} 1 \amp 0 \amp 0 \amp 0 \amp 120 \\ 0 \amp 1 \amp 0 \amp 0 \amp 40 \\ 0 \amp 0 \amp 1 \amp 0 \amp 16 \\ \hline 0 \amp 0 \amp 0 \amp 1 \amp 0 \end{array} \right].
\end{equation*}
Recall that first three columns are the basic variables, the 4th columns is the objective, so this corresponds to
\begin{align*}
x_3 \amp =120,\\
x_4 \amp =40,\\
x_5 \amp =16,\\
z \amp =0.
\end{align*}
We will perform pivots on these matrices, but let’s look at another tableau and how to write the basic solution.
Example 3.2.1.
Find the basic solution of the following tableau:
\begin{equation*}
\left[\begin{array}{rr|rrrr|r} 4 \amp 0 \amp 1 \amp 0 \amp -3 \amp 0 \amp 72\\ 1 \amp 0 \amp 0 \amp 1 \amp -2 \amp 0 \amp 8\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 16\\ \hline -1 \amp 0 \amp 0 \amp 0 \amp 3 \amp 1 \amp 48\\ \end{array} \right]
\end{equation*}
where the variables are the standard \(x_1, x_2, \ldots, x_5\text{.}\)
Solution.
First, notice that the parameter set is \(\pi = \{1,5\}\) because those columns are not multiples of the identity matrix. We set \(x_1\) and \(x_5\) to zero and write down the equations as
\begin{align*}
x_3 \amp =72,\\
x_4 \amp =8,\\
x_2 \amp = 16.
\end{align*}
This can also be written as
\begin{equation*}
\boldsymbol{x} = \left[\begin{array}{rr|rrr} 0 \amp 16 \amp 72 \amp 8 \amp 0 \end{array}\right]^{\intercal}.
\end{equation*}
As we will see below, often the parameters will have a coefficient and that will need to be divided through to find the result.
As we saw in Section 3.1, solving for various variables switches the basis and parameters and moves the basic solution from vertex to vertex along the feasible set. We can represent each dictionary as a tableau, but in this section we will learn how to do the same operation on the tableau itself.
Subsection 3.2.2 Operations on Tableaus
We now repeat what we did in Section 3.1 using a tableau instead of dictionaries. The tableau from (3.2.1) is
\begin{equation}
\left[ \begin{array}{rr|rrrr|r} 4 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 120 \\ 1 \amp 2 \amp 0 \amp 1 \amp 0 \amp 0 \amp 40 \\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 16 \\ \hline -1 \amp -3 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \end{array} \right]\tag{3.2.2}
\end{equation}
From the steps examined in the Dictionary, we want \(x_1\) to be a basis and we also determined that \(x_3\) should be a parameter. Switching the basis variables can be done with a matrix pivot described in Subsection 1.3.6 about row 1, column 1 or since \(x_1\) takes the place of \(x_3\) in the basis, this is equivalent to the tableau pivot of \(1 \mapsto 3\text{.}\) The row operations and the transformed matrix is:
\begin{equation}
\begin{array}{r} -R_1 + 4R_2 \to R_2, \\ 0 R_1 + 4R_3 \to R_3, \\ R_1 + 4R4 \to R_3, \end{array} \qquad \left[\begin{array}{rr|rrrr|r} 4 \amp 3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 120 \\ 0 \amp 5 \amp -1 \amp 4 \amp 0 \amp 0 \amp 40 \\ 0 \amp 4 \amp 0 \amp 0 \amp 4 \amp 0 \amp 64 \\ \hline 0 \amp -9 \amp 1 \amp 0 \amp 0 \amp 4 \amp 120 \end{array} \right]\tag{3.2.3}
\end{equation}
To find the basic solution of (3.2.3), note that the parameter set is now \(\pi = \{2,3\}\text{,}\) which are the columns which are not columns of the identity matrix. If we set these two variables to zero, then read the other solutions off the matrix to get:
\begin{equation*}
\boldsymbol{x} = \frac{1}{4} \left[\begin{array}{cc|ccc} 120 \amp 0 \amp 0 \amp 40 \amp 64 \end{array}\right]^{\intercal}.
\end{equation*}
where the \(4\text{,}\) which is the coefficient of the basic variables is included as the fraction \(1/4\text{.}\)
For the next step, we use the same logic as in Section 3.1 to determine that 2 leaves the basis and 4 enters or the tableau pivot \(2 \mapsto 4\text{.}\) This corresponds to doing a matrix pivot on row 2, column 2 and eliminate the rest of the elements in column 2. These row operations are
\begin{align*}
\\
\frac{1}{4} R_1 \amp \to R_1, \amp \frac{1}{4} R_3 \amp\to R_3, \amp \frac{1}{4} R_4 \amp \to R_4
\end{align*}
and the result is
\begin{equation}
\begin{array}{r} -3R_{2} +5R_{1}\to R_{1}, \\ -4R_{2} +5R_{3} \to R_{3},\\ 9R_{2} + 5 R_{4} \to R_{4}, \\ \frac{1}{4} R_1 \to R_1, \\ \frac{1}{4} R_3 \to R_3, \\ \frac{1}{4} R_4 \to R_4, \end{array} \qquad \left[\begin{array}{rr|rrrr|r} 5 \amp 0 \amp 2 \amp -3 \amp 0 \amp 0 \amp 120\\ 0 \amp 5 \amp -1 \amp 4 \amp 0 \amp 0 \amp 40\\ 0 \amp 0 \amp 1 \amp -4 \amp 5 \amp 0 \amp 40\\ \hline 0 \amp 0 \amp -1 \amp 9 \amp 0 \amp 5 \amp 240\\ \end{array} \right]\tag{3.2.4}
\end{equation}
After performing a pivot, the next step is to check if it is optimal. This means looking at the objective row, which can be written (by solving for \(5z\text{:}\)
\begin{equation*}
5z = 240 + x_3 - 9x_4
\end{equation*}
and since increasing \(x_3\) increases \(z\text{,}\) so this is not an optimal solution. We can look at what we did in the dictionary form of this to determine which variable enters the basis, but let’s use the tableau to determine this. We will zero out \(x_4\text{,}\) the other basic variable
\begin{align*}
5x_1 + 2x_3 \amp = 120\\
5x_2 - x_3 \amp = 40\\
x_3 + 5x_5 \amp =40
\end{align*}
We seek to maximize the amount to increase \(x_3\) and that will switch the other variable to the basis.
\begin{align*}
2x_3-120 \amp \geq 0 \amp x_3 \geq 40
\end{align*}
and we pick the 3rd equation resulting in \(x_5\) entering the basis or the tableau pivot of \(3 \mapsto 5\text{.}\) This is equivalent to a matrix pivot about row 3, column 3, with the row operations:
\begin{equation}
\begin{array}{r} -2R_3 + R_1 \to R_1, \\ R_3 + R_2 \to R_2, \\ R_3 + R_4 \to R_4, \\ \frac{1}{5} R_1 \to R_2, \\ \frac{1}{5} R_2 \to R_2, \\ \frac{1}{5} R_4 \to R_4, \end{array} \qquad \left[\begin{array}{rr|rrrr|r} 1 \amp 0 \amp 0 \amp 1 \amp -2 \amp 0 \amp 8\\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 16\\ 0 \amp 0 \amp 1 \amp -4 \amp 5 \amp 0 \amp 40\\ \hline 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 56\\ \end{array} \right]\tag{3.2.5}
\end{equation}
Now if we look at the objective row, this can be written as \(z = 56 - x_4 - x_5\) and since increasing either of the two basic variables, decreases the objective, so this is optimal. The basic solution for this tableau is
\begin{equation*}
\boldsymbol{x} = \left[\begin{array}{cc|ccc} 8 \amp 16 \amp 40 \amp 0 \amp 0 \end{array}\right]^{\intercal}
\end{equation*}
with the objective value of \(z=56.\text{.}\) This is the same result as the dictionary in Section 3.1. In fact, the steps were identical, just in a matrix context instead of a algebra context.
Subsection 3.2.3 Performing Tableau Operations with WebCAS
The row operations in the previous section that perform a matrix pivot is the
piv command from Subsection 1.3.6. Let’s revisit the simplex tableau in (3.2.2) in WebCAS.
First, go to the Gaussian Eliminator in WebCAS and we want to fix some of the settings that will decorate the matrices in a way similar to those shown here. Click the gear icon in the top bar and
-
For the Vertical Line Mode, select Before Last Column.
-
Select the checkbox for the Horizontal Line for last row.
-
On the option Slack Variables, select \(Standard\text{.}\)
And click Save Changes.
Enter the matrix in (3.2.2) in the Enter a Matrix textbox and it should look the same as the matrix. Recall that separate all numbers by spaces (no other symbol) and each row should be a separate row in the text box.
Note that the first step in finding the optimal value of the tableau in (3.2.2) is to do a matrix pivot about row 1, column 1 or a tableau pivot \(1 \mapsto 3\text{.}\) If you use WebCAS with
piv(1,1), you will get the tableau in (3.2.3). Note that you can also use the tableau pivot notation 1 |-> 3 to accomplish the same task.
The next step results in a matrix pivot around row 2, column 2 or tableau pivot \(2 \mapsto 4\text{.}\) Using
piv(2,2) or 2 |-> 4 in WebCAS will result in (3.2.4).
The last step in finding the optimal solution was to do the matrix pivot around row 3, column 3 or tableau pivot \(3 \mapsto 5\text{.}\) Using
piv(3,3) or 3 |-> 5 in WebCAS will result in (3.2.5).
Subsection 3.2.4 Phase II of the Simplex Method
It seems odd that we start with what is called Phase II of a method to solve, but all problems will need to go through Phase II and as we will see below that not all problems need to go through Phase I.
Algorithm 3.2.2. Phase II of Simplex Method.
If a tableau is feasible, then the following steps are Phase II of the simplex method:
-
If there are no negative numbers in the objective row, the basic solution is optimal. The algorithm should stop.
-
If not, choose the leftmost negative number in the objective row. This is the pivot column. The variable \(x_{j}\) that corresponds to the \(j\)th column is called the entering variable since this variable is entering the basis.
-
Choose \(i\) such that the b-ratio is the smallest nonnegative ratio. Row \(i\) will be the pivot row. The basic variable in the \(i\)th row is called the leaving variable and denote it \(k\text{.}\)
-
Perform a matrix pivot about row \(i\text{,}\) column \(j\) or in terms of a tableau pivot \(j \mapsto k\text{.}\)
-
Goto step 1.
Example 3.2.3.
Consider a LOP with the following tableau:
\begin{equation*}
\left[\begin{array}{rrr|rrrr|r} 2 \amp 1 \amp 2 \amp 1 \amp 0 \amp 0 \amp 0 \amp 30\\ 4 \amp 1 \amp 3 \amp 0 \amp 1 \amp 0 \amp 0 \amp 48\\ -1 \amp 4 \amp 5 \amp 0 \amp 0 \amp 1 \amp 0 \amp 40\\ \hline -3 \amp -1 \amp -2 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
Note first that the basic solution is feasible because the right column has no negative numbers. Therefore, use Algorithm 3.2.2 to find the solution.
Solution.
First, note that the objective row (bottom) has negative numbers, so this isn’t an optimal solution. We select the left-most negative number in this row, which is column 1.
We compute the \(b\)-ratio with
\begin{equation*}
\begin{bmatrix} 30/2 \\ 48/4 \\ 40/(-1) \end{bmatrix} = \begin{bmatrix} 15 \\ 12 \\ -40 \end{bmatrix}
\end{equation*}
and the small non-negative ratio is in the second row. Therefore we perform a pivot about the second row, first column. Note: since \(x_1\) will enter the basis and \(x_5\) will leave, then the tableau pivot is \(1 \mapsto 5\text{.}\)
After performing the matrix pivot we get:
\begin{equation*}
\left[\begin{array}{rrr|rrrr|r} 0 \amp 2 \amp 2 \amp 4 \amp -2 \amp 0 \amp 0 \amp 24\\ 4 \amp 1 \amp 3 \amp 0 \amp 1 \amp 0 \amp 0 \amp 48\\ 0 \amp 17 \amp 23 \amp 0 \amp 1 \amp 4 \amp 0 \amp 208\\ \hline 0 \amp -1 \amp 1 \amp 0 \amp 3 \amp 0 \amp 4 \amp 144\\ \end{array} \right]
\end{equation*}
Examining this tableau, there is still a negative number in the objective row, which means that this is not an optimal solution. Therefore, we find the \(b\)-ratios using the 2nd column or
\begin{equation*}
\begin{bmatrix} 24/2 \\ 48/ 1 \\ 208/17 \end{bmatrix} \approx \begin{bmatrix} 12 \\ 48 \\12.234 \end{bmatrix}
\end{equation*}
and since the smallest non-negative number is in the first row, the next step is to perform a matrix pivot about the first row, second column. This corresponds to the tableau pivot of \(2 \mapsto 4\) resulting in
\begin{equation*}
\left[\begin{array}{rrr|rrrr|r} 0 \amp 2 \amp 2 \amp 4 \amp -2 \amp 0 \amp 0 \amp 24\\ 2 \amp 0 \amp 1 \amp -1 \amp 1 \amp 0 \amp 0 \amp 18\\ 0 \amp 0 \amp 3 \amp -17 \amp 9 \amp 2 \amp 0 \amp 2\\ \hline 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 2 \amp 78\\ \end{array} \right]
\end{equation*}
Now notice that the objective row has no more negative numbers in it. This means that the basic solution of
\begin{equation*}
\boldsymbol{x} = \frac{1}{2} \left[\begin{array}{rrr|rrr} 18 \amp 24 \amp 0 \amp 0 \amp 0 \amp 2 \end{array}\right]^{\intercal} = \left[\begin{array}{rrr|rrr} 9 \amp 12 \amp 0 \amp 0 \amp 0 \amp 1 \end{array}\right]^{\intercal}
\end{equation*}
is optimal. The objective value is \(z = 78/2=39\text{.}\) Note that using the original variables, this solution corresponds to the point \(x_1 =9, x_2=12, x_3=0\text{.}\)
We’ll solve one more problem in this section to show Phase II of the Simplex Method.
Problem 3.2.4.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp \amp z = 2x_1+7x_2, \amp \\ \text{subject to} \amp \amp \amp \amp x_1 + x_2 \amp \leq 15, \amp \amp \amp 2x_1 + 3x_2 \amp \leq 38, \amp \amp \amp 4x_1 + x_2 \amp \leq 56,\amp \amp \amp x_1 + 5x_2 \amp \leq 62,\amp \text{and}\amp \amp x_1, x_2 \amp \geq 0.\amp \end{aligned}
\end{equation*}
Checkpoint 3.2.5.
Use Phase II of the Simplex method to find the optimal solution of Problem 3.2.4 .
Solution.
First, write the constraints with slack variables:
\begin{align*}
x_1 + x_2 + x_3 \amp = 15 \\
2x_1 + 3x_2 + x_4\amp = 38 \\
4x_1 + x_2 + x_5 \amp = 56\\
x_1 + 5x_2 + x_6 \amp = 62
\end{align*}
where all variables need to be nonnegative or \(x_1, x_2, x_3, x_4, x_5, x_6 \geq 0\) and the objective function can be written as \(-2x_1 - 7x_2 + z = 0 \)
Next, write these in tableau form.
\begin{equation*}
\left[\begin{array}{rr|rrrrr|r} 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 15\\ 2 \amp 3 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 38\\ 4 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 56\\ 1 \amp 5 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 62\\ \hline -2 \amp -7 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
and then we use Phase II of the Simplex Method. We first check if it is optimal, but since there are negative numbers in the objective (bottom) row, this is not optimal. To determine the pivot note we start with the leftmost negative number in the objective row or column 1 and form the \(\boldsymbol{b}\)-ratio or
1
Recall negative numbers in the objective row mean that if that variable increases, the the objective increases, so it cannot be optimal.
\begin{equation*}
\begin{bmatrix} 15/1 \\ 38/2 \\ 56/4 \\ 62/1 \end{bmatrix} = \begin{bmatrix} 15 \\ 19 \\ 14 \\ 62 \end{bmatrix}
\end{equation*}
and smallest nonnegative above is 14 in the 3rd row. (this corresponds to the \(x_5\) variable). Therefore we perform a matrix pivot on row 3, column 1, which corresponds to the tableau pivot of \(1 \mapsto 5\text{.}\)
\begin{equation*}
\left[\begin{array}{rr|rrrrr|r} 0 \amp 3 \amp 4 \amp 0 \amp -1 \amp 0 \amp 0 \amp 4\\ 0 \amp 10 \amp 0 \amp 4 \amp -2 \amp 0 \amp 0 \amp 40\\ 4 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 56\\ 0 \amp 19 \amp 0 \amp 0 \amp -1 \amp 4 \amp 0 \amp 192\\ \hline 0 \amp -26 \amp 0 \amp 0 \amp 2 \amp 0 \amp 4 \amp 112\\ \end{array} \right]
\end{equation*}
Check if the objective row has negatives and it does in column 2. Again form \(\boldsymbol{b}\)-ratio for this column or
\begin{equation*}
\begin{bmatrix} 4/3 \\ 40/10 \\ 56/1 \\ 192/19 \end{bmatrix} \approx \begin{bmatrix} 1.333 \\ 4 \\ 56 \\ 10.105 \end{bmatrix}
\end{equation*}
and the smallest nonnegative ratio is in the first row, we perform a tableau pivot of \(2 \mapsto 3\text{.}\)
\begin{equation*}
\left[\begin{array}{rr|rrrrr|r} 0 \amp 3 \amp 4 \amp 0 \amp -1 \amp 0 \amp 0 \amp 4\\ 0 \amp 0 \amp -10 \amp 3 \amp 1 \amp 0 \amp 0 \amp 20\\ 3 \amp 0 \amp -1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 41\\ 0 \amp 0 \amp -19 \amp 0 \amp 4 \amp 3 \amp 0 \amp 125\\ \hline 0 \amp 0 \amp 26 \amp 0 \amp -5 \amp 0 \amp 3 \amp 110\\ \end{array} \right]
\end{equation*}
There are still negatives in the objective row, so this is not optimal. The leftmost negative in the objective row is in column 5, so we form \(\boldsymbol{b}\)-ratio for this column or
\begin{equation*}
\begin{bmatrix} 4/(-1) \\ 20/1 \\ 41/1 \\ 125/4 \end{bmatrix} = \begin{bmatrix} -4 \\ 20 \\ 41 \\ 31.125 \end{bmatrix}
\end{equation*}
and the smallest nonnegative value is in row 2, so we will perform a tableau pivot of \(5 \mapsto 4\text{.}\) The new tableau is:
\begin{equation*}
\left[\begin{array}{rr|rrrrr|r} 0 \amp 1 \amp -2 \amp 1 \amp 0 \amp 0 \amp 0 \amp 8\\ 0 \amp 0 \amp -10 \amp 3 \amp 1 \amp 0 \amp 0 \amp 20\\ 1 \amp 0 \amp 3 \amp -1 \amp 0 \amp 0 \amp 0 \amp 7\\ 0 \amp 0 \amp 7 \amp -4 \amp 0 \amp 1 \amp 0 \amp 15\\ \hline 0 \amp 0 \amp -8 \amp 5 \amp 0 \amp 0 \amp 1 \amp 70\\ \end{array} \right]
\end{equation*}
This is still not the optimal solution (there is a negative in the objective row), so again we form \(\boldsymbol{b}\)-ratio for column 3 or
\begin{equation*}
\begin{bmatrix} 8/(-2) \\ 20/(-10) \\ 7/3 \\ 15/7 \end{bmatrix} \approx \begin{bmatrix} -4 \\ -2 \\ 2.3333 \\ 2.143 \end{bmatrix}
\end{equation*}
and the smallest ratio is in row 4. A tableau pivot of \(3 \mapsto 6\) is performed to get:
\begin{equation*}
\left[\begin{array}{rr|rrrrr|r} 0 \amp 7 \amp 0 \amp -1 \amp 0 \amp 2 \amp 0 \amp 86\\ 0 \amp 0 \amp 0 \amp -19 \amp 7 \amp 10 \amp 0 \amp 290\\ 7 \amp 0 \amp 0 \amp 5 \amp 0 \amp -3 \amp 0 \amp 4\\ 0 \amp 0 \amp 7 \amp -4 \amp 0 \amp 1 \amp 0 \amp 15\\ \hline 0 \amp 0 \amp 0 \amp 3 \amp 0 \amp 8 \amp 7 \amp 610\\ \end{array} \right]
\end{equation*}
And now the tableau is in optimal form—there are no negatives in the objective row. The basic solution for this is
\begin{equation*}
\boldsymbol{x} = \frac{1}{7} \left[ \begin{array}{rr|rrrr} 4 \amp 86 \amp 15 \amp 0 \amp 290 \amp 0 \end{array}\right]^{\intercal}
\end{equation*}
resulting the objective of \(610/7\text{.}\)
