How to Detect that a Problem is Not Bounded with the Simplex Method
ProgrammingThe 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.
Recent
- Exploring the Lifelines: The Majestic Rivers of Pakistan
- How did New Zealand’s continental crust get split between two plates?
- Decoding Haean, South Korea: Unraveling the Origins – Volcanic or Meteor Impact?
- The Mysteries of Earth’s Oxygen: Unraveling the Enigma Before the Great Oxygenation Event
- What is meant by intraplate volcanism?
- Are there any flights that fly east both from origin to destination and from destination to origin?
- Effects of CERN on earth’s magnetic field?
- Unveiling Earth’s Thermometric Timekeepers: The Longest Continuous Temperature Records at Airports
- Unraveling the Enigma: Tracing the Disappearance of Carbon, Neon, and Nitrogen in Earth’s History
- Unveiling the Origins: The Formation of Sand Blocks in Earth’s Sedimentary Landscape
- Unraveling the Geological Marvel: The Formation of Scala dei Turchi Staircases
- How do we know what Earth’s core is made of?
- Unraveling Earth’s Cycles: Exploring the Formation of Supercontinents Throughout History
- Unveiling the Connection: Exploring the Link between Underwater Geological Activity and the Gulf Stream’s Path along the Mid-Atlantic Ridge and South American Plate