Skip to Content
This question has been flagged
1 Reply
53 Views

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?

Avatar
Discard

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.

Avatar
Discard