The Fundamental Theorem of Linear Programming
next up previous
Next: An algebraic characterization of
Up: Generalization to the n-var
Previous: Polytope Convexity and Extreme
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:
theorem471
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 tex2html_wrap_inline1767 denote such an optimal point. The optimal
objective value will be denoted by tex2html_wrap_inline1777 .
- Then notice that point tex2html_wrap_inline1767 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 tex2html_wrap_inline1781 . Otherwise, by moving on this line segment in the direction of
improvement of the ``isoprofit'' hyperplanes,we would be able to
obtain another point tex2html_wrap_inline1735 of the feasible region, such that
tex2html_wrap_inline1785 . But this
contradicts the assumption that tex2html_wrap_inline1767 is an optimal
point. Figure 9 depicts this argument.
[画像:figure496]
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 tex2html_wrap_inline1767 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 tex2html_wrap_inline1735
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 tex2html_wrap_inline1793 with this
variation affecting neither the constraints nor the objective.
- Hence, tex2html_wrap_inline1735 , being on the optimal ``isoprofit''
hyperplane, is another optimal point at which an additional constraint
is binding. Then, there are two possibilities: (i) tex2html_wrap_inline1735 is an
extreme point of the feasible region, in which case we are done, or
(ii) tex2html_wrap_inline1735 is interior point to another line segment lying in
the optimal ``isoprofit'' hyperplane tex2html_wrap_inline1801 , which binds, however, an additional
constraint, compared to point tex2html_wrap_inline1767 . In this case, repeating the
argument above, we establish the existence of another end point tex2html_wrap_inline1737 , determined by the binding of at least one more
constraint. Then, we repeat the entire argument for tex2html_wrap_inline1737 , and
so on. Figure 10 depicts this part of the proof.
[画像:figure516]
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.
next up previous
Next: An algebraic characterization of
Up: Generalization to the n-var
Previous: Polytope Convexity and Extreme
UAL Data
Fri Jun 20 15:03:05 CDT 1997
