Inmathematical optimization, thefundamental theorem oflinear programming states, in aweak formulation, that themaxima and minima of alinear function over aconvex polygonal region occur at the region's corners. Further, if an extreme value occurs at two corners, then it must also occur everywhere on theline segment between them.

Consider the optimization problem

${\displaystyle min{c}^{T}x\text{ subject to }x\in P}$

Where${\displaystyle P=\{x\in {\mathbb{R}}^n:Ax\le b\}}$. If${\displaystyle P}$ is a bounded polyhedron (and thus a polytope) and${\displaystyle x^{\ast }}$ is an optimal solution to the problem, then${\displaystyle x^{\ast }}$ is either anextreme point (vertex) of${\displaystyle P}$, or lies on a face${\displaystyle F\subset P}$ of optimal solutions.

Suppose, for the sake of contradiction, that${\displaystyle x^{\ast }\in \mathrm{i}\mathrm{n}\mathrm{t}(P)}$. Then there exists some${\displaystyle ϵ>0}$ such that the ball of radius${\displaystyle ϵ}$ centered at${\displaystyle x^{\ast }}$ is contained in${\displaystyle P}$, that is${\displaystyle B_{ϵ}(x^{\ast })\subset P}$. Therefore,

${\displaystyle x^{\ast }-\frac{ϵ}{2}\frac{c}{||c||}\in P}$ and

Hence${\displaystyle x^{\ast }}$ is not an optimal solution, a contradiction. Therefore,${\displaystyle x^{\ast }}$ must live on the boundary of${\displaystyle P}$. If${\displaystyle x^{\ast }}$ is not a vertex itself, it must be theconvex combination of vertices of${\displaystyle P}$, say${\displaystyle x_1,...,x_t}$. Then${\displaystyle x^{\ast }=\sum _{i=1}^t{\lambda }_i{x}_i}$ with${\displaystyle {\lambda }_i\ge 0}$ and${\displaystyle \sum _{i=1}^t{\lambda }_i=1}$. Observe that

${\displaystyle 0=c^T\left(\left(\sum _{i=1}^t{\lambda }_i{x}_i\right)-x^{\ast }\right)=c^T\left(\sum _{i=1}^t{\lambda }_i(x_i-x^{\ast })\right)=\sum _{i=1}^t{\lambda }_i(c^T{x}_i-c^T{x}^{\ast }).}$

Since${\displaystyle 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,${\displaystyle c^T{x}^{\ast }=c^T{x}_i}$ for each${\displaystyle x_i}$, so every${\displaystyle x_i}$ is also optimal, and therefore all points on the face whose vertices are${\displaystyle x_1,...,x_t}$, are optimal solutions.

• Bertsekas, Dimitri P. (1995).Nonlinear Programming (1st ed.). Belmont, Massachusetts: Athena Scientific. p. Proposition B.21(c).ISBN 1-886529-14-0.
• "The Fundamental Theorem of Linear Programming".WOLFRAM Demonstrations Project. Retrieved25 September 2024.

• Linear programming
• Theorems in mathematical analysis

• Articles with short description
• Short description with empty Wikidata description