How to detect that a Linear Programming problem is unbounded with the Simplex Method

The Simplex Method is an algorithm that allows us to solve Linear Programming models that sometimes helps us identify exceptional cases with infinite optimal solutions or that the problem is unbounded. In the implementation of the Simplex Method, an unbounded problem is encountered when in any iteration there are any non-basic variables with a negative reduced cost and all elements in the column of this variable are negative or zero. That is, you cannot select a pivot (minimum quotient) to determine the variable to leave the base.

Consider the following Linear Programming model:

unbounded linear programming model

If we solve the model graphically we can see that this is unbounded. Note that the domain of feasible solutions (shaded area) is unbounded since it grows indefinitely in the direction of X2. The contours of the objective function grow at their highest rate in the direction of the vector gradient (X1,X2)=(4,6) indicating that it could be moved in that direction and indefinitely always intersect the domain of feasible solutions.

unbounded linear programming

How can we detect this situation using the Simplex Method? For one, we will carry this model to the standard form, including X3 and X4 as slack variables for constraint 1 and 2, respectively. This defines the following initial tableau for the algorithm:

simplex unbounded

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

Note: You can verify that if we had selected X1 as the variable to enter to the base and one iteration of the Simplex Method, a similar conclusion will be reached as the one presented above.

Rating: 4.7/5. From 7 votes.
Please wait...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.