0
$\begingroup$

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.

1 Answers 1

0

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.

  • 0
    Is there exist any proof?2012-09-28
  • 0
    Was this not proof enough? You may also note that the polyhedron is convex. A nonconstant linear function on a convex set has extrema only on the boundary.2012-09-28
  • 0
    what about in the same dimension, says 2 D, what you mean by lower dimension?2012-09-28
  • 0
    The constraints define a convex polytope. Its "faces" are convex polytopes of one dimension less, this goes finally down to faces in 2D, then edges in 1D and ultimately vertices in 0D.2012-09-28