Fundamentos de Programación Lineal y Algoritmo Símplex: Optimalidad y Restricciones

Programación lineal: la función objetivo y las restricciones son funciones lineales, todas las variables son no negativas y las restricciones son de <: cuando el objetivo es de maximizar y de >: cuando el objetivo es minimizar.

Consecuencias de linealidad: 1. Se cumplen las condiciones necesarias de optimalidad, ya que las funciones lineales son C2 y se cumple la segunda cualificación de restricciones. 2. Los óptimos de un problema lineal son globales, ya que se cumplen los teoremas local-global y de suficiencia de kuhn-tucker, puesto que el conjunto de oportunidades es convexo y la función objetivo es a la vez cóncava y convexa, por ser lineal. Por tanto, todo óptimo local o todo punto kuhn y tucker es un óptimo global. 3. La linealidad no garantiza la existencia de solución óptima global, ya que el problema podría ser infactible o no acotado, puesto que la linealidad no implica el cumplimiento del teorema de Weierstrass, es decir, no implica que el conjunto de oportunidades sea compacto. 4. Las soluciones óptimas de un problema lineal son siempre soluciones frontera, nunca interiores: solución única o de vértice: el óptimo global se encuentra en un vértice del conjunto de oportunidades;solución múltiple: el óptimo global se encuentra en más de un punto frontera. En el caso de dos variables pirncipales: la solución múltiple también se denomina solución de arista: finita: segmento lineal con un vértice en cada extremo, infinita: la arista sólo tiene un vértice en un extremo y no tiene fin en el otro.

MÉTODO SIMPLEX: consiste en partir de un vértice de su conjunto de oportunidades, SFB, e ir saltando de una a otra adyacente, de modo que la función objetivo mejore siempre. Cuando se llega a una solución desde la cual no se puede saltar a otra contigua mejor, el proceso termina, ya sea porque se ha encontrado el óptimo o porque se ha llegado a un extremo de una arista infinita a través de la cual la función objetivo mejora indefinidamente. Ventajas: no es necesario calcular todas las SFB. Cuando termina el método símplex, se sabrá si es porque se ha alcanzado el óptimo o porque el problema es no acotado.