Assume first p variables are greater then zero.
we then have two cases
Assume at least one yi > 0. Multiply with and subtract from above equation.
Then is a solution to Ax=b. Increase until one component . We then have a feasible solution with p-1 variables greater than zero. Repeat until the ais are linearly independent.
We now know that the solution of an LP problem (if it exists) always can be found as a basic feasible solution. In theory one could search for the solution among all possible basic solutions, and there are, at most,
basic solutions. This number quickly gets large, so we will need a method that does not need to examine all possible basic solutions.
A geometrical interpretation of a basic feasible solutions is a
vertex, and one can show that (p. 21):
x being a vertex (extreme point) is equivalent to x being a basic feasible solution.
Here an extreme point is a point x such that no points x1,x2 in the feasible region exists for which where .