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.
Asked
Active
Viewed 33 times
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.
Hagen von Eitzen
- 374,180
-
Is there exist any proof? – Mathematics Sep 28 '12 at 11:01
-
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. – Hagen von Eitzen Sep 28 '12 at 11:07
-
what about in the same dimension, says 2 D, what you mean by lower dimension? – Mathematics Sep 28 '12 at 11:13
-
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. – Hagen von Eitzen Sep 28 '12 at 11:16