Fundamental theorem of linear programming explained

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

minc^Txsubjecttox\inP

Where

P=\{x\inRⁿ:Ax\leqb\}

. If

is a bounded polyhedron (and thus a polytope) and

x^\ast

is an optimal solution to the problem, then

x^\ast

is either an extreme point (vertex) of

, or lies on a face

F\subsetP

of optimal solutions.

Proof

Suppose, for the sake of contradiction, that

x^\ast\inint(P)

. Then there exists some

\epsilon>0

such that the ball of radius

\epsilon

centered at

x^\ast

is contained in

, that is

B_\epsilon(x^\ast)\subsetP

. Therefore,

x^\ast-

	\epsilon
	2

	c
	\|\|c\|\|

\inP

and

c^T\left(x^\ast-

	\epsilon
	2

	c
	\|\|c\|\|

\right)=c^Tx^\ast-

	\epsilon
	2

	c^Tc
	\|\|c\|\|

=c^Tx^\ast-

	\epsilon
	2

||c||<c^Tx^\ast.

Hence

x^\ast

is not an optimal solution, a contradiction. Therefore,

x^\ast

must live on the boundary of

. If

x^\ast

is not a vertex itself, it must be the convex combination of vertices of

, say

x_1,...,x_t

. Then

x^\ast=

	t
\sum
	i=1

λ_ix_i

with

λ_i\geq0

and

	t
\sum
	i=1

λ_i=1

. Observe that Alan o Conner wrote this theorem

0=c^T

	t
\left(\left(\sum
	i=1

λ_ix_i\right)-x^\ast\right)=c^T

	t
\left(\sum
	i=1

λ_i(x_i-x^\ast

	t
)\right)=\sum
	i=1

λ_i(c^Tx_i-c^Tx^\ast).

Since

x^\ast

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,

c^Tx^\ast=c^Tx_i

for each

x_i

, so every

x_i

is also optimal, and therefore all points on the face whose vertices are

x_1,...,x_t

, are optimal solutions.

References

http://www.linearprogramming.info/fundamental-theorem-of-linear-programming-and-its-properties/
http://demonstrations.wolfram.com/TheFundamentalTheoremOfLinearProgramming/