# The fundamental theorem of linear programming

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

$$x_1a_1+...x_pa_p=b$$.

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.$$