Skip to main content

Linear Optimization Modeling and Solving Linear problems with Julia and WebCAS

Peter Staab

Section 8.3 Performing the Matrix Simplex Method

We now adapt the simplex method to using the matrices from the previous section instead of a tableau.
🔗
Let’s return to Problem 8.1.1, which was written in matrix form in Section 8.1. We use all of the matrix notation from that section to adapt the simplex method to solve such LOPs.
🔗
  1. Initially the basis for this problem is \(\beta=\{4,5,6,7\}\) and \(\pi=\{1,2,3\}\text{,}\) therefore the first step is to find \(B\) for this basis which are the 4th through 7th columns of the simplex tableau or just the identity matrix. Therefore \(B=I\) and also \(B'=I\) and the basic solution is \(B'\boldsymbol{b}\text{,}\) which is just \(\boldsymbol{b}\text{.}\)
    🔗
    \begin{equation*} B' \boldsymbol{b} = \begin{bmatrix} -85 \\ -70 \\ 250 \\ 180 \end{bmatrix}. \end{equation*}
    🔗
    Also, note that the parameter columns (which are quite important in the simplex method) are in \(B'\Pi\text{.}\) Since this is the first step, this matrix is just \(\Pi\) or
    🔗
    \begin{equation*} \Pi = \begin{bmatrix} -18 \amp -5 \amp -10 \\ -4 \amp -20 \amp -15 \\ 10 \amp 15 \amp 18 \\ 20 \amp 16 \amp 4 \end{bmatrix}. \end{equation*}
    🔗
    The right column is \(B'\boldsymbol{b}\) has negatives, so the tableau is infeasible and we need to use phase I. In this case, we find the most negative in this vector, which occurs in the first row. The first row corresponds to the first element of \(\beta\text{,}\) so this is the leaving variable. The leftmost negative in the first row of \(\Pi\) corresponds to the smallest value in \(\pi\) or \(x_1\text{,}\) so this is the entering variable. We thus to a pivot \(1 \mapsto 4\text{.}\)
    🔗
    🔗
  2. There the new basis is \(\beta = \{1,5,6,7\}\) and \(\pi=\{2,3,4\}\text{.}\) This means that
    🔗
    \begin{equation*} B = \begin{bmatrix} -18 \amp 0 \amp 0 \amp 0 \\ -4 \amp 1 \amp 0 \amp 0 \\ 10 \amp 0 \amp 1 \amp 0 \\ 20 \amp 0 \amp 0 \amp 1\end{bmatrix} \end{equation*}
    🔗
    We can the calculate the determinant of \(B\) to be \(d_{\beta} = 18\) and
    🔗
    \begin{equation*} B' = d_{\beta} B^{-1} = \begin{bmatrix} -1 \amp 0 \amp 0 \amp 0 \\ -4 \amp 18 \amp 0 \amp 0 \\ 10 \amp 0 \amp 18 \amp 0 \\ 20 \amp 0 \amp 0 \amp 18 \end{bmatrix} \end{equation*}
    🔗
    And then calculate
    🔗
    \begin{equation*} B' \boldsymbol{b} = \begin{bmatrix} 85 \\ -920 \\ 3650 \\ 1540 \end{bmatrix} \end{equation*}
    🔗
    This shows that the tableau is still infeasible and we continue with phase I. We need to find
    🔗
    \begin{equation*} B'\Pi = \begin{bmatrix} 5 \amp 10 \amp -1 \\ -340 \amp -230 \amp -4 \\ 220 \amp 224 \amp 10 \\ 188 \amp -128 \amp 20 \\ \end{bmatrix} \end{equation*}
    🔗
    The smallest (most negative) number in \(B' \boldsymbol{b}\) is in the second row, so the leaving variable is second basis variable or \(x_5\text{.}\) The entering variable will be the leftmost negative in the 2nd row of \(B'\Pi\text{,}\) which occurs in the first column, so the entering variable is the first parameter or \(x_2\text{.}\) We then perform a pivot \(2 \mapsto 5\text{.}\)
    🔗
    🔗
  3. The new basis will be \(\beta = \{1, 2, 6,7 \}\) and \(\pi=\{3,4,5\}\text{.}\) Therefore the result is
    🔗
    \begin{equation*} B = \begin{bmatrix} -18 \amp -5 \amp 0 \amp 0 \\ -4 \amp -20 \amp 0 \amp 0 \\ 10 \amp 15 \amp 1 \amp 0 \\ 20 \amp 16 \amp 0 \amp 1 \\ \end{bmatrix} \qquad \Pi = \begin{bmatrix} -10 \amp 1 \amp 0 \\ -15 \amp 0 \amp 1 \\ 18 \amp 0 \amp 0 \\ 4 \amp 0 \amp 0 \\ \end{bmatrix} \end{equation*}
    🔗
    The determinant of \(B\) is 340, so this is \(d_{\beta}\) and
    🔗
    \begin{equation*} B' = d_{\beta} B^{-1} = \begin{bmatrix} -20 \amp 5 \amp 0 \amp 0 \\ 4 \amp -18 \amp 0 \amp 0 \\ 140 \amp 220 \amp 340 \amp 0 \\ 336 \amp 188 \amp 0 \amp 340 \\ \end{bmatrix} \end{equation*}
    🔗
    and then
    🔗
    \begin{equation*} B' \boldsymbol{b} = \begin{bmatrix} 1350 \\ 920 \\ 57700 \\ 19480 \end{bmatrix} \end{equation*}
    🔗
    There are no negatives in this vector so phase I is complete and we move to phase II.
    🔗
    🔗
  4. In phase II, using the simplex tableau, we need to examine the objective row. In the matrix formulation, we need the coefficient of the parameters in this row and this corresponds to \(\boldsymbol{c}_{\beta}^{\intercal}B'\Pi - d_{\beta}\boldsymbol{c}_{\pi}^{\intercal}\) and this is calculated for this basis as
    🔗
    \begin{equation*} \begin{bmatrix} -11200 \amp -656 \amp -448 \end{bmatrix} \end{equation*}
    🔗
    and since there are negatives in this row, it is not optimal. This also shows that the entering variable is the leftmost negative corresponding to the 1st parameter or \(x_3\text{.}\) To find the leaving variable, we need to examine
    🔗
    \begin{equation*} B' \Pi = \begin{bmatrix} 125 \amp -20 \amp 5 \\ 230 \amp 4 \amp -18 \\ 1420 \amp 140 \amp 220 \\ -4820 \amp 336 \amp 188 \\ \end{bmatrix} \end{equation*}
    🔗
    and create \(\boldsymbol{b}\)-ratios using the 1st column of \(B' \Pi \)
    🔗
    \begin{equation*} \begin{bmatrix} 1350/125 \\ 920/230 \\ 5770/1420 \\ 19480/(-4820) \end{bmatrix} \approx \begin{bmatrix} 10.8 \\ 4.0 \\ 40.63 \\ -4.04 \end{bmatrix} \end{equation*}
    🔗
    The smallest ratio is in the 2nd row, which corresponds to the 2nd basis element or \(x_2\text{,}\) so this is the leaving vector. Therefore we need to perform the pivot \(3 \mapsto 2\)
    🔗
    🔗
  5. We are still in phase II and after the pivot \(4 \mapsto 6\text{,}\) the basis is now \(\beta = \{1,3,6,7\}\) with \(\pi = \{2,4,5\}\text{.}\) Then
    \begin{equation*} B = \begin{bmatrix}-18 \amp -10 \amp 0 \amp 0 \\ -4 \amp -15 \amp 0 \amp 0 \\ 10 \amp 18 \amp 1 \amp 0 \\ 20 \amp 4 \amp 0 \amp 1 \\ \end{bmatrix} \qquad \Pi = \begin{bmatrix} -5 \amp 1 \amp 0 \\ -20 \amp 0 \amp 1 \\ 15 \amp 0 \amp 0 \\ 16 \amp 0 \amp 0 \\ \end{bmatrix}. \end{equation*}
    🔗
    The determinant of \(B\) is \(230\text{,}\) so \(d_{\beta} = 230\) and
    🔗
    \begin{equation*} B' = d_{\beta} B^{-1} = \begin{bmatrix} -15 \amp 10 \amp 0 \amp 0 \\ 4 \amp -18 \amp 0 \amp 0 \\ 78 \amp 224 \amp 230 \amp 0 \\ 284 \amp -128 \amp 0 \amp 230 \end{bmatrix} \end{equation*}
    🔗
    and then since we are in phase II, examine:
    🔗
    \begin{equation*} \boldsymbol{c}_{\beta}^{\intercal}B^{-1}\Pi - \boldsymbol{c}_{\pi}^{\intercal} = \begin{bmatrix} 11200 \amp -312 \amp -896 \end{bmatrix} \end{equation*}
    🔗
    which shows that this basic solution is not optimal. We use the second parameter and corresponds to \(x_4\text{,}\) so this is he entering variable. To decide the leaving, we need to find the \(\boldsymbol{b}\)-ratios using:
    🔗
    \begin{equation*} B' \boldsymbol{b} = \begin{bmatrix} 575 \\ 920 \\ 35190 \\ 26220 \end{bmatrix} \end{equation*}
    🔗
    and
    🔗
    \begin{equation*} B'\Pi = \begin{bmatrix} -125 \amp -15 \amp 10 \\ 340 \amp 4 \amp -18 \\ -1420 \amp 78 \amp 224 \\ 4820 \amp 284 \amp -128 \\ \end{bmatrix} \end{equation*}
    🔗
    and the \(\boldsymbol{b}\)-ratios are found by dividing elements in \(B' \boldsymbol{b}\) by the elements in the first column of \(B'\Pi\) to get
    🔗
    \begin{equation*} \begin{bmatrix} 575/(-15) \\ 920/4 \\ 35190/78 \\ 26220/284 \end{bmatrix} \approx \begin{bmatrix} -38.33 \\ 230.0 \\ 451.15 \\ 92.323 \end{bmatrix} \end{equation*}
    🔗
    and the smallest nonnegative ratio is in the fourth row. This corresponds to the fourth basis element or \(x_7\text{,}\) so we perform the pivot \(4 \mapsto 7\)
    🔗
    🔗
  6. The pivot \(4 \mapsto 7\) results in the basis \(\beta = \{1,3,4,6\}\) with \(\pi=\{2, 5,7\}\text{.}\) The corresponding matrices are
    🔗
    \begin{equation*} B = \begin{bmatrix} -18 \amp -5 \amp -10 \amp 0 \\ -4 \amp -20 \amp -15 \amp 0 \\ 10 \amp 15 \amp 18 \amp 1 \\ 20 \amp 16 \amp 4 \amp 0 \\ \end{bmatrix} \qquad \Pi = \begin{bmatrix} -5 \amp 0 \amp 0 \\ -20 \amp 1 \amp 0 \\ 15 \amp 0 \amp 0 \\ 16 \amp 0 \amp 1 \end{bmatrix} \end{equation*}
    🔗
    The determinant of \(B\) is \(284\text{,}\) so \(d_{\beta}=284\) and
    🔗
    \begin{equation*} B' = \begin{bmatrix} 0 \amp 4 \amp 0 \amp 15 \\ 284 \amp -128 \amp 0 \amp 230 \\ 0 \amp -20 \amp 0 \amp -4 \\ 0 \amp 320 \amp 284 \amp -78 \end{bmatrix} \end{equation*}
    🔗
    and since we are in phase II, we check:
    🔗
    \begin{equation} \boldsymbol{c}_{\beta}^{\intercal}B^{-1}\Pi - \boldsymbol{c}_{\pi}^{\intercal} = \begin{bmatrix} 20368 \amp -1280 \amp 312 \end{bmatrix}\tag{8.3.1} \end{equation}
    🔗
    and note that there are still negatives in this vector, so this solution is not optimal. From (8.3.1), the leftmost negative is in the second position, so the entering variable is the second parameter or \(x_5\text{.}\)
    🔗
    With
    \begin{equation*} \begin{aligned} B'\boldsymbol{b} \amp = \begin{bmatrix} 2420 \\ 26220 \\ 680 \\ 34560 \end{bmatrix} \amp B'\Pi \amp = \begin{bmatrix} 160 \amp 4 \amp 15 \\ 4820 \amp -128 \amp 230 \\ 336 \amp -20 \amp -4 \\ -3388 \amp 320 \amp -78 \\ \end{bmatrix} \end{aligned} \end{equation*}
    and since the leftmost negative in (8.3.1) is in the 2nd column, so we use the second column of \(B'\Pi\) to form \(\boldsymbol{b}\)-ratios:
    \begin{equation*} \begin{bmatrix} 2420 / 4 \\ 26220/(-128) \\ 680/(-20) \\ 34560/320 \end{bmatrix} \approx \begin{bmatrix} 605 \\ -204.84 \\ -34 \\ 108 \end{bmatrix} \end{equation*}
    and the smallest \(\boldsymbol{b}\)-ratio is in the fourth position. This corresponds to the fourth basic variable or \(x_6\) as the leaving variable. We next perform the pivot \(5 \mapsto 6\)
    🔗
    🔗
  7. The pivot \(5 \mapsto 6\) results in \(\beta=\{1,3,4,5\}\) and \(\pi=\{2,6,7\}\) and the corresponding matrices are
    \begin{equation*} \begin{aligned} B \amp = \left[ \begin{array}{cccc} -18 \amp -10 \amp 1 \amp 0 \\ -4 \amp -15 \amp 0 \amp 1 \\ 10 \amp 18 \amp 0 \amp 0 \\ 20 \amp 4 \amp 0 \amp 0 \\ \end{array} \right] \amp \Pi = \amp \left[ \begin{array}{ccc} -5 \amp 0 \amp 0 \\ -20 \amp 0 \amp 0 \\ 15 \amp 1 \amp 0 \\ 16 \amp 0 \amp 1 \\ \end{array} \right] \end{aligned} \end{equation*}
    🔗
    and the value of \(d_{\beta} = \det(B)=320\) will be needed.
    🔗
    Finally, the objective row
    \begin{equation} \boldsymbol{c}_{\beta}^{\intercal}B^{-1}\Pi - \boldsymbol{c}_{\pi}^{\intercal} = \begin{bmatrix} 20368 \amp -1280 \amp 312 \end{bmatrix}\tag{8.3.2} \end{equation}
    is free of negatives, so this is an optimal solution. The basic solution to this is \(B' \boldsymbol{b}\) for the basic variables or
    🔗
    \begin{equation*} \boldsymbol{x}_{\beta} = \frac{1}{d_{\beta}} B' \boldsymbol{b} = \frac{1}{320} \begin{bmatrix} 2240 \\ 3200 \\ 45120 \\ 34560 \end{bmatrix} \end{equation*}
    🔗
    and in terms of the original variables, the optimal solution is
    🔗
    \begin{equation*} \begin{aligned} x_1 \amp = \frac{2240}{320} = 7 \\ x_2 \amp = 0 \\ x_3 \amp = \frac{3200}{320} = 10 \end{aligned} \end{equation*}
    🔗
    and the objective is found with
    🔗
    \begin{equation*} z = \frac{1}{d_{\beta}} \boldsymbol{c}^{\intercal}_{\beta} B' \boldsymbol{b} = \frac{320000}{320} = 1000 \end{equation*}
    🔗
    🔗
🔗

Subsection 8.3.1 The Matrix Simplex Method

This is now the steps of the simplex method if one is using the matrix formulation.
🔗

Setup.

As before the system must be put in standard form and as above, we need the matrix of constraint coefficients \(A\text{,}\) the right hand side \(\boldsymbol{b}\) and the objective vector \(\boldsymbol{c}\text{.}\)
🔗
If there are \(n\) original variables with \(m\) constraints, then to begin with
\begin{equation*} \begin{aligned} \beta \amp = \{n+1, n+2, \ldots, n+m\} \amp \pi \amp = \{1, 2, \ldots, n\} \end{aligned} \end{equation*}
🔗
Let \(S\) be the matrix \([A \;\; I]\text{,}\) then \(B\) is the square matrix with the columns of \(S\) taken from \(\beta\text{.}\) The matrix \(\Pi\) is the \(m \times n\) matrix with the columns of \(S\) taken from \(\pi\text{.}\)
🔗
Let \(d_{\beta} = |\det(B)|\) and \(B' = d_{\beta} B^{-1}\text{,}\) which will be a square integer matrix.
🔗
🔗

Phase I.

Recall that this phase is to take a tableau that is infeasible and make it feasible.
🔗
  1. If \(B'\boldsymbol{b} \geq 0\) then the matrix is feasible. Stop. Phase I is complete.
    🔗
    🔗
  2. Find the most negative number in \(B'\boldsymbol{b}\text{.}\) The index of this corresponds to the leaving variable in \(\beta\text{.}\) Call this index \(i\text{.}\)
    🔗
    🔗
  3. Examine the \(i\)th row of \(B'\Pi\) and find the leftmost negative number. The index of this corresponds to the entering variable in \(\pi\text{.}\) Call this index \(j\text{.}\) We will then perform the pivot \(\pi_j \mapsto \beta_i\text{.}\) Note: if there are no negatives in this row, then the LOP is infeasible.
    🔗
    🔗
  4. Swap the \(i\)th element of \(\beta\) with the \(j\)th element of \(\pi\) and return to Step 1.
    🔗
    🔗
🔗
🔗

Phase II.

Recall that the purpose of this phase is take a feasible tableau and make it optimal.
🔗
  1. The non-basic variables in the objective row can be found with \(\boldsymbol{c}_{\beta}^{\intercal}B'\Pi - d_{\beta}\boldsymbol{c}_{\pi}^{\intercal} \text{.}\) If there are no negatives in this row, then the solution is optimal. Stop. To to the Optimum Solution phase.
    🔗
    🔗
  2. Find the index of the leftmost negative of \(\boldsymbol{c}_{\beta}^{\intercal}B'\Pi - d_{\beta}\boldsymbol{c}_{\pi}^{\intercal} \text{.}\) Call this \(j\text{.}\) Form \(\boldsymbol{b}\)-ratios using the quotient of \(B'\boldsymbol{b}\) to the \(j\)th column of \(B'\Pi\text{.}\) The entering variable will be \(\pi_j\)
    🔗
    🔗
  3. Find the smallest nonnegative ratio from the \(\boldsymbol{b}\)-ratios. Call the index of this \(i\text{.}\) The entering variable will be \(\beta_i\) and the pivot will be \(\pi_j \mapsto \beta_i\text{.}\) Note: if there is no nonnegative ratio, then the problem is unbounded.
    🔗
    🔗
  4. Swap the \(i\)th element of \(\beta\) with the \(j\)th element of \(\pi\) and return to Step 1.
    🔗
    🔗
🔗
🔗

Optimal Solution.

Once the optimal solution has been found, the solution to the basic variable is
\begin{equation*} x_{\beta} = \frac{1}{d_{\beta}} B' \boldsymbol{b} \end{equation*}
and if the objective vlaue is
\begin{equation*} z = \frac{1}{d_{\beta}} \boldsymbol{c}_{\beta}^{\intercal} B' \boldsymbol{b} \end{equation*}
🔗
Lastly, if the dual solutions are needed then they are:
\begin{equation*} \boldsymbol{c}_{\beta}^{\intercal}B'\Pi - d_{\beta}\boldsymbol{c}_{\pi}^{\intercal} \end{equation*}
🔗
🔗
🔗
🔗
PrevTopNext