next up previous
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.
$A=[a_1 a_2 \cdots a_n], x = (x_1 x_2 \cdots x_n)^T$feasible.

\begin{displaymath}
\Rightarrow x_1 a_1 + \cdots x_n a_n = b\end{displaymath}

Assume first p variables are greater then zero.

\begin{displaymath}
\Rightarrow x_1 a_1 + \cdots x_p a_p = b\end{displaymath}

we then have two cases
(a)
ais are linearly independent.

\begin{displaymath}
\Rightarrow p \leq m \qquad \Rightarrow \mbox{ basic solution}
 \end{displaymath}

(b)
ais are linearly dependent.

\begin{displaymath}
\Rightarrow y_1 a_1 + \cdots y_p a_p = 0
 \end{displaymath}

Assume at least one yi > 0. Multiply with $\epsilon$ and subtract from above equation.

\begin{displaymath}
\Rightarrow (x_1-\epsilon y_1) a_1 + \cdots (x_p-\epsilon y_p) a_p = b
 \end{displaymath}

Then $x-\epsilon y$ is a solution to Ax=b. Increase $\epsilon$ until one component $(x_i-\epsilon y_i)=0$. 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 $x-\epsilon y$ the object function is $c^Tx-\epsilon
 c^Ty$. 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,

\begin{displaymath}
\left( \begin{array}
{c} n \\  m \end{array}\right)
 = \frac{n!}{m! \left( n-m\right)!}\end{displaymath}

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 $x = \alpha x_1 + (1-\alpha)x_2$where $0<\alpha<1$.


next up previous
Next: The Simplex Method Up: Lecture 2 Previous: Lecture 2
Mats Holmstr|m
10/31/1997