How to Detect that a Problem is Not Bounded with the Simplex Method

The Simplex Method is an algorithm that allows us to solve Linear Programming models that in certain occasions allows us to identify exceptional cases such as infinite optimal solutions or that the problem is not bounded. In this context the Simplex Method rescues the conditions established in the Fundamental Theorem of Linear Programming.

In the application of the Simplex Method, an unbounded problem is detected when in any iteration there is a non-basic variable with negative reduced cost and all the elements in the column of such variable are negative or zero. That is, a pivot cannot be selected to determine the variable that must leave the base.

Consider the following Linear Programming model:

If we solve graphically this model we can see that it is not bounded. Note that the domain of feasible solutions (shaded area) is not bounded since it grows indefinitely in the direction of the variable X2.

The contour lines of the objective function grow at its highest rate in the direction of the gradient vector \triangledown   which indicates that it could move indefinitely in that direction and always intercept the domain of feasible solutions.

How can we detect this situation (Unbounded Problem? using the Simplex Method?

To do so, we take the model to its standard form, adding X3 and X4 as slack variables of constraint 1 and 2, respectively. This defines the following initial table of the method:

Note that X2 is the non-basic variable with the most negative reduced cost and following this criterion it should be the one we enter in the base. However, it is not feasible to make the feasibility criterion or minimum quotient because the elements in the column of X2 are negative or zero. In this instance we can already state that the problem is not bounded.

It can be verified that if we select X1 as the variable that enters the base and apply an iteration of the Simplex Method, a conclusion similar to the one presented above will be reached.