\begin{equation*}
\begin{aligned} \text{Max.} \amp\amp z = 40 x_1 + 36 x_2 + 72 x_3, \amp \\ \text{s.t.}\amp\amp 18 x_1 + 5 x_2 + 10 x_3 \amp \geq 85, \\ \amp\amp 4 x_1 + 20 x_2 + 15 x_3 \amp \geq 70, \\ \amp\amp10 x_1 + 15 x_2 + 18 x_3 \amp \leq 250, \\ \amp\amp 20 x_1 + 16 x_2 + 4x_3\amp \leq 180, \\ \text{and} \amp\amp x_1, x_2, x_3, x_4 \amp \geq 0.
\end{aligned}
\end{equation*}
Section 8.1 Writing a LOP in Matrix Form
Consider the following LOP.
Problem 8.1.1.
This can be first written in standard form and then if the following are defined
\begin{align*}
A \amp = \begin{bmatrix} -18 \amp -5 \amp -10 \\ -4 \amp -20 \amp -15 \\ 10 \amp 15 \amp 18 \\ 20 \amp 16 \amp 4 \end{bmatrix} \amp \boldsymbol{b} \amp =\begin{bmatrix} -85 \\ -70 \\ 250 \\ 180 \end{bmatrix} \amp \boldsymbol{c} \amp = \begin{bmatrix} 40 \\ 36 \\ 72 \end{bmatrix}
\end{align*}
Then Problem 8.1.1 can be written as
Problem 8.1.2.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp \amp z = \boldsymbol{c}^{\intercal} \boldsymbol{x} \\ \text{such that} \amp \amp A \boldsymbol{x} \leq \boldsymbol{b} \\ \text{and} \amp \amp \boldsymbol{x} \geq \boldsymbol{0}.
\end{aligned}
\end{equation*}
where the inequalities need to be considered as satisfying for each element.
Any problem can be written in this form. Additionally, the dual of the problem can be written
\begin{equation*}
\begin{aligned} \text{Minimize} \amp \amp w \amp = \boldsymbol{b}^{\intercal} \boldsymbol{y} \\ \text{such that} \amp \amp A^{\intercal} \boldsymbol{y} \amp \geq \boldsymbol{c} \\ \text{and} \amp \amp \boldsymbol{y} \amp \geq \boldsymbol{0}.
\end{aligned}
\end{equation*}
It is nice to be able to write a problem or it’s dual in this form, however, this generally doesn’t help us solve the problem.
Subsection 8.1.1 The Matrix Simplex Method
We will see in this section how to set up the simplex method to solve an LOP not by using the simplex tableau but by updating the matrix \(A\) and vectors \(\boldsymbol{b}\) and \(\boldsymbol{c}\text{.}\)
First, we define
\begin{equation*}
\boldsymbol{x}_{\beta} = \text{basis variables} \qquad \boldsymbol{x}_{\pi} = \text{parameters}
\end{equation*}
Then introducing slack variables to the inequality \(A \boldsymbol{x} \leq \boldsymbol{b}\) results in \(A\boldsymbol{x}_{\pi} + I \boldsymbol{x}_{\beta} = \boldsymbol{b}\text{.}\)
If we define
\begin{equation*}
\begin{aligned} \boldsymbol{c}_{\pi} \amp = \text{the $c$ variables with respect to the basis variables} \\ \boldsymbol{c}_{\beta} \amp = \text{the $c$ variables with respect to the parameters} \\ \end{aligned}
\end{equation*}
Then Problem 8.1.2 can be written
\begin{equation}
\text{Maximize}\;\; z = \boldsymbol{c}^{\intercal} \boldsymbol{x} \quad \text{such that} \; A\boldsymbol{x}_{\pi} + I \boldsymbol{x}_{\beta} = \boldsymbol{b} \; \text{and} \; \boldsymbol{x} \geq \boldsymbol{0}.\tag{8.1.1}
\end{equation}
where the objective is
\begin{equation*}
z = \boldsymbol{c}_{\beta}^{\intercal}\boldsymbol{x}_{\beta} + \boldsymbol{c}_{\pi}^{\intercal}\boldsymbol{x}_{\pi}
\end{equation*}
Specifically, for Problem 8.1.1, initially \(\beta = \{4,5,6,7\}\) and \(\pi = \{1,2,3\}\) and therefore
\begin{equation*}
\begin{aligned} \boldsymbol{c}_{\pi} = \begin{bmatrix} 40 \amp 36 \amp 72 \end{bmatrix}^{\intercal} \\ \boldsymbol{c}_{\beta} = \begin{bmatrix} 0 \amp 0 \amp 0 \amp 0 \end{bmatrix}^{\intercal} \\ \end{aligned}
\end{equation*}
and we write
\begin{equation*}
\boldsymbol{c} = \left[\begin{array}{rrr|rrrr} 40 \amp 36 \amp 72 \amp 0 \amp 0 \amp 0 \amp 0 \end{array}\right]^{\intercal}
\end{equation*}
Next, we define \(B\) to be the matrix that is the same size as \(A\) and have the columns of \(A\) or the identity matrix, \(I\) corresponding to the basic variables and the matrix \(\Pi\) a square matrix with the parameters.
\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} \qquad \Pi = \begin{bmatrix} -5 \amp -10 \amp 1 \\ -20 \amp -15 \amp 0 \\ 15 \amp 18 \amp 0 \\ 16 \amp 4 \amp 0 \end{bmatrix}
\end{equation*}
Now, the Primal LOP can be written:
\begin{equation*}
\text{Maximize}\;\; z = \boldsymbol{c}_{\beta}^{\intercal} \boldsymbol{x}_{\beta}+ \boldsymbol{c}_{\pi}^{\intercal} \boldsymbol{x}_{\pi}\quad \text{s.t.}\;\; B \boldsymbol{x}_{\beta} + \Pi \boldsymbol{x}_{\pi} = \boldsymbol{b}\quad\text{and}\;\; \boldsymbol{x} \geq \boldsymbol{0}.
\end{equation*}
Recall the dictionary form of an LOP problem from Section 3.1 in which the equations are written with the basic variables on the left. We can write the above LOP in dictionary form by solving for \(\boldsymbol{x}_{\beta}\) or
\begin{equation}
\boldsymbol{x}_{\beta} = B^{-1} (\boldsymbol{b}- \Pi \boldsymbol{x}_{\pi}) = B^{-1} \boldsymbol{b} - B^{-1} \Pi \boldsymbol{x}_{\pi}\tag{8.1.2}
\end{equation}
and substituting this into the objective function:
\begin{align}
z \amp = \boldsymbol{c}_{\beta}^{\intercal} \bigl( B^{-1} \boldsymbol{b} - B^{-1} \Pi \boldsymbol{x}_{\pi} \bigr)+ \boldsymbol{c}_{\pi}^{\intercal} \boldsymbol{x}_{\pi} \notag\\
\amp = \boldsymbol{c}_{\beta}^{\intercal} B^{-1} \boldsymbol{b} - \boldsymbol{c}_{\beta}^{\intercal} B^{-1} \Pi \boldsymbol{x}_{\pi} + \boldsymbol{c}_{\pi}^{\intercal} \boldsymbol{x}_{\pi} \notag\\
\amp = \boldsymbol{c}_{\beta}^{\intercal} B^{-1} \boldsymbol{b} - (\boldsymbol{c}_{\beta}^{\intercal} B^{-1} \Pi - \boldsymbol{c}_{\pi}^{\intercal}) \boldsymbol{x}_{\pi} \tag{8.1.3}
\end{align}
Note that if the parameters are 0 or \(\boldsymbol{x}_{\pi}=\boldsymbol{0}\text{,}\) then (8.1.2) becomes
\begin{equation}
\boldsymbol{x}_{\beta} = B^{-1} \boldsymbol{b}.\tag{8.1.4}
\end{equation}
\begin{equation}
z = \boldsymbol{c}_{\beta}^{\intercal} B^{-1} \boldsymbol{b}\tag{8.1.5}
\end{equation}
In the following example, we will calculate the formulas or parts of formulas above and will be useful for performing the simplex method in the next section.
Example 8.1.3.
-
\(\displaystyle B^{-1}\)
-
\(B^{-1}\boldsymbol{b}\text{,}\)
-
\(B^{-1}\Pi\text{,}\)
-
\(\displaystyle \boldsymbol{c}_{\beta}^{\intercal}B^{-1}\boldsymbol{b}\)
-
\(\boldsymbol{c}_{\beta}^{\intercal}B^{-1}\Pi - \boldsymbol{c}_{\pi}^{\intercal}\text{.}\)
Solution.
First, note that \(B\) takes on the 1st and 3rd columns of \(A\) and then the 3rd and 4th columns of \(I\text{.}\) The first column of \(\Pi\) is the 2nd column of \(A\) and then the 2nd and 3rd columns of \(\Pi\) are the first and second columns of \(I\) or
\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*}
Also, it is helpful to use software to find the inverse and matrix product. See Section 8.2 to use Julia to do this.
-
\begin{equation*} B^{-1} = \begin{bmatrix} -3/46 \amp 1/23 \amp 0 \amp 0 \\ 2/115 \amp -9/115 \amp 0 \amp 0 \\ 39/115 \amp 112/115 \amp 1 \amp 0 \\ 142/115 \amp -64/116 \amp 0 \amp 1 \end{bmatrix} \end{equation*}
-
Using the matrix \(B^{-1}\) above leads to\begin{equation*} B^{-1} \boldsymbol{b} = \begin{bmatrix} 5/2 \\ 4 \\ 153 \\114 \end{bmatrix} \end{equation*}
-
Again, use the matrix \(B^{-1}\) above,\begin{equation*} B^{-1} \Pi = \begin{bmatrix} -25/46 \amp -3/46 \amp 1/23 \\ 34/23 \amp 2/115 \amp -9/115 \\ -142/23 \amp 39/115 \amp 112/115 \\ 482/23 \amp 142/115 \amp -64/115 \end{bmatrix} \end{equation*}
-
First, note that\begin{equation*} \boldsymbol{c}_{\beta} = \begin{bmatrix} 40 \\ 72 \\ 0 \\ 0 \end{bmatrix} \qquad \boldsymbol{c}_{\pi} = \begin{bmatrix} 36 \\ 0 \\ 0 \end{bmatrix} \end{equation*}and then\begin{equation*} \boldsymbol{c}_{\beta}^{\intercal}B^{-1}\boldsymbol{b} = 388 \end{equation*}
-
To find \(\boldsymbol{c}_{\beta}^{\intercal}B^{-1}\Pi - \boldsymbol{c}_{\pi}^{\intercal}\) first find\begin{equation*} \boldsymbol{c}_{\beta}^{\intercal}B^{-1}\Pi = \frac{1}{115}\begin{bmatrix} 9740 \amp -156 \amp -448 \end{bmatrix}^{\intercal} \end{equation*}so\begin{equation*} \boldsymbol{c}_{\beta}^{\intercal}B^{-1}\Pi -\boldsymbol{c}_{\pi}^{\intercal} = \frac{1}{115}\begin{bmatrix} 5600 \amp -156 \amp -448 \end{bmatrix}^{\intercal} \end{equation*}
The matrices and vectors in Example 8.1.3 are useful for solving LOPs using this matrix form. More details on using these will follow below. However, if you notice that each of these had fractions in the results and to keep things in integer form, we can introduce some other notation. First, let \(d_{\beta} = |\text{det}(B)|\) and then
\begin{equation*}
B' = d_{\beta}B^{-1}
\end{equation*}
\begin{equation}
d_{\beta} \boldsymbol{x}_{\beta} = B' \boldsymbol{b} - B'\Pi\boldsymbol{x}_{\pi}\tag{8.1.6}
\end{equation}
\begin{equation}
d_{\beta} z = \boldsymbol{c}_{\beta}^{\intercal} B' \boldsymbol{b} - (\boldsymbol{c}_{\beta}^{\intercal} B' \Pi - d_{\beta}\boldsymbol{c}_{\pi}^{\intercal}) \boldsymbol{x}_{\pi}\tag{8.1.7}
\end{equation}
Example 8.1.4.
Using the basis and parameters in Example 8.1.3, then find the following:
-
\(\displaystyle d_{\beta}\)
-
\(\displaystyle B'\)
-
\(B'\boldsymbol{b}\text{,}\)
-
\(B'\Pi\text{,}\)
-
\(\displaystyle \boldsymbol{c}_{\beta}^{\intercal}B'\boldsymbol{b}\)
-
\(\boldsymbol{c}_{\beta}^{\intercal}B'\Pi - d_{\beta} \boldsymbol{c}_{\pi}^{\intercal}\text{.}\)
Solution.
-
\(\displaystyle d_{\beta} = 230\)
-
\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 using the above\begin{equation*} B'\boldsymbol{b} = \begin{bmatrix} 575 \\ 920 \\ 35190 \\ 26220 \end{bmatrix} \end{equation*}
-
\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*}
-
\begin{equation*} \boldsymbol{c}_{\beta}^{\intercal} B' \boldsymbol{b} = 89240 \end{equation*}
-
\begin{equation*} \boldsymbol{c}_{\beta}^{\intercal} B' \Pi - d_{\beta} \boldsymbol{c}_{\pi}^{\intercal} = \begin{bmatrix} 11200 \amp -312 \amp -896 \end{bmatrix} \end{equation*}
Although the terms we found in Example 8.1.3 came from the formulas above, they will also be used to perform the simplex method. We will walk through the steps of the simplex method using these matrices and vectors in the next section.
Subsection 8.1.2 Comparison to the Tableau
How does this compare to the simplex tableau? Let’s look at the tableau of Problem 8.1.1 and see how this compares to the matrix forms. Start with the initial tableau of
\begin{equation*}
\left[\begin{array}{rrr|rrrrr|r}
-18 \amp -5 \amp -10 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp -85\\
-4 \amp -20 \amp -15 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp -70\\
10 \amp 15 \amp 18 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 250\\
20 \amp 16 \amp 4 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 180\\ \hline
-40 \amp -36 \amp -72 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\
\end{array} \right]
\end{equation*}
The basis in Example 8.1.3 and Example 8.1.4 is \(\beta=\{1,3,6,7\}\text{,}\) so we need to perform pivots for this. We can do \(1 \mapsto 4\) and \(3 \mapsto 5\) to get this basis. Applying these pivots to the above tableau is
\begin{equation*}
\left[\begin{array}{rrr|rrrrr|r}
230 \amp -125 \amp 0 \amp -15 \amp 10 \amp 0 \amp 0 \amp 0 \amp 575\\
0 \amp 340 \amp 230 \amp 4 \amp -18 \amp 0 \amp 0 \amp 0 \amp 920\\
0 \amp -1420 \amp 0 \amp 78 \amp 224 \amp 230 \amp 0 \amp 0 \amp 35190\\
0 \amp 4820 \amp 0 \amp 284 \amp -128 \amp 0 \amp 230 \amp 0 \amp 26220\\ \hline
0 \amp 11200 \amp 0 \amp -312 \amp -896 \amp 0 \amp 0 \amp 230 \amp 89240\\
\end{array} \right]
\end{equation*}
Hopefully, you can see a number of similarities. First, the value in each of the basis variables in 230, which is the value \(d_{\beta}\text{.}\)
The matrix \(B'\) is the columns 4 through 7 of the tableau.
The vector \(B'\boldsymbol{b}\) is the right column of the tableau. Also, this is the value of basic solution with the factor of \(1/d_{\beta}\text{.}\)
The matrix \(B'\Pi\) is the columns of the tableau corresponding to the parameters \(\pi=\{2,4,5\}.\) This part of the tableau is important in determining the next pivot in the simplex method as we will see in the next section.
The value \(\boldsymbol{c}^{\intercal}_{\beta} B' \boldsymbol{b}\) is that of the objective function (lower right element).
The row vector \(\boldsymbol{c}^{\intercal}_{\beta} B'\pi - d_{\beta} \boldsymbol{c}^{\intercal}_{\pi}\) is the coefficients of the parameters in the objective row. We will need this for the simplex method in the next section.
