Summary of the Simplex Method

Section 3.5 Summary of the Simplex Method

This section lists the details of the full Simplex Method that we have developed in this chapter.

Write the LOP in standard form as shown in Subsection 2.2.2. Note: if each the variables do not have the non-negative constraint, there are techniques in Chapter 7 to handle these situations.
🔗

🔗
From the LOP in standard form, write down the tableau as shown in Subsection 3.2.1.
🔗

🔗
Phase I (details in Algorithm 3.3.3)
🔗
1. If there are no negatives in the last column, the tableau is already feasible and move to Phase II in Step 4.
  🔗
  
  🔗
2. Find the row with the largest negative in the last column. Denote this as row \(i\) and the last number is \(b_i\text{.}\) The basic variable associated with this row is the leaving variable. Denote it \(x_{k}\text{.}\)
  🔗
  
  Find the leftmost negative parameter (that one with the smallest index) in the row. The column where this takes place will be column \(j\) and thus the entering variable will be \(x_j\text{.}\)
  🔗
  
  If there are no negative parameter in row \(i\text{,}\) then the tableau and thus the LOP is infeasible. Exit the algorithm.
  🔗
  
  🔗
3. Perform the pivot \(j \mapsto k\text{.}\) Return to Step 3.
  🔗
  
  🔗
🔗
🔗
Phase II (details in Algorithm 3.2.2).
🔗
1. If there are no negative numbers in the objective row (ignoring the last column), the tableau is optimal. Goto step 5.
  🔗
  
  🔗
2. Select the leftmost negative number in the objective row (again, not including the last column). Call this column \(j\) and \(x_j\) will be the entering variable.
  🔗
  
  🔗
3. Calculate the \(\boldsymbol{b}\)-ratios of the last column to column \(j\text{.}\) Call \(i\) the row/element with the smallest nonnegative ratio. Denote the basic variable in row \(i\text{,}\) \(x_k\) and this will be the leaving variable.
  🔗
  
  If there are no nonnegative ratios, then the problem is unbounded. Stop the algorithm.
  🔗
  
  🔗
4. Perform the pivot \(j \mapsto k\) and return to Step 4.
  🔗
  
  🔗
🔗
🔗
The solution is optimal. Write down the basic solution and objective value from the tableau.
🔗

🔗

In previous sections, the geometry of the simplex method was shown through many examples, however these mainly confined to problems with two original variables such that the feasible set was easy to plot. To thoroughly understand the Simplex Method, one should understand the underlying geometry of these examples.

🔗

To finish this section, two more problems are solved completely with the Simplex Method using the steps above.

🔗

Problem 3.5.1.

\begin{equation*} \begin{aligned} \text{Minimize} \amp \amp w = 5 x_1 + 2 x_2 + 4 x_3, \amp \\ \text{subject to} \amp \amp 4 x_1 + 5 x_2 + 3 x_3 \amp \geq 60, \\ \amp \amp 3 x_1 - 4x_2 +2 x_3 \amp \leq 48, \\ \amp \amp -x_1 + x_2 + 2x_3 \amp \leq 24, \\ \amp \amp x_2 \amp \geq 8, \\ \amp \amp x_1, x_2, x_3 \amp \geq 0. \end{aligned} \end{equation*}

🔗

Solution.

The first step is to put the problem in standard form, which means in this case to change to a maximum problem and then change the first and fourth inequalities.

🔗

\begin{equation*} \begin{aligned} \text{Maximize} \amp \amp z = -5 x_1 - 2 x_2 - 4 x_3, \amp \\ \text{subject to} \amp \amp -4 x_1 - 5 x_2 - 3 x_3 \amp \leq -60, \\ \amp \amp 3 x_1 - 4x_2 +2 x_3 \amp \leq 48, \\ \amp \amp -x_1 + x_2 + 2x_3 \amp \leq 24, \\ \amp \amp -x_2 \amp \leq -8, \\ \amp \amp x_1, x_2, x_3 \amp \geq 0. \end{aligned} \end{equation*}

🔗

Next, this is put into the simplex tableau:

🔗

\begin{equation*} \left[\begin{array}{rrr|rrrrr|r} -4 \amp -5 \amp -3 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp -60\\ 3 \amp -4 \amp 2 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 48\\ -1 \amp 1 \amp 2 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 24\\ 0 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp -8\\ \hline 5 \amp 2 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right] . \end{equation*}

🔗

Looking at the tableau, there are negatives in the last column, so this is phase I. We start with the most negative row (row 1) and note that the leftmost negative parameter occurs in column 3, thus we choose \(x_1\) to enter the basis and since the current basis variable in row 1 is \(x_4\) and thus

🔗

\begin{equation*} 1 \mapsto 4, \qquad \left[\begin{array}{rrr|rrrrr|r} 4 \amp 5 \amp 3 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 60\\ 0 \amp -31 \amp -1 \amp 3 \amp 4 \amp 0 \amp 0 \amp 0 \amp 12\\ 0 \amp 9 \amp 11 \amp -1 \amp 0 \amp 4 \amp 0 \amp 0 \amp 156\\ 0 \amp -4 \amp 0 \amp 0 \amp 0 \amp 0 \amp 4 \amp 0 \amp -32\\ \hline 0 \amp -17 \amp 1 \amp 5 \amp 0 \amp 0 \amp 0 \amp 4 \amp -300\\ \end{array} \right] . \end{equation*}

🔗

There are still negatives in the last column, so this is still phase I. The most negative value is in row 4 and the leftmost negative parameter in this row is in column 2. Thus \(x_2\) enters the basis and the basic variable in row 4 is \(x_7\) so the pivot will give

🔗

\begin{equation*} 2 \mapsto 7, \qquad \left[\begin{array}{rrr|rrrrr|r} 4 \amp 0 \amp 3 \amp -1 \amp 0 \amp 0 \amp 5 \amp 0 \amp 20\\ 0 \amp 0 \amp -1 \amp 3 \amp 4 \amp 0 \amp -31 \amp 0 \amp 260\\ 0 \amp 0 \amp 11 \amp -1 \amp 0 \amp 4 \amp 9 \amp 0 \amp 84\\ 0 \amp 4 \amp 0 \amp 0 \amp 0 \amp 0 \amp -4 \amp 0 \amp 32\\ \hline 0 \amp 0 \amp 1 \amp 5 \amp 0 \amp 0 \amp -17 \amp 4 \amp -164\\ \end{array} \right] \end{equation*}

🔗

There are no remaining negatives in the last column, so we have moved out of phase I. Phase II starts will determining if there are negatives in the objective row and there are.

🔗

For this phase, the entering variable is the leftmost negative in the objective row or \(x_7\text{.}\) The leaving variable is determined by \(\boldsymbol{b}\)-ratios or

🔗

\begin{equation*} \begin{bmatrix} 20/5 \\ 260/(-31) \\ 84/9 \\ 32/(-4) \end{bmatrix} \approx \begin{bmatrix} 4 \\ -8.38 \\ 9.33 \\ -8 \end{bmatrix} \end{equation*}

🔗

and the smallest nonnegative ratio is the first row. Since the basic variable that corresponds to the 1st row is \(x_1\text{,}\) this is the leaving variable and the pivot is \(7 \mapsto 1\) or

🔗

\begin{equation*} \left[\begin{array}{rrr|rrrrr|r} 4 \amp 0 \amp 3 \amp -1 \amp 0 \amp 0 \amp 5 \amp 0 \amp 20\\ 31 \amp 0 \amp 22 \amp -4 \amp 5 \amp 0 \amp 0 \amp 0 \amp 480\\ -9 \amp 0 \amp 7 \amp 1 \amp 0 \amp 5 \amp 0 \amp 0 \amp 60\\ 4 \amp 5 \amp 3 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 60\\ \hline 17 \amp 0 \amp 14 \amp 2 \amp 0 \amp 0 \amp 0 \amp 5 \amp -120\\ \end{array} \right] \end{equation*}

🔗

Since there are no more negative parameters in the objective row, this tableau is now optimal. The basic solution is

🔗

\begin{align*} \boldsymbol{x} \amp = \frac{1}{5}\left[\begin{array}{rrr|rrrr} 0 \amp 60 \amp 0 \amp 0 \amp 480 \amp 60 \amp 20 \end{array}\right] \\ \amp = \left[\begin{array}{rrr|rrrr} 0 \amp 12 \amp 0 \amp 0 \amp 96 \amp 12 \amp 4 \end{array}\right] \end{align*}

🔗

and corresponding objective of \(z = -120/5 = -24\text{,}\) so the original objective is \(w = 24\) when \(x_1 = 0, x_2 = 12\) and \(x_3 = 0\text{.}\)

🔗

Problem 3.5.2.

\begin{equation*} \begin{aligned} \text{Maximize} \amp \amp z = 4x_1 +5x_2 + x_3 + 2x_4, \amp\\ \text{subject to} \amp \amp x_1 +3 x_2 + 2 x_3 + 4 x_4 \amp \geq 24 \\ \amp \amp - x_1 + 2x_2 + 3x_3 \amp \geq 10 \\ \amp \amp 5 x_1 -3x_2 +4 x_3 + 8x_4 \amp \geq 30 \\ \amp \amp x_1, x_2, x_3, x_4 \amp \geq 0. \end{aligned} \end{equation*}

🔗

Solution.

First, this is a maximum problem, so no changes needed to be made on the objective function. The three inequalities need to be flipped by multiplying by a negative number. This can be written as

🔗

\begin{equation*} \begin{aligned} \text{Maximize} \amp \amp z = 4x_1 +5x_2 + x_3 + 2x_4, \amp\\ \text{subject to} \amp \amp -x_1 - 3 x_2 - 2 x_3 - 4 x_4 \amp \leq -24, \\ \amp \amp x_1 - 2x_2 - 3x_3 \amp \leq -10, \\ \amp \amp -5 x_1 +3x_2 - 4 x_3 - 8x_4 \amp \leq -30, \\ \amp \amp x_1, x_2, x_3, x_4 \amp \geq 0. \end{aligned} \end{equation*}

🔗

which has the following simplex tableau:

🔗

\begin{equation*} \left[\begin{array}{rrrr|rrrr|r} -1 \amp -3 \amp -2 \amp -4 \amp 1 \amp 0 \amp 0 \amp 0 \amp -24\\ 1 \amp -2 \amp -3 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp -10\\ -5 \amp 3 \amp -4 \amp -8 \amp 0 \amp 0 \amp 1 \amp 0 \amp -30\\ \hline -4 \amp -5 \amp -1 \amp -2 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right] \end{equation*}

🔗

Since this the last column has negative numbers, this tableau is infeasible and we use phase I. Select row 3, which has the most negative values in the last column and the leftmost negative parameter in the row is in column 1, so \(x_1\) is the entering variable. The basic variable in row 3 is \(x_7\) so this is the leaving variable and we perform the following pivot:

🔗

\begin{equation*} 1 \mapsto 7, \qquad \left[\begin{array}{rrrr|rrrr|r} 0 \amp -18 \amp -6 \amp -12 \amp 5 \amp 0 \amp -1 \amp 0 \amp -90\\ 0 \amp -7 \amp -19 \amp -8 \amp 0 \amp 5 \amp 1 \amp 0 \amp -80\\ 5 \amp -3 \amp 4 \amp 8 \amp 0 \amp 0 \amp -1 \amp 0 \amp 30\\ \hline 0 \amp -37 \amp 11 \amp 22 \amp 0 \amp 0 \amp -4 \amp 5 \amp 120\\ \end{array} \right] \end{equation*}

🔗

There is still a negative number in the last column. The most negative occurs in row 1, which has the basic variable \(x_5\text{,}\) so this is the leaving variable. The leftmost negative parameter in this row occurs in column 2, so this is the entering variable and we perform the pivot

🔗

\begin{equation*} 2 \mapsto 5, \qquad \left[\begin{array}{rrrr|rrrr|r} 0 \amp 18 \amp 6 \amp 12 \amp -5 \amp 0 \amp 1 \amp 0 \amp 90\\ 0 \amp 0 \amp -60 \amp -12 \amp -7 \amp 18 \amp 5 \amp 0 \amp -162\\ 18 \amp 0 \amp 18 \amp 36 \amp -3 \amp 0 \amp -3 \amp 0 \amp 162\\ \hline 0 \amp 0 \amp 84 \amp 168 \amp -37 \amp 0 \amp -7 \amp 18 \amp 1098\\ \end{array} \right] \end{equation*}

🔗

There is still a negative in the last column and this occurs in row 2, which corresponds to \(x_6\text{,}\) so this is the leaving variable. The leftmost negative parameter in this row in in column 3, so the pivot is

🔗

\begin{equation*} 3 \mapsto 6 \qquad \left[\begin{array}{rrrr|rrrr|r} 0 \amp 60 \amp 0 \amp 36 \amp -19 \amp 6 \amp 5 \amp 0 \amp 246\\ 0 \amp 0 \amp 60 \amp 12 \amp 7 \amp -18 \amp -5 \amp 0 \amp 162\\ 60 \amp 0 \amp 0 \amp 108 \amp -17 \amp 18 \amp -5 \amp 0 \amp 378\\ \hline 0 \amp 0 \amp 0 \amp 504 \amp -156 \amp 84 \amp 0 \amp 60 \amp 2904\\ \end{array} \right] \end{equation*}

🔗

There are no negatives in the last column, so this is now a feasible tableau and we move onto phase II of the Simplex Method. There are negatives in the bottom/objective row, so we select the leftmost column in this row as the entering variable or \(x_5\text{.}\) We could calculate all of the \(\boldsymbol{b}\)-ratios, but notice that the only positive one is in the 2nd row. The basic variable in the row is \(x_3\) so the pivot:

🔗

\begin{equation*} 5 \mapsto 3, \qquad \left[\begin{array}{rrrr|rrrr|r} 0 \amp 7 \amp 19 \amp 8 \amp 0 \amp -5 \amp -1 \amp 0 \amp 80\\ 0 \amp 0 \amp 60 \amp 12 \amp 7 \amp -18 \amp -5 \amp 0 \amp 162\\ 7 \amp 0 \amp 17 \amp 16 \amp 0 \amp -3 \amp -2 \amp 0 \amp 90\\ \hline 0 \amp 0 \amp 156 \amp 90 \amp 0 \amp -37 \amp -13 \amp 7 \amp 760\\ \end{array} \right] \end{equation*}

🔗

There are still negatives in the objective row and so we examine column 6 (the leftmost and only negative number) and form \(\boldsymbol{b}\)-ratios. However, note that there are no positives in this column, so there will be no nonnegative ratios.

🔗

When this situation arises, this means that the LOP has no solution because the LOP is unbounded.

🔗

Prev Top Next