Section 5.6 Using the SimplexTableau package in Julia
In Section 3.2, we introduced the Simplex Tableau method for solving linear optimization problems. In this section, we will see how to implement the Simplex Tableau method using the SimplexTableau package in Julia.
To get started, you will need to install the
SimplexTableau package. This is a package written by Dr. Peter Staab, the author of this book. The format of the package is similar to that of the textbook, so it should be easy to follow along. Download the package and place the file in a folder where you intend to work. Then, in Julia, you can include the package using the following command:
include("SimplexTableau.jl")
using .SimplexTableau
Subsection 5.6.1 Entering Tableaus
We first start by entering a tableau. For example, let’s look at Problem 2.2.2 which is put into a tableau in Section 3.2. Enter the code below to create the tableau in Julia:
t = Tableau([4 3 1 0 0 0 120
1 2 0 1 0 0 40
0 1 0 0 1 0 16;
-1 -3 0 0 0 1 0])
The result is the following:
\begin{equation*}
\begin{aligned} A \amp = \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] \\ ~ \amp \\ d \amp = 1 \qquad \pi = \{1, 2\} \qquad \beta = \{3, 4, 5\} \end{aligned}
\end{equation*}
which clearly shows the simplex tableau, but also the value \(d\text{,}\) the basic variable, the basis \(\beta\) and non-basis \(\pi\text{.}\)
Alternatively, if one defines the LOP in matrix form, such as
A = [4 3; 1 2; 0 1]
b = [120; 40; 16]
c= [1; 3]
Then create the tableau with
Tableau(A, b, c)
And that results in the same tableau.
Subsection 5.6.2 Pivoting with the SimplexTableau Package
The most-used step in the Simplex method is that of a pivot. The
pivot command in the SimplexTableau package allows you to perform a pivot operation in a fraction-free way that we had always done in the book. For the pivot we use the form i => j where i is the entering variable and j is the leaving variable.
t1 = pivot(t, 1 => 3)
results in
\begin{equation*}
\begin{aligned} A \amp = \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] \\ ~ \amp \\ d \amp = 4 \qquad \pi = \{2, 3\} \qquad \beta = \{1, 4, 5\} \end{aligned}
\end{equation*}
Notice that the basis \(\beta\) reflects the fact that \(x_1\) is now in the basis and \(x_3\) has left. Let’s do the next step with
t2 = pivot(t1, 2 => 4)
resulting in
\begin{equation*}
\begin{aligned} A \amp = \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] \\ ~ \amp \\ d \amp = 5 \qquad \pi = \{3, 4\} \qquad \beta = \{1, 2, 5\} \end{aligned}
\end{equation*}
This is still not optimal, so one more step with
t3 = pivot(t2, 3 => 5) results in
\begin{equation*}
\begin{aligned} A \amp = \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] \\ ~ \amp \\ d \amp = 1 \qquad \pi = \{4, 5\} \qquad \beta = \{1, 2, 3\} \end{aligned}
\end{equation*}
Note that all three of these steps can be combined with one step:
pivot(t, [1 => 3, 2 => 4, 3 => 5])
and the result is the same as above. Note: Although this can do multiple steps, this is often only when it is known what steps to do. When performing phase I or phase II, decisions are needed at each step.
Subsection 5.6.3 Phase I and Phase II using SimplexTableau in Julia
The above steps are those used in both phase I and phase II of the simplex method. The
phaseII function can be used to perform phase II directly on a tableau that is already feasible. For example, using the tableau t from above,
t_opt = phaseII(t)
returns
\begin{equation*}
\begin{aligned} A \amp = \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] \\ ~ \amp \\ d \amp = 1 \qquad \pi = \{4, 5\} \qquad \beta = \{1, 2, 3\} \end{aligned}
\end{equation*}
which is the optimal tableau as found above with the individual pivot steps. If we want to see the steps/pivots, we can add the optional argument
show_steps = true:t_opt = phaseII(t, show_steps = true)
which results in
\begin{equation*}
\begin{aligned} \text{Initial Tableau} \qquad \amp \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] \\ d \amp = 1 \qquad \pi = \{1, 2\} \qquad \beta = \{3, 4, 5\} \\ \text{pivots} \qquad \amp 1 \mapsto 3, 2 \mapsto 4, 3 \mapsto 5 \\ ~ \amp \\\text{Final Tableau} \qquad \amp \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] \\ d \amp = 1 \qquad \pi = \{4, 5\} \qquad \beta = \{1, 2, 3\} \\ \text{Completed} \qquad \amp true \\ \text{Message} \qquad \amp \end{aligned}
\end{equation*}
A phase I example, is the following. Consider the LOP in Problem 3.3.1. This can be entered into a tableau in Julia as
t1 = Tableau([-2 1; -2 -1; -1 -1],[6 ; -12; -8],[-3; -2])
and then can be solved with
phaseI(t1), which results in
\begin{equation*}
\begin{aligned} A \amp = \left[ \begin{array}{rr|rrrr|r} 0 \amp 0 \amp 1 \amp -3 \amp 4 \amp 0 \amp 10\\ 1 \amp 0 \amp 0 \amp -1 \amp 1 \amp 0 \amp 4\\ 0 \amp 1 \amp 0 \amp 1 \amp -2 \amp 0 \amp 4 \\ \hline 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp -20 \end{array}\right] \\ ~ \amp \\ d \amp = 1 \qquad \pi = \{4, 5\} \qquad \beta = \{1, 2, 3\} \end{aligned}
\end{equation*}
If the optional argument
show_steps = true is added, then the steps of phase I are also shown.
\begin{equation*}
\begin{aligned} \text{Initial Tableau} \qquad \amp \left[ \begin{array}{rr|rrrr|r} -2 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 6\\ -2 \amp -1 \amp 0 \amp 1 \amp 0 \amp 0 \amp -12\\ -1 \amp -1 \amp 0 \amp 0 \amp 1 \amp 0 \amp -8 \\ \hline 3 \amp 2 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \end{array}\right] \\ d \amp = 1 \qquad \pi = \{1, 2\} \qquad \beta = \{3, 4, 5\} \\ \text{pivots} \qquad \amp 1 \mapsto 3, 2 \mapsto 3 \\ ~ \amp \\\text{Final Tableau} \qquad \amp \left[ \begin{array}{rr|rrrr|r} 0 \amp 0 \amp 1 \amp -3 \amp 4 \amp 0 \amp 10\\ 1 \amp 0 \amp 0 \amp -1 \amp 1 \amp 0 \amp 4\\ 0 \amp 1 \amp 0 \amp 1 \amp -2 \amp 0 \amp 4 \\ \hline 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp -20 \end{array}\right] \\ d \amp = 1 \qquad \pi = \{4, 5\} \qquad \beta = \{1, 2, 3\} \\ \text{Completed} \qquad \amp true \\ \text{Message} \qquad \amp \end{aligned}
\end{equation*}
