Fundamental theorem of linear programming
= Fundamental theorem of linear programming
{c}
{wiki}
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.