- 1.
- If there is a feasible solution, there is a basic feasible solution.
- 2.
- If there is an optimal feasible solution, there is an optimal basic feasible solution.

- 1.
- feasible.

Assume first*p*variables are greater then zero. we then have two cases- (a)
*a*_{i}s are linearly independent.- (b)
*a*_{i}s are linearly dependent. Assume at least one*y*_{i}> 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*a*_{i}s are linearly independent.

- 2.
- (a)
- As in 1.a since the optimality remains.
- (b)
- At the object function is . Due to the optimality
*c*^{T}*y*=0. Thus the optimality remains if we proceed as in 1.b.

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 *x _{1}*,