3.4.2 Máximos y mínimos

Puntos minimax.

El punto minimax de la función lagrangiana es otro concepto relacionado con la
solución de un problema de optimización. Si bien su definición no le hace útil a la
hora de la resolución directa del problema, sí constituye un paso intermedio muy
importante en la obtención del problema dual, que estudiaremos más adelante. En
esta sección definimos dicho punto y estudiamos su relación con otro concepto, el
punto de silla de la lagrangiana.

La relación del punto minimax con la solución del problema de programación no
lineal se obtiene de forma inmediata sin mas que tener en cuenta que:

Min L (x, ë ) = f (x) − Max ët [g(x) − b]R m+R m+

Si gi (x) – bi ≤ 0, entonces ëi [gi(x) - bi] ≤ 0, luego

Max ëi ( gi (x) − bi ) = 0R m+ (se alcanza en ë = 0). Por tanto, si x ∈ X, Min L (x, ë )
= f (x) .R m+ Si gi (x) – bi > 0, entonces Sup ëi [gi(x) - bi] = ∞, por lo que en este
caso no se alcanza el R m+ mínimo de la Lagrangiana.

Por tanto,
Max Min L (x, ë ) = Max f (x) D R m+ X

Así pues, si (x0, ë0) es un punto minimax, x0 es una solución óptima del problema
original.

3.4.1 Puntos de inflexión

Un punto de inflexión es un punto donde cambia la curvatura de la función.

Si x=a es un punto de inflexión → f”(a)=0

En el problema nos dan 2 datos:

f(x) pasa por el punto (3,1), es decir f(3)=1

x=3 es un punto de inflexión, es decir, f”(3)=0

Con esta información, obtenemos b y d

f(3)=1 → 1=33+b32+2.3+d → 1=27+9b+6+d → 9b+d=-32

f’(x)=3x2+2bx+2

f”(x)=6x+2b

f”(3)=0 → 6.3+2b=0 → 18+2b=0 → 2b=-18 → b=-18/2=-9

9b+d=-32; 9.(-9)+d=-32; -81+d=-32; d=-32+81; d=49

Solución: b=-9 y d=49

3.4 Optimización clásica

Si la restricción no existe, o es una restricción de igualdad, con menor o igual

número de variables que la función objetivo entonces, el cálculo diferencial, da la

respuesta, ya que solo se trata de buscar los valores extremos de una función.

3.3 Tipos de problemas de programación no lineal

Los problemas de programación no lineal se presentan de muchas formas

distintas. Al contrario del método símplex para programación lineal, no se dispone

de un algoritmo que resuelva todos estos tipos especiales de problemas. En su

lugar, se han desarrollado algoritmos para algunas clases (tipos especiales) de

problemas de programación no lineal. Se introducirán las clases más importantes

y después se describirá cómo se pueden resolver algunos de estos problemas.

Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema

es de Programación lineal y puede resolverse utilizando alguno de los bien

conocidos algoritmos de programación lineal.

Si la función objetivo es cóncava (problema de maximización), o convexa

(problema de minimización) y el conjunto de restricciones es convexo, entonces se

puede utilizar el método general de Optimización convexa

Existe una variedad de métodos para resolver problemas no convexos. Uno de

ellos consiste en utilizar formulaciones especiales de problemas de programación

lineal. Otro método implica el uso de técnicas de Ramificación y poda, cuando el

problema se divide en subdivisiones a resolver mediante aproximaciones que

forman un límite inferior del coste total en cada subdivisión. Mediante

subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior

que el mejor límite inferior obtenido por alguna de las soluciones aproximadas.

Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede

ser parado antes, con la garantía de que la mejor solución será mejor que la

solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en

problemas importantes y especialmente difíciles y cuando el problema cuenta con

costes inciertos o valores donde la incertidumbre puede ser estimada en un grado

de fiabilidad apropiado.

Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias

para que una solución sea óptima.

Los tipos de problemas de programación no lineal son:

 Optimización no restringida.

 Optimización linealmente restringida.

 Programación cuadrática

 Programación convexa.

 Programación separable.

 Programación no convexa.

 Programación geométrica.

 Programación fraccional.

 Problema de complementariedad.

3.2 Ilustración grafica de problemas de programación no linea

Cuando un problema de programación no lineal tiene sólo una o dos variables, se

puede representar gráficamente de forma muy parecida al ejemplo de la Wyndor

Glass Co. de programación lineal, de la sección 3.1. Se verán unos cuantos

ejemplos, ya que una representación gráfica de este tipo proporciona una visión

global de las propiedades de las soluciones óptimas de programación lineal y no

lineal. Con el fin de hacer hincapié en las diferencias entre programación lineal y

no lineal, se usarán algunas variaciones no lineales del problema de la Wyndor

Glass Co.

La figura 13.5 muestra lo que ocurre con este problema si los únicos cambios que

se hacen al modelo de la sección 3.1 son que la segunda y tercera restricciones

funcionales se sustituyen por la restricción no lineal 9x{ + 5x2 < 216. Compare las

figuras 13.5 y 3.3. La solución óptima sigue siendo (a^ , x2) = (2,6). Todavía se

encuentra sobre la frontera de la región factible, pero no es una solución factible 

en un vértice (FEV). La solución óptima pudo haber sido una solución FEV con

una función objetivo diferente (verifique Z = 3xx + x2), pero que no necesite serlo

significa que ya no se puede aprovechar la gran simplificación utilizada en

programación lineal que permite limitar la búsqueda de una solución óptima para

las soluciones FEV

Ahora suponga que las restricciones lineales de la sección 3.1 se conservan sin

cambio, pero que la función objetivo se hace no lineal. Por ejemplo, si

entonces la representación gráfica en la figura 13.6 indica que la solución óptima es xx – x2 = 5, que de nuevo se encuentra en la frontera de la región factible. (El valor óptimo de Z es Z = 857; así, la figura 13.6 muestra el hecho de que el lugar geométrico de todos los puntos para los que Z = 857 tiene en común con la región factible sólo este punto, mientras que el lugar geométrico de los puntos con Z más grande no toca la región factible en ningún punto.) Por otro lado, si

entonces la figura 13.7 ilustra que la solución óptima es (*l5 x2 ) = (3,3), que se

encuentra dentro de la frontera de la región factible. (Se puede comprobar que

esta solución es óptima si se usa cálculo para derivarla como un máximo global no

restringido; como también satisface las restricciones, debe ser óptima para el

problema restringido.) Por lo tanto, es necesario que

un algoritmo general para resolver problemas de este tipo tome en cuenta todas

las soluciones en la región factible, y no sólo aquellas que están sobre la frontera.

Otra complicación que surge en programación no lineal es que un máximo local no

necesariamente es un máximogbbal (la solución óptima global). Por ejemplo,

considere la función de una sola variable graficada en la figura 13.8. En el

intervalo 0 < x < 5, esta función tiene tres máximos locales — x=0,x=2,x=4—pero

sólo uno de éstos—x – 4—es un máximo global. (De igual manera, existen

mínimos locales en x = 1,3 y 5, pero sólo x = 5 es un mínimo global.)

En general, los algoritmos de programación no lineal no pueden distinguir entre un

máximo local y un máximo global (excepto si encuentran otro máximo local mejor),

por lo que es determinante conocer las condiciones bajo las que se garantiza que

un máximo local es un máximo global en la región factible. Recuerde que en

cálculo, cuando se maximiza una función ordinaria (doblemente diferenciable) de

una sola variable f(x) sin restricciones, esta garantía está dada cuando

3.1 Conceptos básicos de problemas de Programación Lineal

Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con una función objetivo a maximizar, cuando alguna de las restricciones o la función objetivo no son lineales. Una suposición importante de programación lineal es que todas sus funciones (función objetivo y funciones de restricción) son lineales. Aunque, en esencia, esta suposición se cumple para muchos problemas prácticos, con frecuencia no es así. De hecho muchos economistas han encontrado que cierto grado de no linealidad es la regla, y no la excepción, en los problemas de planeación económica, por lo cual, muchas veces es necesario manejar problemas de programación no lineal, lo cual vamos a analizar enseguida. De la manera general el problema de programación no lineal consiste en encontrar: X=(X1, X2, X3, X4, XN) para Maximizar f(X), sujeta a Gi(X)<= bi para i=1,2…..m, Y X=>0, Donde f(X) y gi(x) son funciones dadas de n variables de decisión. 

DEFINICIÓN Se puede expresar un problema de programación no lineal (PNL)de la siguiente manera: Encuentre los valores de las variables que 

Como en la programación lineal z es el funcional del problema de programación no lineal y 

son las restricciones del problema de programación no lineal. Un problema de programación no lineal es un problema de programación no lineal no restringido. El conjunto de puntos , tal que es un número real, es, entonces, es el conjunto de los números reales. Los siguientes subconjuntos de (llamados intervalos) serán de particular interés:

Y en forma análoga a las definiciones de la programación lineal.

 DEFINICIÓN La región factible para el problema de programación no lineal es el conjunto de puntos que satisfacen las m restricciones de (1).