En la optimización matemática , el teorema fundamental de la 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 las esquinas de la región. Además, si se produce un valor extremo en dos esquinas, también debe aparecer en todas partes del segmento de línea entre ellas.
Supongamos, en aras de la contradicción, que . Entonces existe algo tal que la bola de radio centrado en está contenido en , es decir . Por lo tanto,
- y
Por eso no es una solución óptima, 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 , decir . Luego con y . Observa eso
Desde es una solución óptima, todos los términos de la suma no son negativos. Dado que la suma es igual a cero, debemos tener que cada término individual es igual a cero. Por eso, para cada , entonces cada también es óptimo y, por lo tanto, todos los puntos de la cara cuyos vértices son , son soluciones óptimas.