Past exam of the mathematics course of the University of Cambridge / 2021 / ib / Paper 4 / 18H / b / Solution

Choose an optimal feasible vector $x$ having as few positive coordinates as possible, and letIf 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 $\epsilon$, bothwould remain feasible.

If $c^{T}h\ne 0$, one of these two perturbations would increase the objective, contradicting optimality. Hence $c^{T}h=0$. We may then increase $\epsilon$ 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$.

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.

Solved by gpt-5.6-sol high.