Share
Explore BrainMass

Proof in Linear Programming - extreme point

Can anyone help me to prove this? I'm really stuck with geometry in Linear Programming...

(See attached file for full problem description and equations)

---
Assume P is a polyhedron and H is a supporting hyperplane to P.
Prove that is an extreme point of if and only if is an extreme point of P.

Attachments

Solution This solution is FREE courtesy of BrainMass!

Question rewritten in available notations:
Assume P is a polyhedron and H is a supporting hyperplane to P.
Prove that N belonging to (P cross H) is an extreme point of (P cross H) if and only if N is an extreme point of P.

Answer:

Prrof of "if"
If N is an extreme point of P, any straight segment in P containing N ends at N. The same follows for any section of P by a hyperplane, therefore N must be an extreme point of (P cross H).

Proof of "only if"
If N is an extreme point of (P cross H), any straight segment in (P cross H) containing N has it at its end. A segment in P containing N but not contained in H would cross H at point N. Therefore any extension of this segment beyond N would be outside P. And therefore N must be the end point of this segment, so that N is an extreme point of P.