The 2-phase Simplex Method and infeasible linear programs
Table of Contents
So far we’ve only discussed how to solve linear programs (that are in standard form and) for which the right-hand sides of the constraints are all non-negative. Why did we have that restriction? Take this LP, for instance:
Maximize \( x_1 - x_2 + x_3\)
subject to \[\begin{aligned} 2x_1 - x_2 + 2x_3 & \le 4 \\ 2x_1 -3x_2 + x_3 & \le -5 \\ -x_1 + x_2 - 2x_3 & \le -1 \\ x_1, x_2, x_3 & \ge 0. \end{aligned}\]
This problem is in standard form, but since there are negative numbers in the right hand sides of the constraints, introducing slack variables produces an initial dictionary that is not feasible:
\[\begin{array}{*{10}{r}} x_4 = & 4 & -2 x_1& + x_2& -2 x_3\\ x_5 = & -5 & -2 x_1& +3 x_2& - x_3\\ x_6 = & -1 & + x_1& - x_2& +2 x_3\\ z = & 0& + x_1& - x_2& +3 x_3\\ \end{array}\]
The solution associated to that dictionary has, for example, \(x_5 = -5\), which is negative. That means that the second constraint is violated and indeed, the associated solution has \(x_1=x_2=x_3=0\) so that \(2x_1 -3x_2 + x_3 = 0 \not \le -5\).
Remember that the simplex method proceeds by pivoting from feasible dictionary to feasible dictionary until you reach a dictionary from which you cannot pivot indicating you either have an optimal solution or the LP is unbounded (in which case you can find an 1-parameter family of solutions with objective function tending to infinity). So we can’t use this infeasible dictionary.
It’s possible that choosing a different set of variables (instead of the slack variables) to be the basic variables and solving for them would produce a feasible dictionary from which we can start the simplex method. But how can we find which set of variables to use?
Phase 1: Finding a feasible starting dictionary
If we had a feasible dictionary to begin applying the simplex method, the associated solution would be a feasible solution of the LP, that is, it would have values for the decision variables that satisfy all of the constraints in original LP. Such values don’t always exist! We’ll now explain how to simultaneously find out whether or not there are feasible solutions and, if there are, how to pick a feasible starting dictionary.
We’ll do it by considering an auxiliary linear program that is constructed from the original LP by a adding a variable we will call \(x_0\) as follows:
Minimize \( x_0 \) (or, in standard form, maximize \( -x_0\))
subject to \[\begin{aligned} 2x_1 - x_2 + 2x_3 - x_0 \le 4 \\ 2x_1 -3x_2 + x_3 - x_0 \le -5 \\ -x_1 + x_2 - 2x_3 - x_0 \le -1 \\ x_0, x_1, x_2, x_3 & \ge 0. \end{aligned}\]
Notice that this auxiliary LP only uses the constraints from the original LP, not the objective function. This is reasonable because in this first phase we are only concerned with finding a feasible starting point for the second phase (that we’ve already seen how to do); feasibility is all about the constraints and not the objective function.
This auxiliary LP obviously has feasible solutions: just take \(x_0\) very large and all constraints are satisfied. (In this example, we can take \(x_1=x_2=x_3=0\) and \(x_0 = 5\).) And this auxiliary LP has a feasible solution with \(x_0=0\) if and only if the original LP has a feasible solution! This is an important point, make sure you understand why that’s true.
If we add slack variables to the auxiliary LP we still get an infeasible starting dictionary (where I’ve called the objective function \(w\) so we can still use \(z\) for the objective function in the original LP):
\[\begin{array}{*{10}{r}} x_4 = & 4 & -2 x_1& + x_2& -2 x_3 & + x_0 \\ x_5 = & -5 & -2 x_1& +3 x_2& - x_3 & + x_0 \\ x_6 = & -1 & + x_1& - x_2& +2 x_3 & + x_0 \\ w = & & & & & - x_0\\ \end{array}\]
But this kind of infeasible dictionary coming from the auxiliary LP becomes feasible after just one pivot! The variables are chosen by a different rule than the standard pivots we’ve seen, so we’ll call this a special pivot to feasibility. The entering variable can only be \(x_0\), and for the exiting variable we’ll take the one with the most negative value, here \(x_5\). After pivoting we get:
\[\begin{array}{*{10}{r}} x_0 = & 5 & +2 x_1& -3 x_2& + x_3& + x_5\\ x_4 = & 9 & & -2 x_2& - x_3& + x_5\\ x_6 = & 4 & +3 x_1& -4 x_2& +3 x_3& + x_5\\ w = & -5& -2 x_1& +3 x_2& - x_3& - x_5\\ \end{array}\]
This dictionary is feasible and tells us that we can achieve \(w = -x_0 = -5\). Remember we’re hoping to achieve \(x_0=0\). We can use the simplex method with standard pivots starting from this feasible dictionary to maximize \(w\):
\(x_2\) enters, \(x_6\) exits:
\[\begin{array}{*{10}{r}} x_2 = & 1 & +\frac{3}{4} x_1& +\frac{3}{4} x_3& +\frac{1}{4} x_5& -\frac{1}{4} x_6\\ x_0 = & 2 & -\frac{1}{4} x_1& -\frac{5}{4} x_3& +\frac{1}{4} x_5& +\frac{3}{4} x_6\\ x_4 = & 7 & -\frac{3}{2} x_1& -\frac{5}{2} x_3& +\frac{1}{2} x_5& +\frac{1}{2} x_6\\ w = & -2& +\frac{1}{4} x_1& +\frac{5}{4} x_3& -\frac{1}{4} x_5& -\frac{3}{4} x_6\\ \end{array}\]
Now \(x_3\) enters, \(x_0\) exits:
\[\begin{array}{*{10}{r}} x_2 = & \frac{11}{5} & +\frac{3}{5} x_1& +\frac{2}{5} x_5& +\frac{1}{5} x_6 & -\frac{3}{5} x_0\\ x_3 = & \frac{8}{5} & -\frac{1}{5} x_1& +\frac{1}{5} x_5& +\frac{3}{5} x_6 & -\frac{4}{5} x_0\\ x_4 = & 3 & - x_1& & - x_6 & +2 x_0 \\ w = & & & & & - x_0\\ \end{array}\]
At this point, the auxiliary LP is solved: the maximum value of \(w=-x_0\) is 0, which means the auxiliary LP does have feasible solutions with \(x_0=0\), namely the solution associated to this dictionary: \(x_0=x_1=x_5=x_6=0, x_2= \frac{11}{5}, x_3 = \frac{8}{5}, x_4 = 3\). This (ignoring \(x_0=0\)) is also a feasible solution for the constraints of the original LP. Moreover, setting \(x_0=0\) we get a feasible dictionary for the original LP that we can use for the Simplex Method:
\[\begin{array}{*{10}{r}} x_2 = & \frac{11}{5} & +\frac{3}{5} x_1& +\frac{2}{5} x_5& +\frac{1}{5} x_6 \\ x_3 = & \frac{8}{5} & -\frac{1}{5} x_1& +\frac{1}{5} x_5& +\frac{3}{5} x_6 \\ x_4 = & 3 & - x_1& & - x_6 \\ \end{array}\]
This dictionary is just missing a \(z\)-row for the objective function. Now \(z = x_1 - x_2 + x_3\), but we can’t use this directly since the non-basic variable for the dictionary are \(x_1, x_5, x_6\). So we simply plug in the values for \(x_2\) and \(x_3\) given by the dictionary:
\[ \begin{aligned} z & = x_1 - x_2 + x_3\\ & = x_1 - (\frac{11}{5} +\frac{3}{5} x_1 +\frac{2}{5} x_5 +\frac{1}{5} x_6) + (\frac{8}{5} -\frac{1}{5} x_1 +\frac{1}{5} x_5 +\frac{3}{5} x_6) \\ & = -\frac{3}{5} + \frac{1}{5} x_1 - \frac{1}{5} x_5 + \frac{2}{5} x_6. \end{aligned} \]
Phase 2
Adding that formula for \(z\) to the above dictionary gives us a complete feasible dictionary for the original linear problem, namely:
\[\begin{array}{*{10}{r}} x_2 = & \frac{11}{5} & +\frac{3}{5} x_1& +\frac{2}{5} x_5& +\frac{1}{5} x_6 \\ x_3 = & \frac{8}{5} & -\frac{1}{5} x_1& +\frac{1}{5} x_5& +\frac{3}{5} x_6 \\ x_4 = & 3 & - x_1& & - x_6 \\ z = & -\frac{3}{5} & + \frac{1}{5} x_1 & - \frac{1}{5} x_5 & + \frac{2}{5} x_6 \end{array}\]
From there we can do standard pivots until we solve the LP. In this particular example one pivot suffices: \(x_6\) enters, \(x_4\) exits and we get the final dictionary (which is optimal):
\[\begin{array}{*{10}{r}} x_2 = & \frac{14}{5} & +\frac{2}{5} x_1& -\frac{1}{5} x_4& +\frac{2}{5} x_5\\ x_3 = & \frac{17}{5} & -\frac{4}{5} x_1& -\frac{3}{5} x_4& +\frac{1}{5} x_5\\ x_6 = & 3 & - x_1& - x_4& \\ z = & \frac{3}{5} & -\frac{1}{5} x_1& -\frac{2}{5} x_4& -\frac{1}{5} x_5\\ \end{array}\]
So the Simplex Method as we studied it initially is really only “Phase 2” of the full 2-phase Simplex Method! It’s just that we initially discussed only the case where the starting dictionary was feasible, so we could skip Phase 1.
Example of an infeasible LP
As we mention above, not all LPs are feasible: sometimes the constraints are just impossible to satisfy simultaneously. In that case, the Simplex Method discovers this in Phase 1. For example, consider the following LP:
Maximize \(x_1 - x_2 + x_3\)
subject to \[\begin{aligned} 2x_1 - x_2 - 2x_3 & \le 4 \\ 2x_1 -3x_2 - x_3 & \le -5 \\ -x_1 + x_2 + x_3 & \le -1 \\ x_1, x_2, x_3 & \ge 0. \end{aligned}\]
We form the auxiliary LP for Phase 1:
Maximize \( -x_0 \)
subject to \[\begin{aligned} 2x_1 - x_2 - 2x_3 - x_0 & \le 4 \\ 2x_1 -3x_2 - x_3 - x_0 & \le -1 \\ -x_1 + x_2 + x_3 - x_0 & \le -2 \\ x_0, x_1, x_2, x_3 & \ge 0. \end{aligned}\]
Adding slack variables we get the initial dictionary:
\[\begin{array}{*{10}{r}} x_4 = & 4 & -2 x_1& + x_2& +2 x_3& + x_0\\ x_5 = & -5 & -2 x_1& +3 x_2& + x_3& + x_0\\ x_6 = & -1 & + x_1& - x_2& - x_3& + x_0\\ w = & & & & & - x_0\\ \end{array}\]
For the special pivot to feasibility, \(x_0\) enters and \(x_5\) exits (since \(-5\) is the most negative value of any slack variable).
\[\begin{array}{*{10}{r}} x_0 = & 5 & +2 x_1& -3 x_2& - x_3& + x_5\\ x_4 = & 9 & & -2 x_2& + x_3& + x_5\\ x_6 = & 4 & +3 x_1& -4 x_2& -2 x_3& + x_5\\ w = & -5 & -2 x_1& +3 x_2& + x_3& - x_5\\ \end{array}\]
Now standard pivots: \(x_2\) enters, \(x_6\) exits.
\[\begin{array}{*{10}{r}} x_0 = & 2 & -\frac{1}{4} x_1& +\frac{1}{2} x_3& +\frac{1}{4} x_5& +\frac{3}{4} x_6\\ x_2 = & 1 & +\frac{3}{4} x_1& -\frac{1}{2} x_3& +\frac{1}{4} x_5& -\frac{1}{4} x_6\\ x_4 = & 7 & -\frac{3}{2} x_1& +2 x_3& +\frac{1}{2} x_5& +\frac{1}{2} x_6\\ w = & -2 & +\frac{1}{4} x_1& -\frac{1}{2} x_3& -\frac{1}{4} x_5& -\frac{3}{4} x_6\\ \end{array}\]
Now \(x_1\) enters, \(x_4\) exits.
\[\begin{array}{*{10}{r}} x_0 = & \frac{5}{6} & +\frac{1}{6} x_3& +\frac{1}{6} x_4& +\frac{1}{6} x_5& +\frac{2}{3} x_6\\ x_1 = & \frac{14}{3} & +\frac{4}{3} x_3& -\frac{2}{3} x_4& +\frac{1}{3} x_5& +\frac{1}{3} x_6\\ x_2 = & \frac{9}{2} & +\frac{1}{2} x_3& -\frac{1}{2} x_4& +\frac{1}{2} x_5& \\ w = & -\frac{5}{6} & -\frac{1}{6} x_3& -\frac{1}{6} x_4& -\frac{1}{6} x_5& -\frac{2}{3} x_6\\ \end{array}\]
This dictionary is optimal, so we discover that for the auxiliary LP the maximum value of \(w\) is \(-\frac{5}{6}\), or, in other words, the minimum value of \(x_0\) is \(\frac{5}{6}\). This tells us that the original LP is infeasible. (So we’re done for the original LP: there is no Phase 2, and we just answer: “the LP is infeasible”.)
Let’s go over why this means that the original is infeasible. Indeed, we just learned that in the auxiliary LP there are feasible solutions with \(x_0 = \frac{5}{6}\) but no feasible solutions with any smaller \(x_0\). That is, the inequalities: \[\begin{aligned} 2x_1 - x_2 - 2x_3 - \frac{5}{6} & \le 4 \\ 2x_1 -3x_2 - x_3 - \frac{5}{6} & \le -1 \\ -x_1 + x_2 + x_3 - \frac{5}{6} & \le -2 \\ x_1, x_2, x_3 & \ge 0, \end{aligned}\] have a simultaneous solution (namely, \(x_1=\frac{14}{3}\), \(x_2=\frac{9}{2}\), \(x_3=0\), as we see from the final dictionary), but, if we replace \(\frac{5}{6}\) with any small number they have no solution. The inequalities of the original LP correspond to setting \(x_0=0\) and so they have no solution —which is exactly what it means to say the LP is infeasible.
Sneak Preview: “Magic Coefficients”
The \(w\)-row of the final dictionary contains information you can use to find a quick proof of infeasibility for the original LP: \[ w = -\frac{5}{6} -\frac{1}{6} x_3 -\frac{1}{6} x_4 -\frac{1}{6} x_5 -\frac{2}{3} x_6. \]
The coefficients of the slack variables \(x_4\), \(x_5\) and \(x_6\) are \(-\frac{1}{6}\), \(-\frac{1}{6}\) and \(-\frac{2}{3}\), respectively. The negatives of these numbers can be used as coefficients for a linear combination of the constraints of the original LP. Multiply both sides of each inequality by the corresponding coefficient and add them up: \[\begin{aligned} \frac{1}{6}(2x_1 - x_2 - 2x_3) & \le \frac{1}{6}( 4) \\ \frac{1}{6}(2x_1 -3x_2 - x_3) & \le \frac{1}{6}(-1) \\ \frac{2}{3}(-x_1 + x_2 + x_3) & \le \frac{2}{3}(-2) \\ \hline \frac{1}{6} x_3 & \le -\frac{5}{6} \\ \end{aligned}\] The answer, \(\frac{1}{6} x_3 \le -\frac{5}{6}\), must true for any feasible solution, but this is impossible because \(x_3\) has a positivity constraint! this contradiction proves there can be no feasible solution.
We won’t be able to prove this recipe works (i.e., that the coefficients of the slacks to combine the inequalities always gives an obvious contradiction for infeasible problem) until we discuss Duality Theory later on.