   Next: The Simplex Method Up: Lecture 2 Previous: Lecture 2

## The Fundamental Theorem of Linear Programming

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.
Outline of proof
1. feasible. Assume first p variables are greater then zero. we then have two cases
(a)
ais are linearly independent. (b)
ais are linearly dependent. 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.
2.
(a)
As in 1.a since the optimality remains.
(b)
At the object function is . Due to the optimality cTy=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 x1,x2 in the feasible region exists for which where .   Next: The Simplex Method Up: Lecture 2 Previous: Lecture 2
Mats Holmstr|m
10/31/1997