In the previous section we showed that if an LP has a (bounded) optimal solution, then it has (at least) one which corresponds to an extreme point of its feasible region. To exploit this result algorithmically, we need an algebraic characterization of the extreme point concept. This is the topic of this section.
The starting point of this discussion is the observation made at the end of the previous section, that at an extreme point, the set of binding constraints is such that it characterizes the point uniquely. Let's try to investigate what is the algebraic structure implied by this statement. Also, staying close to the general spirit of our discussion, let's examine this issue in an inductive manner.
with a unique solution, i.e., with
Such a system of equations is characterized as linearly independent, and geometrically, it corresponds to two intersecting straight lines.
corresponds to the intersection of two planes, i.e., a straight line.
Defining a unique point in the 3-dim space requires three linearly independent equations, i.e.,