Consider Problem 2.1.2, in which coffee is shipped from warehouses to retail outlets. The problem was set up as an LOP in Problem 2.1.8 and we can use the techniques from the Section 3.2 to write this as a tableau.
First, as discussed in Subsection 2.2.2, we need to write this problem in standard form, which means switching two of the inequalities by negating them. Also, the objective needs to be written as a maximum. The LOP in standard maximum form is
Typically, we look at the objective row to determine if a tableau is optimal and the there are no negatives in this row, so it appears it is optimal. The basic solution of (3.3.2) is
and there are negatives in the solution, which implies that this is an infeasible basic solution. We need to perform some pivots to get a basic solution to be feasible first. This is what is called Phase I of the Simplex Method. We will use a simpler problem to develop this.
Figure3.3.2.A plot of the feasible set from Problem 3.3.1 . The boundary lines (where the slack variables are each 0) are labelled with the slack variables. Also, all the intersection points between the slack variables are also labelled.
As with phase II, we will perform a pivot to move variables in and out of the basis. Instead of just looking at the standard algorithm, let’s look at the feasible set and make some determinations.
First, the standard first step from phase II is to determine the entering variable, which could be discovered by using the objective function and determining which was the lowest indexed variable that would increase the value of the objective function.
We aren’t concerned yet about the objective function. We just need to find a feasible solution. In this case, finding the leaving variable is generally a better first step. The leaving variable would bring the current vertex to along it’s line. This would mean that we would select between \(y_3\text{,}\)\(y_4\) and \(y_5\) on which variable to leave—using the feasible set in Figure 3.3.2, that means selecting one of the variables that form the boundary of the feasible set. \(F\text{.}\)
Before selecting the pivot variables, let’s look at the dictionary for this problem. If we introduce slack variables then in Dictionary form in the same way as that in Section 3.1, then
And note that the two variables that do not satisfy the nonnegative condition is \(y_4\) and \(y_5\text{.}\) The goal is to select a basis that is feasible and therefore either \(y_4\) or \(y_5\) will be selected as the leaving variable and this means that upon pivoting will either go to these lines on the feasible set.
Note that a pivot will be to solve for a variable entering the basis in one of the equations. This is then used in the other solutions. The hope would be that the new dictionary or tableau is feasible. Thus, selecting the most negative number, since when a variable is solved for, that value will become positive and perhaps lead to all other basic variable being solved for.
In this case, we can solve for either \(2y_1\) or \(y_2\) and in either case, the result will be a positive value for either of these. These correspond to either \(1 \mapsto 4\) or \(2 \mapsto 4\text{.}\)
Without further analysis, it’s hard to say which to choose. And think if we had 10s or 100s of parameters to choose from. If we did calculations to help determine the “best”, it may be expensive to compute. Because of this, we will choose the entering variable to be the negative parameter with lowest index.
Select the row of the tableau with the most negative basic variable and call this row \(i\text{.}\) The basic variable in row \(i\) is the leaving variable and denote this variable \(k\text{.}\)
And to start phase I, we note that the largest negative in the \(\boldsymbol{b}\)-column is in the second row. This will be the leaving variable and is \(y_4\text{.}\) To select the entering variable, select the negative parameter with the smallest index in row 2. This occurs in column 1, so \(y_1\) is the entering variable. Now perform a pivot.
This tableau is still infeasible. Note the basic solution for \(y_5\) is \(-4\) so this is the leaving variable. To determine the entering variable, find the leftmost negative parameter in row 3. This is \(y_2\) and we pivot:
This tableau is feasible in that all variables are now nonnegative. Notice that in Figure 3.3.2 this tableau corresponds to the vertex \(E\text{.}\) This completes phase I of the simplex method.
with \(z = -20\text{.}\) This corresponds to the original problem as \(w = -z = 20\text{,}\) so the function is minimized when \(x_1=4\) and \(x_2 = 4\text{.}\)
We use phase I of the Simplex Method because there are negatives in the last column. This occurs in row 2 and the corresponding leaving variable is \(x_4\text{.}\) To determine the entering variable, we select the leftmost (lowest indexed) of the parameters with negative values or \(x_1\text{.}\) Thus pivot:
There are still negatives in the last column. This time it is in row 3 and will select its corresponding variable, \(x_5\) as the leaving variable. The leftmost negative parameter is in column 2, so \(x_2\) will be the entering variable and we perform the pivot:
For phase II, we first look in the objective row of the tableau and note that because there are negative numbers so the basic solution is not optimal. We start with the leftmost negative in the objective row or the fourth column, so \(x_4\) is the entering variable. Then form the \(\boldsymbol{b}\)-ratios.
and noting that the only positive number here is in the first row. The basic variable in the first row is \(x_3\text{,}\) so this is the leaving variable. Perform the pivot
Figure3.3.6.A plot of the feasible set for the LOP in Problem 3.3.4 . The sides of the lines not in the feasible set are crossed out. The resulting feasible set is the triangle \(CEG\text{.}\)
And recall that the shaded side of the lines are the infeasible sides, meaning that the triangular region \(CEG\) is the feasible set. When the simplex method starts (either under phase I or II), the initial point is always the origin. In this particular case, the only variable that is infeasible is \(x_4\text{,}\) which is what we see in (3.3.4), in that the negative number in the left column corresponds to \(x_4\text{.}\)
The first step moved the basic variable from the origin to the point \(x_1=15, x_2=0\text{,}\) which is point \(A\text{.}\) However, note that this is still infeasible. From the plot you can see that the side to the right of \(x_5=0\) is infeasible. This can also be seen in (3.3.5) in that the negative number in the left column corresponds to the basic variable \(x_5\text{.}\)
Even though it appears that we have all of the bases covered, there are a couple of spots in the simplex method that can go wrong. Although these are eluded to while developing this method, the following section will cover these cases.
