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 , 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.

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 satisfying it. Then, for any , we have:

Adding Equations 21 and 22, we get:

i.e., point 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 is an
*extreme point*, if each line segment that lies completely in
*S* and contains point , has as an end point of
the line segment. Mathematically,

Fri Jun 20 15:03:05 CDT 1997