Multiple optimal solutions
Table of Contents
When you reach a feasible dictionary where all the coefficients in the row for the objective function are negative, why does that mean you have an optimal solution? For example, if you come to the following dictionary1 you’ve found an optimal solution:
\[\begin{array}{*{10}{r}} x_1 = & 5 & & -\frac{5}{8} x_4& +\frac{1}{8} x_6\\ x_2 = & 4 & -x_3& +\frac{1}{4} x_4& -\frac{1}{4} x_6\\ x_5 = & 0 & -x_3& +2 x_4\\ z = & 13& -3 x_3& & -\frac{3}{8} x_6\\ \end{array}\]
The argument was as follows: since we know that \(x_3, x_4, x_6 \ge 0\), we have \(z = 13 -3 x_3 - \frac{3}{8} x_6 \le 13\). This tells us that \(13\) is the maximum value of \(z\), so the associated solution to this dictionary, namely \(x_3 = x_4 = x_6 = 0\), \(x_1 = 5, x_2 = 4, x_5 = 0\), is an optimal solution.
Now, in an earlier example we reached a final dictionary that was almost like this except the \(z\)-row was \(z = 13 -3 x_3 -\frac{1}{8} x_4 -\frac{3}{8} x_6\). In that case to get \(z=13\) we needed all three non-basic variables to be \(0\) so that the solution associated to the dictionary was the only optimal solution. In our current example, to get \(z=13\) only \(x_3 = x_6 = 0\) is required, so it is possible that there are other optimal solutions in which \(x_4>0\). Let’s try to find them:
Setting \(x_3 = x_6 = 0, x_4 = t\) we get \(x_1 = 5 - \frac{5}{8} t, x_2 = 4 + \frac{1}{4} t, x_5 = 2t\). Now this solution will be optimal (because it has \(z=13\)) as long as it is feasible, that is, as long as all \(x_i\) are non-negative. This boils down to \(t \ge 0\) and \(5 - \frac{5}{8} t\), because the other inequalities (namely \(2t \ge 0\), \(4 + \frac{1}{4} t \ge 0\)) have a positive coefficient of \(t\) and thus follow from \(t \ge 0\).
Putting it all together we see that for this second dictionary we have that \(x_3 = x_6 = 0, x_4 = t, x_1 = 5 - \frac{5}{8} t, x_2 = 4 + \frac{1}{4} t, x_5 = 2t\) is an optimal solution for \( 0 \le t \le 8\), and that this formula gives all the optimal solutions.
Warning: zeros in the z-row don’t automatically imply multiple optimal solutions
What if we had reached the following dictionary instead? What are the optimal solutions?
\[\begin{array}{*{10}{r}} x_1 = & 5 & & -\frac{5}{8} x_4& +\frac{1}{8} x_6\\ x_2 = & 4 & -x_3& +\frac{1}{4} x_4& -\frac{1}{4} x_6\\ x_5 = & 0 & -x_3& +2 x_4\\ z = & 13& & -\frac{1}{8} x_4& -\frac{3}{8} x_6\\ \end{array}\]
Well, since the non-basic variable \(x_3\) is missing from the \(z\)-row we might think there are again multiple optimal solutions, but see what happens when we carry out the reasoning we used above:
We have \(z \le 13\) and to get \(z=13\) we need \(x_4=x_6=0\), but \(x_3\) needn’t be zero. Setting \(x_3 = t\) we see that \(x_1 = 5, x_2 = 4-t, x_5 = -t\). What values can \(t\) take? The positivity constraint on \(x_3\) tells us that \(t \ge 0\); the positivity constraint on \(x_5\) tells us that \(-t \ge 0\), or, \(t \le 0\). So we can only have \(t=0\), which means that if we had found this final dictionary the only optimal solution to the LP would be the associated solution to the dictionary, namely \(x_3 = x_4 = x_6 = 0\), \(x_1 = 5, x_2 = 4, x_5 = 0\). This happened even though the non-basic variable \(x_3\) had a coefficient of zero in the \(z\)-row, because the basic variable \(x_5\) had value \(0\) and a negative coefficient for \(x_3\).
Warning: when more than non-basic variable has a zero coefficient things can get complicated
Don’t get the impression that it is always easy to find formulas for all of the optimal solution! The examples above gave unique solutions or a line segment of solutions because only one of the non-basic variables was free to be non-zero. If more non-basics can be positive the inequalities can become tricky. This makes sense if you think geometrically: for example if you have three variables in the original problem, the feasible solutions form a convex polytope in three dimensional space and the optimal solutions are the intersection of that polytope with a plane; this intersection could be either (1) a single vertex, (2) an edge of the polytope, (3) and entire face, which could be any convex polygon!
For example, imagine we had reached the final dictionary:
\[\begin{array}{*{10}{r}} x_1 = & 5 & & -\frac{5}{8} x_4& +\frac{1}{8} x_6\\ x_2 = & 4 & -x_3& +\frac{1}{4} x_4& -\frac{1}{4} x_6\\ x_5 = & 0 & -x_3& +2 x_4\\ z = & 13& -3 x_3& & \\ \end{array}\]
Then the optimal solutions would have \(x_3 = 0\), but \(x_4\) and \(x_6\) could take any values as long all the variables are non-negative, that is, they could take any values solving the following system of inequalities:
\[\begin{array}{*{10}{r}} 5 & -\frac{5}{8} x_4& +\frac{1}{8} x_6 & \ge 0\\ 4 & +\frac{1}{4} x_4& -\frac{1}{4} x_6 & \ge 0\\ & 2 x_4& & \ge 0\\ x_4 &\ge 0, & x_6 &\ge 0 \\ \end{array}\]
While it may not be easy in such case (specially if there are more variables!) to find all optimal solutions, it’s usually not hard to find at least two optimal solutions. You can always take all the non-basic variables to be \(0\) (this is the solution associated to the final dictionary), and then by trial and error guess a second solution. In this example, \(x_4 = x_6 = 1\) works.
This dictionary is very similar, but not exactly the same as the final dictionary in the example we did earlier.