Fundamental theorem of linear programming
ID: fundamental-theorem-of-linear-programming
For a linear program in standard equality form , , a finite attained optimum has an optimal basic feasible solution. After deleting redundant equality rows, assume has full row rank. The nonnegative standard form is part of the statement: an arbitrary polyhedron containing lines can have an optimum and no extreme point.
Choose an optimal feasible vector with the fewest positive coordinates. If its positive-support columns are dependent, there is a nonzero vector supported there with . Both signs of a sufficiently small displacement remain feasible. Optimality forces , or one sign would improve the objective. Reverse if necessary so it has a negative coordinate, and increase until the first positive coordinate becomes zero. The objective is unchanged, contradicting minimal positive support. Thus those columns are independent and the solution is basic.
For contrast, minimizing the constant zero on the unrestricted real line has an optimum at every point, but no extreme points. Converting such a model to nonnegative standard form introduces a different polyhedron where the basis theorem applies. The theorem guarantees a place to find an optimum; it does not guarantee that every optimum is a vertex or that a particular pivot rule is fast.
New to topics? Read the docs here!