next up previous
Next: The Fundamental Theorem of Up: Generalization to the n-var Previous: The geometry of n-var

Polytope Convexity and Extreme Points

In this paragraph we show that polytopes are convex sets. This property is important for eventually proving the Fundamental Theorem of LP. A set of points S in the n-dim space is convex, if the line segment connecting any two points tex2html_wrap_inline1751 , belongs completely in S. According to the previous mathematical definition of line segments, this definition of convexity is mathematically expressed as:



Figure 8 depicts the concept.

Figure 8: Convex sets

To show that a polytope is a convex set, we first establish that the solution space of any linear constraint (i.e., hyperplanes and half-spaces) is a convex set. Since a polytope is the intersection of a number of hyperplanes and half-spaces, the convexity of the latter directly implies the convexity of the polytope (i.e., a line segment belonging to each defining hyperplane and/or half-space will also belong to the polytope).

To establish the convexity of the feasible region of a linear constraint, let's consider the constraint:


and two points tex2html_wrap_inline1757 satisfying it. Then, for any tex2html_wrap_inline1759 , we have:



Adding Equations 21 and 22, we get:


i.e., point tex2html_wrap_inline1761 belongs in the solution space of the constraint.

A last concept that we must define before the statement of the Fundamental Theorem of LP, is that of the extreme point of a convex set. Given a convex set S, point tex2html_wrap_inline1763 is an extreme point, if each line segment that lies completely in S and contains point tex2html_wrap_inline1767 , has tex2html_wrap_inline1767 as an end point of the line segment. Mathematically,



UAL Data
Fri Jun 20 15:03:05 CDT 1997