As the topics, why the optimized point always appear in the interception in LP problem? I think there should be a proof but i am not sure about it.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
In LP we deal with linear constraints and a linear target function. Along any edge, face and so on, the target function will either be constant (hence you may use a vertex as optimal point just like any other point on that face/edge); or it is still a linear function, hence grows as long as you move along a fixed direction and hit a lowerdimensional face/edge and ultimately a vertex. Therefore it is sufficient to consider the vertices of the polyhedron given by the constraints.