Having established all the necessary concepts and properties of the
solution space of *n*-var LP's, we are now ready to discuss the
Fundamental Theorem of Linear Programming. This theorem can be stated
as follows:

**Proof (Sketch):** We establish the validity of
Theorem 1, through a series of observations:

- First notice that according to the previous discussion, the
feasible region of an LP is a
*polytope*, and thus,*convex*. - Furthermore, since we assume that the LP has an optimal solution, let denote such an optimal point. The optimal objective value will be denoted by .
- Then notice that point cannot be interior to a line
segment that is not perpendicular to the direction of improvement to
the
*``isoprofit''*hyperplanes - w.l.o.g., let's assume a maximization LP for our discussion - defined by vector . Otherwise, by moving on this line segment in the direction of improvement of the ``isoprofit'' hyperplanes,we would be able to obtain another point of the feasible region, such that . But this contradicts the assumption that is an optimal point. Figure 9 depicts this argument.

**Figure 9:**Why an optimal solution to an LP cannot be interior to a line segment not perpendicular to the direction of improvement of the "isoprofit" hyperplanes

- However, point can be interior to a line segment of the feasible solution space which is perpendicular to the direction of improvement of the optimal ``isoprofit'' hyperplane. This, in fact, corresponds to a situation of many optimal solutions. In this case, notice that this line segment must have at least one end defined by the fact that one (or more) additional constraint is binding at this point. Otherwise, the problem is ill-posed, since we can vary some variable(s) at will over with this variation affecting neither the constraints nor the objective.
- Hence, , being on the optimal ``isoprofit''
hyperplane, is another optimal point at which an additional constraint
is binding. Then, there are two possibilities: (i) is an
extreme point of the feasible region, in which case we are done, or
(ii) is interior point to another line segment lying in
the optimal ``isoprofit'' hyperplane , which binds, however, an additional
constraint, compared to point . In this case, repeating the
argument above, we establish the existence of another end point , determined by the binding of at least one more
constraint. Then, we repeat the entire argument for , and
so on. Figure 10 depicts this part of the proof.

**Figure 10:**Identifying an optimal extreme point on the optimal isoprofit hyperplane

- Finally, notice that every time we bind an additional
constraint, we restrict the (sub-)space of optimal solutions
considered by one ``degree of freedom''. Since an
*n*-dim space has*n*``degrees of freedom'', the number of end points visited in the argument above before we find one that it is an extreme point is*finite*. Thus, this last observation establishes the existence of an optimal extreme point for the case of many optimal solutions, and the proof is complete.

The discourse of the previous proof has also revealed a
very important property of extreme points: At these points, the number
of binding constraints is such that it allows *zero* ``degrees of
freedom'', or, in other words, these constraints define the point *
uniquely*. Starting from this observation, in the next section we
provide a series of *algebraic* characterizations of the *
extreme points*, which will eventually allow us to analytically
manipulate the set of extreme points of an LP, in the context of the
Simplex algorithm. As it has been previously mentioned, this algorithm
exploits the result stated in the *Fundamental Theorem* above, by
limiting the search for an optimal solution over the set of extreme
points of the polytope defining the LP feasible region.
In the next section, we shall show that this set is
*finite* and *discrete*, so it can even be exhaustively
enumerated. Simplex algorithm provides an efficient way to search this
set.

Fri Jun 20 15:03:05 CDT 1997