= Solution
Choose an optimal feasible vector $x$ having as few positive coordinates as possible, and let
$$
S=\{i:x_i>0\}.
$$
If the columns $(A_i)_{i\in S}$ were linearly dependent, there would be a nonzero vector $h$, supported on $S$, such that $Ah=0$. For all sufficiently small positive $\varepsilon$, both
$$
x+\varepsilon h
\quad\hbox{and}\quad
x-\varepsilon h
$$
would remain feasible.
If $c^Th\ne0$, one of these two perturbations would increase the objective, contradicting optimality. Hence $c^Th=0$. We may then increase $\varepsilon$ in one of the two directions until at least one positive coordinate first becomes zero. The resulting vector is still feasible and optimal but has smaller positive support, contradicting the choice of $x$.
\b[Thus the active columns are linearly independent, so $x$ is basic. This proves the <Fundamental theorem of linear programming>: whenever the finite maximum is attained, an optimal basic feasible solution exists.]
Back to article page
