Objectives
-
Write a general Linear Optimization Problem (LOP) in general form.
-
Provide the Phase 0 method of the simplex method.
Section 7.2 Solving General Linear Optimization Problems
The previous section Section 7.1 updated the simplex method to handle free variables as well as equality constraints
\begin{equation*}
\begin{aligned} \text{Maximize} \amp\amp z = \sum_{j=1}^n c_j x_j,\amp \\ \text{subject to} \amp\amp \sum_{j=1}^n a_{ij} x_j \amp\leq b_i, \qquad \text{if $i \in I$}, \\ \amp\amp \sum_{j=1}^n a_{ij} x_j \amp= b_i, \qquad \text{if $i \in E$}, \\ \text{and} \amp\amp x_j \amp\geq 0 \qquad \text{if $j \in R$.} \end{aligned}
\end{equation*}
where \(I \subset \{1,2,\ldots,m\}\) are the constraints which are inequalities, \(E = \{1,2,\ldots,m\}-I\) are the constraints which are equalities. \(R \subset \{1,2,\ldots, n\}\) are restricted to be nonnegative which \(F = \{1,2,\ldots, n\} - R\) are those that are free variables.
The algorithm denoted Phase 0 was developed in Section 7.1 to solve general LOPs. The following is a summary of the steps and how phase I and II need to be adapted to solve these problems.
Phase 0 method
-
As with all other LOPs, the problem needs to be written in standard form.
-
In building the simplex tableau, for equality statements, do not add a slack variable, but add the equation in the tableau. For free variables, note the column of that variable. This is often done by writing \(F\) above the column in the tableau for the free variables.
-
If there are equality constraints in the tableau, pivot to bring a standard variable into the basis. Give preference to free variables and otherwise chose the lowest subscript.
-
If there are free variables still not in the basis, pivot them to be in the basis.
-
Repeat these steps 3 and 4 until all free variables and all equality constraints are in the basis, if possible. If this is not possible, then there is no solution.
Phase I revisited
Recall that the goal of Phase 1 is to make a set feasible. If a free variable has a negative value for its basic variable, that’s okay. Phase I should not take a free variable out of the basis variables.
In short, phase I now only removes negative variables from restricted variables.
Phase II revisited
In phase 2, recall that we are trying to pivot to increase the value of \(z\text{.}\) This typically means that if any number is negative in the objective row, that we enter that variable. After phase 0, all free variables should be in the basis and phase 1 should not remove them, so only restricted variables can have a negative number in the objective row.
Next, we typically chose the pivot row based on not making the tableau infeasible. However, recall that since free variables can take on any value, we pivot to increase \(z\) the most and should never remove a free variable from the basis.
Problem 7.2.1.
Solve the following Linear Optimization Problem using the adapted Simplex method
\begin{equation*}
\begin{aligned} \text{Minimize} \amp\amp z = 2x_1 + 4x_2, \amp \\ \text{s.t.} \amp\amp x_1 - x_2 \amp \geq 0, \\ \amp\amp3x_1 + 2x_2 \amp \leq 24, \\ \amp\amp 2x_1 - 3x_2 \amp \leq 12.
\end{aligned}
\end{equation*}
Note that there are no nonnegative constraints so both \(x_1\) and \(x_2\) are free. The first inequality is not in standard form, so we multiply through by \(-1\) first. Also, this is a minimum problem, so we write the maximum version as \(w = -2x_1-4x_2\text{.}\) The simplex tableau can be written as
\begin{align*}
\amp\begin{array}{rrrrrr}\phantom{111} {\small F} \amp \phantom{-}{\small F} \end{array}\\
\amp \left[\begin{array}{rr|rrrr|r} -1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0\\ 3 \amp 2 \amp 0 \amp 1 \amp 0 \amp 0 \amp 24\\ 2 \amp -3 \amp 0 \amp 0 \amp 1 \amp 0 \amp 12\\ \hline 2 \amp 4 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{align*}
Since both \(x_1\) and \(x_2\) are free, we will pivot to bring them into the basis. There’s not a clear choice for what leaves the basis, so we will select \(x_3\) and \(x_4\) to leave.
\begin{align*}
\amp\begin{array}{rrrrrr}\phantom{1} {\small F} \amp \phantom{-}{\small F} \end{array}\\
1 \mapsto 3, \qquad \amp \left[\begin{array}{rr|rrrr|r} 1 \amp -1 \amp -1 \amp 0 \amp 0 \amp 0 \amp 0\\ 0 \amp 5 \amp 3 \amp 1 \amp 0 \amp 0 \amp 24\\ 0 \amp -1 \amp 2 \amp 0 \amp 1 \amp 0 \amp 12\\ \hline 0 \amp 6 \amp 2 \amp 0 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{align*}
\begin{align*}
\amp\begin{array}{rrrrrr}\phantom{1} {\small F} \amp {\small F} \end{array}\\
2 \mapsto 4, \qquad \amp \left[\begin{array}{rr|rrrr|r} 5 \amp 0 \amp -2 \amp 1 \amp 0 \amp 0 \amp 24\\ 0 \amp 5 \amp 3 \amp 1 \amp 0 \amp 0 \amp 24\\ 0 \amp 0 \amp 13 \amp 1 \amp 5 \amp 0 \amp 84\\ \hline 0 \amp 0 \amp -8 \amp -6 \amp 0 \amp 5 \amp -144\\ \end{array} \right]
\end{align*}
Now that both free variables are in the basis, Stage 0 is finished.
Note that all of the variables are feasible, so there is no need to perform any Phase I steps. Next we move to Phase II and we perform the matrix pivot on row 3, column 3:
Recall that the \(\boldsymbol{b}\)-ratios,
\begin{equation*}
\frac{\boldsymbol{b}}{A_3} = \begin{bmatrix} -24/2 \\ 24/3 \\ 84/13 \end{bmatrix} \approx \begin{bmatrix} -12 \\ 8 \\ 6.46 \end{bmatrix}
\end{equation*}
and then typically the smallest nonnegative ratio is selected. This ensures that the solution stays feasible. This is a bit different with free variables, because they can take on negative numbers. However since \(x_3\) is entering the basis and it is restricted to be nonnegative, we still select the 3rd variable above, and \(x_5\) will leave the basis.
\begin{equation*}
3 \mapsto 5 \qquad \left[\begin{array}{rr|rrrr|r} 13 \amp 0 \amp 0 \amp 3 \amp 2 \amp 0 \amp 96\\ 0 \amp 13 \amp 0 \amp 2 \amp -3 \amp 0 \amp 12\\ 0 \amp 0 \amp 13 \amp 1 \amp 5 \amp 0 \amp 84\\ \hline 0 \amp 0 \amp 0 \amp -14 \amp 8 \amp 13 \amp -240\\ \end{array} \right]
\end{equation*}
and still this isn’t an optimal solution, so we’ll do one more pivot. Again, the following \(\boldsymbol{b}\)-ratio is found
\begin{equation*}
\frac{\boldsymbol{b}}{A_4} = \begin{bmatrix}96/3 \\ 12/2 \\ 84/1 \end{bmatrix} = \begin{bmatrix} 32 \\ 6 \\ 84 \end{bmatrix}
\end{equation*}
and if we do the standard smallest nonnegative ratio, we would choose the 2nd one. However, that would remove \(x_2\) from the basis, so we don’t select that or the first one, which would remove \(x_1\text{.}\) The only result is \(x_3\text{.}\) Therefore, we perform
\begin{equation*}
4 \mapsto 3 \qquad \left[\begin{array}{rr|rrrr|r} 1 \amp 0 \amp -3 \amp 0 \amp -1 \amp 0 \amp -12\\ 0 \amp 1 \amp -2 \amp 0 \amp -1 \amp 0 \amp -12\\ 0 \amp 0 \amp 13 \amp 1 \amp 5 \amp 0 \amp 84\\ \hline 0 \amp 0 \amp 14 \amp 0 \amp 6 \amp 1 \amp 72\\ \end{array} \right]
\end{equation*}
This results in an optimal solution
\begin{equation*}
\boldsymbol{x} = \left[\begin{array}{rr|rrr} -12 \amp -12 \amp 0 \amp 84 \amp 0 \end{array}\right]^{\intercal}
\end{equation*}
The next exercise finds the feasible set for this problem as determines the individual basic variables. Again, this gives a feeling for how the simplex method works.
Checkpoint 7.2.2.
Graph the feasible set and label on the set the points \((x_1, x_2)\) with the step number.
Solution.
A graph of the feasible set is
The first step brought \(x_1\) into the basis and \(x_3\) leaves, so this goes to that intersection, which is still the origin.
The second step brings \(x_2\) into the basis and \(x_4\) leaves. This goes to the vertex near \((5,5)\text{.}\) After this, both free variables are in the basis.
The third step is a phase II step and maximizes the objective taking the point to near \((7,1)\text{.}\)
The last step is again phase II and moves to the vertex at \((12,12)\text{.}\) Since both \(x_1\) and \(x_2\) are free then they can both take on negative values. Also note that since the original problem is a minimum problem and both coefficients of the objective are positive, the vertex in the lower left corner would be a minimum.
Checkpoint 7.2.3.
Solve the following LOP using the full simplex method described above.
Problem 7.2.4.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp\amp z = 3x_1 + 4x_2, \amp \\ \text{such that} \amp\amp x_1 + 2x_2 \amp = 12, \\ \amp\amp 4x_1 + 3x_2 \amp = 18, \\ \amp \amp x_1 - 2x_2 \amp = 4, \\ \amp \amp x_1 + x_2 \amp \leq 10.
\end{aligned}
\end{equation*}
Solution.
This problem is in standard form, so we can write the tableau as
\begin{equation*}
\left[\begin{array}{rr|rr|r} 1 \amp 1 \amp 1 \amp 0 \amp 10\\ 1 \amp 2 \amp 0 \amp 0 \amp 12\\ 4 \amp 3 \amp 0 \amp 0 \amp 18\\ 1 \amp -2 \amp 0 \amp 0 \amp 4\\ \hline -3 \amp -4 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
Note that both \(x_1\) and \(x_2\) are free variables, so we will pivot to bring them into the basis.
\begin{equation*}
1 \mapsto \emptyset \qquad \left[\begin{array}{rr|rr|r} 1 \amp 1 \amp 1 \amp 0 \amp 10\\ 1 \amp 2 \amp 0 \amp 0 \amp 12\\ 4 \amp 3 \amp 0 \amp 0 \amp 18\\ 1 \amp -2 \amp 0 \amp 0 \amp 4\\ \hline -3 \amp -4 \amp 0 \amp 1 \amp 0\\ \end{array} \right]
\end{equation*}
\begin{equation*}
2 \mapsto \emptyset \qquad \left[\begin{array}{rr|rr|r} 0 \amp 0 \amp 11 \amp 0 \amp 60\\ 0 \amp 0 \amp 0 \amp 0 \amp 80\\ 0 \amp 11 \amp 0 \amp 0 \amp 2\\ 11 \amp 0 \amp 0 \amp 0 \amp 48\\ \hline 0 \amp 0 \amp 0 \amp 11 \amp 152\\ \end{array} \right]
\end{equation*}
At this point the two free variables are in the basis, so we can move to Phase I. However, all of the variables are feasible (and would be anyway since they are free variables), so we do not need to perform any Phase I steps.
If we move to Phase II, it appears that the solution is optimal because there are no negative numbers in the objective row. However, examining the 2nd row, the corresponding equation to this is \(0 = 80\text{,}\) which is not possible. This is because there is no solution to this problem.
Since this problem has only two variables, the constraints can be graphed.
The solution needs to be within the gray area (feasible side of the inequality constraint) as well as on all three lines. Since the three lines do not intersect at one point, there is no solution to this.
