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
    The constraints de$f$ine a convex polytope. Its "faces" are convex polytopes of one dimension less, this $g$oes finally down to faces in 2D, then ed$g$es in 1D and ultimately vertices in 0D.2012-09-28