A proof from An Introduction to Optimization By Edwin Chong and Zak

Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form.

  1. If there exists a feasible solution, then there exists a basic feasible solution;
  2. If there exists an optimal feasible solution, then there exists an optimal basic feasible solution.

    Proof. We first prove part 1. Suppose that $x = [x_1,..., x_n]^T$ is a feasible solution and it has $p$ positive components. Without loss of generality, we can assume that the first $p$ components are positive, whereas the remaining components are zero. Then, in terms of the columns of $A = [a_1,..., a_p, . . . , a_n]$ this solution satisfies


There are now two cases to consider.

Case 1: If $a_1, a_2,..., a_p$ are linearly independent, then $p \leq m$. If $p = m$, then the solution $x$ is basic and the proof is completed. If, on the other hand, $p < m$, then, since $rank A = m$, we can find $m—p$ columns of A from the remaining $n — p$ columns so that the resulting set of m columns forms a basis. Hence, the solution $x$ is a (degenerate) basic feasible solution corresponding to the above basis.

Case 2: Assume that $a_1, a_2,..., a_p$ are linearly dependent. Then, there exist numbers $y_i, i = 1, . . . , p $ not all zero, such that $y_1a_1+..y_pa_p=0$

We can assume that there exists at least one $y_i$ that is positive, for if all the $y_i$ are nonpositive, we can multiply the above equation by $-1$. Multiply the above equation by a scalar $\epsilon$ and subtract the resulting equation from $x_1a_1+...x_pa_p=b$ to obtain $(x_1-\epsilon y_1)a_1+....+(x_p-\epsilon y_p)a_p=b$

Let $y=[y_1,..y_p,0,..0]^T$.then Then, for any $\epsilon$

we can write $A[x-\epsilon y]=b$

Let $\epsilon$ = min{$xi/yi : i = 1,..., p, yi > 0$}. Then, the first $p$ components o f $x — \epsilon y$ are nonnegative, and at least one of these components is zero. We then have a feasible solution with at most $p — 1$ positive components. We can repeat this process until we get linearly independent columns of A, after which we are back to Case 1. Therefore, part 1 is proved.

My question is why first $p$ components of $x-\epsilon y$ is non-negative.I thought to understand this by contradiction that suppose for any $i$ $i$ $\in$ {$1,2,..p$},

$x_i-\epsilon y_i<0$

$\implies x_i<\epsilon y_i$

$\implies \frac{x_i}{y_i}<\epsilon$.I dont know how to go further.I could have achieved contradiction if $\epsilon$ = min{$xi/yi : i = 1,..., p$},but they have defined $\epsilon$ only for $y_i>0$$


We have $x\ge0$. Then $\epsilon\ge0$. If $y_i\le0$ then $x_i -\epsilon y_i\ge0$. If $y_i>0$ then $\epsilon\le x_i / y_i$, and $$ x_i - \epsilon y_i \ge x_i - \frac{x_i}{y_i} y_i=0. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.