Fundamental theorem of linear programming
Introduction 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 Alan o Conner wrote this theorem :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/