In a degenerate linear programming problem, how can multiple distinct bases correspond to the exact same geometric vertex, and why does this phenomenon create challenges for standard pivoting rules?
This question has been flagged
1
Reply
53
Views
Multiple distinct bases can correspond to the same geometric vertex when more constraints are binding at that vertex than are required to define it. In this case, some basic variables can have a value of zero, producing different combinations of basic and non-basic variables while representing the same point.
This creates challenges for standard pivoting rules because the Simplex method may move from one basis to another without actually moving to a new geometric vertex. The algorithm can therefore make zero-improvement pivots and, in some cases, cycle through the same bases repeatedly instead of progressing toward a new solution.
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