Geometry of leaving variable in simplex method

284 Views Asked by At

Why can't a leaving variable in a simplex method iteration be the entering variable in the next iteration, in terms of the geometry?

1

There are 1 best solutions below

0
On BEST ANSWER

The variable which left the building made room for another variable which made the solution better (negative reduced cost for a maximization problem). In the next step, to bring the old variable back in, would worsen the cost function (positive reduced cost). In the nondegenerate case at least.

Geometrically speaking: Bringing in a nonbasic variable into the basis and kicking out a basic variable out of the basis, is equal to a jump from an edge on the polyhedron to another edge with better cost function. From the perspective of the new edge, bringing in the old basic variable - which is now a nonbasic variable - would lead to a jump to an edge with a worse solution. And in Simplex you only jump to better solutions because of the convexity property.