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.
why the optimized point always appear in the interception in LP problem
0
$\begingroup$
linear-programming
1 Answers
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.
-
0The 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