1
$\begingroup$

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

$\endgroup$
2
  • $\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$
    – jameselmore
    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

0

Reset to default

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.