Fundamental theorem of linear programming
ID: fundamental-theorem-of-linear-programming
If a linear program has an optimal solution, it has an optimal basic feasible solution. Choose an optimum with minimal positive support. A dependence among its active columns gives a feasible two-sided perturbation; optimality makes its objective slope zero, and moving until one coordinate vanishes contradicts minimality.
New to topics? Read the docs here!