Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.