Fundamental theorem of linear programming
In mathematical optimization, the fundamental theorem of linear programming states, in a weak formulation, that the maxima and minima of a linear function over a convex polygonal region occur at the region's corners. Further, if an extreme value occurs at two corners, then it must also occur everywhere on the line segment between them.
Statement
Consider the optimization problem
Where . If is a bounded polyhedron (and thus a polytope) and is an optimal solution to the problem, then is either an extreme point (vertex) of , or lies on a face of optimal solutions.
Proof
Suppose, for the sake of contradiction, that . Then there exists some such that the ball of radius centered at is contained in , that is . Therefore,
- and
Hence is not an optimal solution, a contradiction. Therefore, must live on the boundary of . If is not a vertex itself, it must be the convex combination of vertices of , say . Then with and . Observe that
Since is an optimal solution, all terms in the sum are nonnegative. Since the sum is equal to zero, we must have that each individual term is equal to zero. Hence, for each , so every is also optimal, and therefore all points on the face whose vertices are , are optimal solutions.
References
- http://www.linearprogramming.info/fundamental-theorem-of-linear-programming-and-its-properties/
- http://demonstrations.wolfram.com/TheFundamentalTheoremOfLinearProgramming/
This applied mathematics-related article is a stub. You can help Infogalactic by expanding it. |
This computer science article is a stub. You can help Infogalactic by expanding it. |