# How exactly is the Simplex Method related to the idea of walking along the edges of a polyhedron?

I understand the theoretical foundation of the idea, that when I want to find the minimum of a linear function over a bounded polyhedron that I kind of only need to look at the vertices and if I am located at a vertice where all outgoing edges are not "better" for the value of my objective function then I am done because for a linear function on a convex set a local minimum is also a global one. So it is reasonable to just walk over all the vertices until we find a locally minimal one.

Right now I am working with the book "Linear Programming" by Chvatal and I understand the Simplex Method the way he is explaining it. This is explained in a very intuitive more algebraic way in terms of manipulating a system of linear equations and at the same time not making the basis variables negative. He calls this representation a dictionary.

The thing I am having trouble with is that I just can't connect the two ideas.How does the Simplex Algorithm relates to the idea of "walking along edges"?

• Every dictionary corresponds to a vertex on the polytope, and through the simplex method, you are moving between dictionaries that correspond to neighboring vertices. Jan 28 at 15:19
• @jameselmore Thank you very much, this makes sense when I think about it. Is it also true, that the non basic variables kind of correspond to the specific hyperplanes, whom intersection describes the vertex we are at right know? Jan 30 at 21:36