Unbounded linear programs
Table of Contents
Let’s think about how the Simplex Method stops. In other words: when can we no longer pivot? We’ve already seen one way this can happen: if all coefficients in the \(z\)-row are non-positive, then we have found an optimal solution. In terms of pivoting, that happens when we can’t choose an entering variable.
But can pivoting instead fail at the stage where you choose an exiting variable? That is, could it be that you do have an entering variable but no exiting variable? Well, the exiting variable is chosen to be the basic variable imposing the most stringent constraint on the entering variable. What if none of the basic variable imposes any constraint on how much you can increase the entering variable? For that to happen we’d need all the equations for the basic variables to contain the entering variable with a non-negative coefficient. This can certainly happen, for example, the dictionary might be:
\[\begin{array}{*{10}{r}} x_1 = & 5 & & +5 x_4 & + x_6\\ x_2 = & 4 & -x_3 & + x_4 & - x_6\\ x_5 = & 2 & -x_3 & +2 x_4 & \\ z = & 13 & -3 x_3 & +2 x_4 & -3 x_6\\ \end{array}\]
Here \(x_4\) is the entering variable and we can increase \(x_4\) as much as we want without \(x_1\), \(x_2\) or \(x_5\) ever becoming negative. And as \(x_4\) keeps increasing, \(z\) also increases without bound. In this situation \(z\) does not have a maximum and we say the linear program is unbounded. We can use the entering variable to find formulas for a family of feasible solutions for which the objective function tends to infinity. Set \(x_4 = t\) and all other non-basic variables to zero: \(x_3 = x_6 = 0\). Then the basic variables become \(x_1 = 5 + 5t\), \(x_2 = 4+t\), \(x_5 = 2+2t\) and the objective function is \(z = 13 + 2t\). These solutions are feasible as long as \(t \ge 0\) and we have \(\lim_{t \to \infty} z = \infty\).
Whenever a linear problem is unbounded the Simplex Method will eventually tell us (by reaching a dictionary that has an entering variable but no exiting variable) and we can produce an unbounded one-parameter family of feasible solutions as above.
A shortcut that is sometimes available
Consider this slight variation on the previous example, imagine that while solving a linear program you came across this dictionary:
\[\begin{array}{*{10}{r}} x_1 = & 5 & & +5 x_4 & + x_6\\ x_2 = & 4 & -x_3 & + x_4 & - x_6\\ x_5 = & 2 & -x_3 & +2 x_4 & \\ z = & 13 & +3 x_3 & +2 x_4 & -3 x_6\\ \end{array}\]
The standard pivoting rule would lead us to choose \(x_3\) as the entering variable and then \(x_5\) as the exiting variable. But here \(x_4\) has positive coefficients in every row of the dictionary; this tells us already that the linear program is unbounded and that \[ x_1=5+5t, x_2=4+t, x_3=0, x_4=t, x_5=2+2t, x_6=0\] for \(t \ge 0\) is a family of feasible solutions with \(\lim_{t \to \infty} z = \infty\). So, if you notice that some variable (here \(x_4\)) shows the problem is unbounded, you can stop pivoting and go straight to the unbounded family of feasible solutions.
What happens if you don’t spot \(x_4\) and instead do the standard pivot? Nothing terrible: you just do a little extra work: since the problem is unbounded at some later stage you will be forced to discover that the problem is unbounded.