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"?

  • $\begingroup$ Every dictionary corresponds to a vertex on the polytope, and through the simplex method, you are moving between dictionaries that correspond to neighboring vertices. $\endgroup$ Jan 28 at 15:19
  • $\begingroup$ @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? $\endgroup$
    – Josh.K
    Jan 30 at 21:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.