Fundamental theorem of linear programming
Encyclopedia
In applied mathematics
, the fundamental theorem of linear programming, in a weak formulation, states that the maxima and minima
of a linear function
over a convex polygon
al 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.
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.
, then there exists some 
such that the ball of radius 
centered at 
is contained in 
, that is 
. Therefore,
and
And hence we have a contradiction because
is not an optimal solution.
Therefore,
must live on the boundary of 
. If 
is not a vertex itself, it must be the convex combination of vertices of 
. That is that 
with 
and 
. Then we must have
Since all terms in the sum are positive and the sum is equal to zero, we must have that each individual term is equal to zero. Hence, every
is also optimal, and therefore all points on the face whose vertices are 
, are all optimal solutions.
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
, the fundamental theorem of linear programming, in a weak formulation, states that the maxima and minima
Maxima and minima
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
of a linear function
Linear function
In mathematics, the term linear function can refer to either of two different but related concepts:* a first-degree polynomial function of one variable;* a map between two vector spaces that preserves vector addition and scalar multiplication....
over a convex polygon
Convex polygon
In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...
al 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
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
between them.
Statement
Consider the optimization problemWhere
. 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, andAnd hence we have a contradiction because
is not an optimal solution.Therefore,
must live on the boundary of . If is not a vertex itself, it must be the convex combination of vertices of . That is that with and . Then we must haveSince all terms in the sum are positive and the sum is equal to zero, we must have that each individual term is equal to zero. Hence, every
is also optimal, and therefore all points on the face whose vertices are , are all optimal solutions.