Teorema fundamental de programación lineal

En optimización matemática , el teorema fundamental de programación lineal establece, en una formulación débil, que los máximos y mínimos de una función lineal sobre una región poligonal convexa ocurren en los vértices de la región. Además, si un valor extremo ocurre en dos vértices, entonces también debe ocurrir en todas partes en el segmento de línea entre ellos.

Consideremos el problema de optimización

${\displaystyle \min c^{T}x{\text{ sujeto a }}x\in P}$

Dónde . Si es un poliedro acotado (y por lo tanto un politopo) y es una solución óptima al problema, entonces es un punto extremo (vértice) de , o se encuentra en una cara de soluciones óptimas. ${\displaystyle P=\{x\in \mathbb {R} ^{n}:Ax\leq b\}}$${\estilo de visualización P}$${\displaystyle x^{\ast}}$${\displaystyle x^{\ast}}$${\estilo de visualización P}$${\displaystyle F\subconjunto P}$

Supongamos, por razones de contradicción, que . Entonces existe algún objeto tal que la bola de radio centrada en está contenida en , es decir . Por lo tanto, ${\displaystyle x^{\ast}\in \mathrm {int} (P)}$${\displaystyle \epsilon >0}$${\displaystyle \épsilon}$${\displaystyle x^{\ast}}$${\estilo de visualización P}$${\displaystyle B_{\epsilon }(x^{\ast })\subconjunto P}$

${\displaystyle x^{\ast }-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\en P}$y

${\displaystyle c^{T}\left(x^{\ast }-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\right)=c^{T}x^{\ast }-{\frac {\epsilon }{2}}{\frac {c^{T}c}{||c||}}=c^{T}x^{\ast }-{\frac {\epsilon }{2}}||c||<c^{T}x^{\ast }.}$

Por lo tanto no es una solución óptima, es una contradicción. Por lo tanto, debe vivir en el límite de . Si no es un vértice en sí mismo, debe ser la combinación convexa de vértices de , digamos . Entonces con y . Observe que ${\displaystyle x^{\ast}}$${\displaystyle x^{\ast}}$${\estilo de visualización P}$${\displaystyle x^{\ast}}$${\estilo de visualización P}$${\displaystyle x_{1},...,x_{t}}$${\displaystyle x^{\ast}=\sum _{i=1}^{t}\lambda _{i}x_{i}}$${\displaystyle \lambda _ {i}\geq 0}$${\displaystyle \suma _{i=1}^{t}\lambda _{i}=1}$

${\displaystyle 0=c^{T}(\left(\sum _{i=1}^{t}\lambda _{i}x_{i}\right)-x^{\ast }\right)=c^{T}(\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 }).}$

Como es una solución óptima, todos los términos de la suma son no negativos. Como la suma es igual a cero, debemos tener que cada término individual es igual a cero. Por lo tanto, para cada , entonces cada también es óptimo y, por lo tanto, todos los puntos en la cara cuyos vértices son , son soluciones óptimas. ${\displaystyle x^{\ast}}$${\displaystyle c^{T}x^{\ast}=c^{T}x_{i}}$$Estilo de visualización x_{i}}$$Estilo de visualización x_{i}}$${\displaystyle x_{1},...,x_{t}}$

• Bertsekas, Dimitri P. (1995). Programación no lineal (1.ª ed.). Belmont, Massachusetts: Athena Scientific. pág. Proposición B.21(c). ISBN 1-886529-14-0.
• "El teorema fundamental de la programación lineal". Proyecto de demostraciones WOLFRAM . Consultado el 25 de septiembre de 2024 .