Objectives
-
Understand how to write a general LOP in standard form.
-
Adapt the simplex method to handle equality constraints and free variables.
-
Develop additional steps to the simplex method to handle equality constraints and free variables.
Section 7.1 General Form of an LOP
Throughout this book, we have seen linear problems with many different types of linear constraints. This however, is not the most general types of problems we can handle. This chapter goes into adding linear equality constraints as well as cases when variables lose the non-negative constraint, which is crucial to getting the simplex method to solve correctly.
Subsection 7.1.1 Writing a General LOP in Standard Form
Consider the LOP:
Problem 7.1.1.
\begin{equation}
\begin{aligned} \text{maximize} \amp\amp z=5x_1+3x_2, \amp \\ \text{subject to} \amp\amp x_1 + x_2 \amp\leq 6, \\ \amp\amp 2x_1 - 3x_2 \amp\leq 12, \\ \amp\amp -2x_1 +x_2 \amp = -2, \\ \amp\amp x_1 \amp \geq 0.
\end{aligned}\tag{7.1.1}
\end{equation}
A graph of the feasible set is
Note that in Problem 7.1.1 the third constraint is an equality constraint and the second variable, \(x_2\text{,}\) does not have a nonnegative constraint. We will see how to handle these cases in this section.
The solution needs to be on both on the line (in red) as well as in the gray triangular region. A keen observation would notice that in the upper right direction along the line increases the objective function, so the solution must be at the intersection of the red line and the upper boundary of the triangle. However as problems get more complicated, arguments like this will not work and we will adapt the simplex method to solve this in general.
We can put this problem in standard form for both the equality constraint as well as the lack of nonnegative constraint on the variable. First, the equality as the third constraint in (7.1.1) can be written as two inequalities.
\begin{align*}
-2 x_1 + x_2 \amp \leq -2 \\
-2 x_1 + x_2 \amp \geq -2
\end{align*}
and the set of points that satisfy both of these is the line.
The lack of nonnegative constraint on \(x_2\) in Problem 7.1.1 can be written by introducing two new variables, \(x_2^+\) and \(x_2^-\text{,}\) then rewriting \(x_2 = x_2^+-x_2^-\text{,}\) where \(x_2^+ \geq 0\) and \(x_2^- \geq 0\text{.}\) Basically this is saying that a variable with no constraints can be the difference of two nonnegative variables. The new version of Problem 7.1.1 can be written
Problem 7.1.3.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp\amp z = 5x_1 +3(x_2^+ - x_2^-) \amp \\ \text{subject to} \amp\amp x_1 + x_2^+ - x_2^- \amp \leq 6, \\ \amp\amp 2x_1 -3(x_2^+ - x_2^-) \amp \leq 12, \\ \amp\amp -2x_1 + x_2^+ - x_2^- \amp\leq -2, \\ \amp\amp 2x_1 - (x_2^+ - x_2^-) \amp \leq 2, \\ \text{and}\amp\amp x_1, x_2^+, x_2^- \amp \geq 0.
\end{aligned}
\end{equation*}
with the updated inequality constraints and the introduction of the new variables, this is now in standard form and can be solved using the standard simplex method:
\begin{equation*}
\left[\begin{array}{rrr|rrrrr|r} 1 \amp 1 \amp -1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6\\ 2 \amp -3 \amp 3 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 12\\ -2 \amp 1 \amp -1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -2\\ 2 \amp -1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 2\\ \hline -5 \amp -3 \amp 3 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
where the first three columns are labelled \(x_1, x_2^+, x_2^-\) and the slack variables are \(x_3,x_4,x_5,x_6\text{.}\)
To solve this, we perform the standard simplex method.
\begin{equation*}
\begin{array}{r} x_5 \mapsto x_1, \\ x_3 \mapsto x_2^+ \\ x_6 \mapsto x_5, \end{array} \qquad \left[\begin{array}{rrr|rrrrr|r} 0 \amp 3 \amp -3 \amp 2 \amp 0 \amp 0 \amp -1 \amp 0 \amp 10\\ 0 \amp 0 \amp 0 \amp 4 \amp 3 \amp 0 \amp -5 \amp 0 \amp 50\\ 3 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 8\\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 3 \amp 3 \amp 0 \amp 0\\ \hline 0 \amp 0 \amp 0 \amp 11 \amp 0 \amp 0 \amp 2 \amp 3 \amp 70\\ \end{array} \right]
\end{equation*}
which is optimal now. The solution is
\begin{equation*}
\boldsymbol{x} = \frac{1}{3} \left[\begin{array}{rrr|rrrr} 8 \amp 10 \amp 0 \amp 0 \amp 50 \amp 0 \amp 0 \end{array}\right]
\end{equation*}
which translates back to the original variables as
\begin{equation*}
\begin{aligned} x_1 \amp = \frac{8}{3} \amp x_2 \amp = x_2^{+} - x_2^- = \frac{10}{3} - 0 = \frac{10}{3}\end{aligned}
\end{equation*}
with the objective function of \(z= 70/3\text{.}\)
This technique will work for both equality constraints as well as free variables. However, for each equality constraint it introduces another constraint (extra row in the tableau) for each free variable, there is a new variable (extra column in the tableau). Now we will see how to adapt the original simplex tableau and method to directly handle these.
Subsection 7.1.2 Adapting the Simplex Method to Equality Constraints and Free Variables
Let’s return to Problem 7.1.1 that we saw at the top of this section. We will now try to determine a solution without introducing new constraints or variables other than slack variables. To do this, recall that underlying the simplex method is the dictionary. If we write the objective function and constraints with a slack variables as
\begin{equation}
\begin{aligned} \text{Maximize} \amp \amp z \amp = 5x_1 + 3x_2, \\ \text{such that} \amp \amp x_3 \amp = 6 - x_1 -x_2 \\ \amp \amp x_4 \amp = 12-2x_1+3x_2 \\ \amp \amp0 \amp = -2 + 2x_1 -x_2 \\ \text{and} \amp \amp x_1, x_3, x_4 \amp \geq 0 \end{aligned}\tag{7.1.2}
\end{equation}
and again notice that \(x_2\) is missing from the nonnegative constraint and the equality constraint does not have a slack variable. Also, the parameters are \(x_1, x_2\) or \(\pi = \{1,2\}\) and therefore the basic variables are \(\beta=\{3,4\}\text{.}\)
Note that this has a basic solution of \(x_1=0, x_2 = 0, x_3 = 6, x_4 = 12\text{,}\) so it is feasible, so we perform a pivot to increase the objective function. As before, we will select \(x_1\text{,}\) which is the smaller index of the parameters that will increase the objective, to enter the basis.
Previously, we would select a basic variable to leave the basis, however, since we have an equality constraint, we will not do that. It may seem arbitrary to choose either parameter, however, we eventually need to get all free variables into the basis and selecting to bring a free variable is done for efficiency. Therefore \(x_2 = -2+2x_1\) and then substitute this into the other equations in (7.1.2)
\begin{equation}
\begin{aligned} \text{Maximize} \amp \amp z \amp = 5x_1 + 3(-2+2x_1) = -6 + 11 x_1 \\ \text{such that} \amp \amp x_3 \amp = 6 - x_1 - (-2 +2x_1) = 8 - 3x_1 \\ \amp \amp x_4 \amp = 12 - 2x_1 + 3(-2 + 2x_1) = 6 + 4x_1 \\ \amp \amp x_2 \amp = -2 + 2 x_1.
\end{aligned}\tag{7.1.3}
\end{equation}
Notice that the basic solution to this is \(x_1 = 0, x_2 = -2, x_3 = 6, x_4 = 12\) and that there is now only 1 parameter so \(\pi = \{1\}\) and the basis is \(\beta = \{2,3,4\}\text{.}\) We will denote a tableau pivot of this form as \(2 \mapsto \emptyset\text{.}\)
One may also cringe a bit with a negative number in the basic solution (although we could take care of that in phase I), however since \(x_2\) is a free variable this is a feasible solution.
Examining the objective function in the dictionary, note that increasing \(x_1\) will increase the objective, so we perform another pivot to bring \(x_1\) into the basis. To select the variable to leave the basis, we typically use an argument to increase the objective without making the result infeasible. This is still true, however, it is important that the free variable \(x_2\) does not leave the basis. Therefore we need to either select \(x_3\) or \(x_4\text{.}\)
We’ll use the same argument as before in Phase II except don’t include \(x_2\) in the possible list. If we select \(x_4\) to leave, then \(x_1\) would be negative, so we will select \(x_3\) to leave or the tableau pivot of \(1 \mapsto 3\text{.}\) This results in \(3x_1 = 8- x_3\text{.}\)
We will place this in the dictionary (multiplying each row by 3) to get
\begin{equation*}
\begin{aligned} \text{Maximize} \amp \amp 3z \amp = -18 + 11 (3x_1) = - 18 + 11(8-x_3) = 70 - 11 x_3 \\ \text{such that} \amp \amp 3x_2 \amp = 24 - (8-x_3) = 16 + x_3 \\ \amp \amp 3x_4 \amp = 18 + 4 (3x_1) = 18 + 4 (8-x_3) = 50 - 4 x_3 \\ \amp \amp 3x_1 \amp = 8 - x_3 \end{aligned}
\end{equation*}
This now has the basic solution:
\begin{equation*}
x_1 = \frac{8}{3}, x_2 = \frac{10}{3}, x_3 = 0, x_4 = \frac{50}{3}
\end{equation*}
and objective value of \(z=70/3\text{.}\) This is the same solution that we found in Subsection 7.1.1.
The steps to work with free variables and equality constraints will be called Phase 0 of the Simplex Method. We will see this same example with a tableau in the next section.
Subsection 7.1.3 Simplex Method: Phase 0
We knew from before that using the dictionary to find optimal solutions to LOPs is helpful in understanding, but difficult in performing the arithmetic. In this section, we adapt the steps above to a simplex tableau.
Let’s return to Problem 7.1.1 and write down the simplex tableau if we keep the inequality constraint without a slack variable as in
\begin{align*}
\amp\begin{array}{rrrrrr}\phantom{11}\amp\phantom{1}\amp F \end{array}\\
\amp\left[\begin{array}{rr|rrr|r} 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 6\\ 2 \amp -3 \amp 0 \amp 1 \amp 0 \amp 12\\ -2 \amp 1 \amp 0 \amp 0 \amp 0 \amp -2\\ \hline -5 \amp -3 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{align*}
There are two things to note with this. First, the 2nd column has an \(F\) above it. This indicates that the 2nd variable is a free variable. Secondly, the 3rd row has no slack variable.
Above, the first step of the solution was to bring \(x_2\) into the basis. We will use the notation \(2 \mapsto \emptyset\) where \(\emptyset\) indicates that nothing leaves the basic. This results in a matrix pivot about row 3, column 1.
\begin{equation*}
2 \mapsto \emptyset \qquad \left[\begin{array}{rr|rrr|r} 3 \amp 0 \amp 1 \amp 0 \amp 0 \amp 8\\ -4 \amp 0 \amp 0 \amp 1 \amp 0 \amp 6\\ -2 \amp 1 \amp 0 \amp 0 \amp 0 \amp -2\\ \hline -11 \amp 0 \amp 0 \amp 0 \amp 1 \amp -6\\ \end{array} \right].
\end{equation*}
Note that the 3rd row is still an inequality and this is the tableau version of (7.1.3) with the same basic solution of
\begin{equation*}
\boldsymbol{x} = \left[\begin{array}{rr|rr} 0 \amp -2 \amp 8 \amp 6 \end{array}\right]
\end{equation*}
and note that since \(x_2\) is a free variable that this is a feasible solution. Now that all of the free variables are in the basis and the equality constraint is written in terms of a basis variable that this is out of phase 0.
Also, since all of the variables are feasible, we do not need to perform any phase 1 pivots. Let’s move to phase 2.
As previous, we select column 1 to create the \(\boldsymbol{b}\)-ratios to bring \(x_1\) into the basis. Since \(x_2\) is a free variable, when selecting the pivot, do not remove this from the basis. Only removing \(x_3\) from the basis will accomplish our tasks.
\begin{equation}
1 \mapsto 3, \qquad \left[\begin{array}{rr|rrr|r} 3 \amp 0 \amp 1 \amp 0 \amp 0 \amp 8\\ 0 \amp 0 \amp 4 \amp 3 \amp 0 \amp 50\\ 0 \amp 3 \amp 2 \amp 0 \amp 0 \amp 10\\ \hline 0 \amp 0 \amp 11 \amp 0 \amp 3 \amp 70\\ \end{array} \right]\tag{7.1.4}
\end{equation}
The solution to this is the same as using the dictionary or
\begin{equation*}
\boldsymbol{x} = \frac{1}{3}\left[\begin{array}{rr|rr} 8 \amp 10 \amp 0 \amp 50 \end{array}\right]
\end{equation*}
Checkpoint 7.1.4.
Find the solution to the following LOP using the steps in Phase 0 of the simplex method.
Problem 7.1.5.
\begin{equation*}
\begin{aligned} \text{Minimize} \amp\amp w = 5x_1 + x_2,\amp \\ \text{subject to} \amp\amp x_1 + x_2 \amp\leq 5, \\ \amp\amp 2x_1 - x_2 \amp\leq 1, \\ \amp\amp x_1 - x_2 \amp \geq -4, \\ \amp\amp x_1 + 2x_2 \amp = 6, \\ \text{and} \amp\amp x_2 \amp \geq 0.
\end{aligned}
\end{equation*}
Solution.
The first step is to write the problem in standard form, so the third constraint is written as \(-x_1+x_2 \leq 4\) and the objective function is written as \(z = -5x_1-x_2\) then the simplex tableau can be
\begin{align*}
\amp\begin{array}{rrrrrr}\amp \phantom{1} F \end{array}\\
\amp\left[\begin{array}{rr|rrrr|r} 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 5\\ 2 \amp -1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1\\ -1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 4\\ 1 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6\\ \hline 5 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{align*}
Since \(x_1\) is a free variable, but is not in the basis, Phase 0 needs to be performed with
\begin{align*}
\amp\begin{array}{rrrrrr}\phantom{11} F \end{array}\\
1 \mapsto \emptyset, \qquad \amp \left[\begin{array}{rr|rrrr|r} 0 \amp -1 \amp 1 \amp 0 \amp 0 \amp 0 \amp -1\\ 0 \amp -5 \amp 0 \amp 1 \amp 0 \amp 0 \amp -11\\ 1 \amp 2 \amp 0 \amp 0 \amp 0 \amp 0 \amp 6\\ 0 \amp 3 \amp 0 \amp 0 \amp 1 \amp 0 \amp 10\\ \hline 0 \amp -9 \amp 0 \amp 0 \amp 0 \amp 1 \amp -30\\ \end{array} \right]
\end{align*}
This is not feasible, so we are in Phase I. The following steps will create a feasible tableau:
\begin{align*}
\amp\begin{array}{rrrrrr}\phantom{11} F \end{array}\\
\begin{array}{r} 2 \mapsto 4, \end{array} \qquad \amp \left[\begin{array}{rr|rrrr|r} 0 \amp 0 \amp 5 \amp -1 \amp 0 \amp 0 \amp 6\\ 0 \amp 5 \amp 0 \amp -1 \amp 0 \amp 0 \amp 11\\ 0 \amp 0 \amp 0 \amp 3 \amp 5 \amp 0 \amp 17\\ 5 \amp 0 \amp 0 \amp 2 \amp 0 \amp 0 \amp 8\\ \hline 0 \amp 0 \amp 0 \amp -9 \amp 0 \amp 5 \amp -51\\ \end{array} \right]
\end{align*}
And this is feasible now, however it is not optimal, so continue with Phase II. If we find \(\boldsymbol{b}\)-ratios with the 4th column, we get
\begin{equation*}
\begin{bmatrix} 6/(-1) \\ 11/(-1) \\ 17/3 \\ 8/2 \end{bmatrix} \approx \begin{bmatrix} -6 \\ -11 \\ 5.67 \\ 4 \end{bmatrix}
\end{equation*}
Normally, we would choose the 4th row because it is the smallest nonnegative ratio, however, this corresponds to \(x_1\) which is a free variable and cannot remove it from the basis. Therefore we will choose the 3rd row, corresponding to \(x_5\) to leave the basis.
\begin{align*}
\amp\begin{array}{rrrrrr}\phantom{11} F \end{array}\\
4 \mapsto 5, \qquad \amp\left[\begin{array}{rr|rrrr|r} 0 \amp 0 \amp 3 \amp 0 \amp 1 \amp 0 \amp 7\\ 0 \amp 3 \amp 0 \amp 0 \amp 1 \amp 0 \amp 10\\ 0 \amp 0 \amp 0 \amp 3 \amp 5 \amp 0 \amp 17\\ 3 \amp 0 \amp 0 \amp 0 \amp -2 \amp 0 \amp -2\\ \hline 0 \amp 0 \amp 0 \amp 0 \amp 9 \amp 3 \amp 0\\ \end{array} \right]
\end{align*}
and this solution is now optimal with the basic solution
\begin{equation*}
\boldsymbol{x} = \frac{1}{3} \left[\begin{array}{rr|rrrr} -2 \amp 10 \amp 7 \amp 17 \amp 0\end{array}\right].
\end{equation*}
and recall that since \(x_1\) is a free variable, it can take on any value, so the negative number is not a problem.
Subsection 7.1.4 Geometry of Phase 0
As noted in previous sections, understanding the geometry of the simplex method is important to understanding how the algorithm works. Let’s look at the example shown above in Subsection 7.1.1 and see how the geometry of the solution changes with the introduction of free variables and equality constraints.
To begin with, revisit Figure 7.1.2 and note that the first step of the simplex method for any problem starts at the origin. The next step way a pivot to bring \(x_2\) into the basis, which is shown in Figure 7.1.2 as the point \((0,-2)\text{.}\) Note that this is a feasible point (clear from the diagram), but since \(x_2\) is a free variable, it can take on any value.
The next pivot was to bring \(x_1\) into the basis, which is shown in Figure 7.1.2 as the point \((8/3,10/3)\text{.}\)
Checkpoint 7.1.6.
Plot the feasible set from Problem 7.1.5 and on the plot show the location of the basic solution at each step.
Solution.
From Checkpoint 7.1.4, the basic variables at each step are
-
\(\displaystyle (0,0)\)
-
\(\displaystyle (6,0)\)
-
\(\displaystyle (8/5, 11/5)\)
-
\(\displaystyle (-2/3, 10/3)\)
Some commentary on the results is helpful. As mentioned throughout this text, the first step is always at the origin, which is shown in the figure as \((0,0)\text{.}\) The next step is to bring \(x_1\text{,}\) the free variable into the basis and because there is a linear constraint, the next step is where the free variable or \(x_1\) intersects the line \(x_1 + 2x_2 = 6\text{.}\) This may seem strange because the origin was in the feasible set and this first step is not infeasible. However, phase 0 is always to bring free variables into the basis when emphasis on doing this with equality constraints.
Since the point \(\boldsymbol{x}^{(1)}\) is outside the feasible set, this point (basic solution of the tableau) is in Phase I. We need to make it feasible, so \(\boldsymbol{x}^{(2)}\) is the first point on the linear constraint that is inside the feasible set.
The last step is Phase II because the basic solution is feasible and the objective function is not optimal. To increase the objective takes the last point to \(\boldsymbol{x}^{(3)}\text{,}\) at which the tableau is optimal.
