A Simplex algorithm reaches the same basic feasible solution after several pivots, even though no mathematical error was made. Which special case could explain this behavior, and why can it occur?
Welcome!
This community is for professionals and enthusiasts of our products and services.
Share and discuss the best content and new marketing ideas, build your professional profile and become a better marketer together.
This question has been flagged
It occurs when a degenerate basic feasible solution contains one or more basic variables equal to zero, causing the Simplex algorithm to execute pivots with a step size of zero (\theta = 0); as a result, the basis changes while the objective value and physical solution remain identical, allowing the algorithm to enter a loop that continuously cycles through previously visited bases.
The special case is degeneracy, which can occur when one or more basic variables are zero, allowing pivots that change the basis without changing the solution and may cause the algorithm to return to the same basic feasible solution.
The special case is cycling, which is usually caused by degeneracy. It can occur when one or more basic variables become zero, so a pivot can change the basis without improving the objective value. If the pivot rule repeatedly selects these non-improving pivots, the Simplex algorithm can return to a previously visited basic feasible solution and continue repeating the same sequence indefinitely, even though there is no mathematical error.
The special case is degeneracy. When basic variables take on a value of zero, the algorithm can pivot to a new basis without moving the solution point, potentially causing it to return to an earlier basic feasible solution.
The special case is cycling due to degeneracy. It can occur when one or more basic variables have a value of zero, causing the Simplex Method to make pivots without improving the objective value. As a result, the algorithm can return to the same basic feasible solution repeatedly.
Yes, that explanation is correct. A simpler version is:
Cycling can occur because of degeneracy, where one or more basic variables are zero. During the Simplex method, the algorithm may pivot between different bases that represent the same basic feasible solution and eventually return to a previous basis. This creates a cycle, even though the calculations are correct.
This is degeneracy — it happens when a basic variable equals zero, so pivoting swaps one zero-valued basic variable for another without changing the solution point or objective value. The Simplex method stays at the same corner because more constraints intersect there than needed, creating redundant directions that lead nowhere new. Cycling — repeatedly revisiting the same tableaus — can occur if poor pivot choices keep rotating these zero-value variables, even though no calculation mistake was made. Anti-cycling rules (like Bland’s rule) prevent this by enforcing a consistent tie-breaking order when multiple variables qualify to enter or leave the basis.
Enjoying the discussion? Don't just read, join in!
Create an account today to enjoy exclusive features and engage with our awesome community!
Sign up