Programacion No Lineal

3.1 Conceptos básicos de problemas de programación no 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 un función objetivo a maximizar (o minimizar), cuando alguna de las restricciones o la función objetivo no son lineales.

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.

3.2 ilustración grafica de problemas de programación no lineal

Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede re­presentar gráficamente de forma muy parecida al ejemplo de la Wyndor Glass Co. de progra­mació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 ópti­mas 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 ha­cen al modelo de la sección 3.1 son que la segunda y tercera restricciones funcionales se susti­tuyen por la restricción no lineal 9x{ + 5x₂ < 216. Compare las figuras 13.5 y 3.3. La solu­ción óptima sigue siendo (a^ , x₂) = (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 = 3x_x + x₂), 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 solu­ciones 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 x_x – x₂ = 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 lu­gar 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 x₂ ) = (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 nece­sariamente es un máximogbbal (la solución óptima global). Por ejemplo, considere la fun­ció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 fun­ción ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta ga­rantía está dada cuando

 

Una función de este tipo cuya curvatura siempre es “hacia abajo” (o que no tiene curvatura) se llama función cóncava.¹ De igual manera, si se sustituye < por >, de manera que la función tiene siempre una curvatura “hacia arriba” (o no tiene curvatura), se llama función convexa.² (Así, una función lineal es tanto cóncava como convexa.) En la figura 13.9 se pueden ver ejemplos de esto. Note que la figura 13.8 ilustra una función que no es cóncava, ni convexa pues alterna sus curvaturas hacia arriba y hacia abajo.

Las funciones de variables múltiples también se pueden caracterizar como cóncavas o convexas si su curvatura es siempre hacia abajo o hacia arriba. Estas definiciones intuitivas se fundamentan en términos precisos que, junto con cierta profundización en los conceptos, se presentan en el apéndice 2. El apéndice 2 proporciona una prueba conveniente para verifi­car si una función de dos variables es cóncava, convexa o ninguna de las dos.

La siguiente es una forma conveniente de verificar esto para una función de más de dos variables cuando la función consiste en una suma de funciones más pequeñas cada una de sólo

una o dos variables. Si cada función más pequeña es cóncava, entonces la función completa es cóncava. De manera similar, la función completa es convexa si cada función más pequeña es convexa.

 

que es la suma de las dos funciones más pequeñas dadas en los paréntesis cuadrados. La pri­mera función más pequeña 4*! – x\ es una función de la variable x_x nada más, por lo que puede verse que es cóncava si se observa que su segunda derivada es negativa. La segunda función más pequeña -(x₂ – x¿ )² es una fimción de x₂ y por lo que se puede aplicar la prueba para funciones de dos variables dada en el apéndice 2. De hecho, este apéndice usa esta función en particular para ilustrar la prueba y encuentra que la función es cóncava. Como las dos funciones más pequeñas son cóncavas, la función completa f (jVj ,x₂,x₃) debe ser cóncava.

Si un problema de programación no lineal no tiene restricciones, el hecho de que la fun­ción objetivo sea cóncava garantiza que un máximo local es un máximoglobal. (De igual mane­ra, una función objetivo convexa asegura que un mínimo local es un mínimo global.) Si existen restricciones, entonces se necesita una condición más para dar esta garantía, a saber, que la re­gión factible sea un conjunto convexo. Como se analiza en el apéndice 2, un conjunto conve­xo es sencillamente un conjunto de puntos tales que, para cada par de puntos de la colección, el segmento de recta que los une está totalmente contenido en la colección. Así, la región fac­tible en el problema original de la Wyndor Glass Co. (vea la figura 13.6 o 13.7) es un conjun­to convexo. De hecho, la región factible para cualquier otro problema de programación lineal es un conjunto convexo. De igual manera, la región factible de la figura 13.5 también es un conjunto convexo.

En general la región factible para un problema de programación no lineal es un conjunto convexo siempre que todas las funciones g¡ (x) [para las restricciones g¿ (x) < b_{ ] sean conve­xas. Para el ejemplo de la figura 13.5, las dos g_t (x) son convexas, ya que g_x (x) = x_x (una fun­ción lineal es automáticamente cóncava y convexa) y g₂ (x) = 9x\ + 5x\ (tanto 9x\ como 5x₂ son funciones convexas, por lo que su suma es una función convexa). Estas dos funciones convexas g¡ (x) conducen a que la región factible de la figura 13.5 sea un conjunto convexo.

Ahora se analizará qué pasa cuando sólo una de estas funciones g¡ (x) es una función cón­cava. En particular, suponga que el único cambio que se hace al ejemplo de la figura 13.5 es

son funciones cóncavas. La nueva región factible mostrada en la figura 13.10 no es un conjun­to convexo. <Por qué? Porque contiene pares de puntos, como (0, 7) y (4, 3), tales que parte del segmento de recta que los une no está en la región factible. En consecuencia, no se puede garantizar que un máximo local sea un máximo global. De hecho, este ejemplo tiene dos má­ximos locales (0, 7) y (4, 3), pero sólo (0, 7) es un máximo global.

Entonces, para garantizar que un máximo local sea un máximo global para un problema de programación no lineal con restricciones (x) < b¡ (i = 1,2,…, m) y x > 0, la función obje­tivo /(x) debe ser cóncava y cada g_í (x) debe ser convexa. Un problema de este tipo se llama problema de programación convexa y es una de las clases más importantes de la programación no lineal que se estudiará en la siguiente sección.

3.3 Tipos De Problemas De Programacion No Lineal 

Los problemas de programación no lineal se presentan de muchas formas distintas. Al con­trario del método símplex para programación lineal, no se dispone de un algoritmo que re­suelva 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 introduci­rán las clases más importantes y después se describirá cómo se pueden resolver algunos de es­tos 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:

1.       Optimización no restringida.
2.       Optimización linealmente restringida.
3.       Programación cuadrática
4.       Programación convexa.
5.       Programación separable.
6.       Programación no convexa.
7.       Programación geométrica.
8.       Programación fraccional.
9.       Problema de complementariedad.

  

ALGORITMOS SIN RESTRICCIÓN

En esta sección se presentarán dos algoritmos para el problema no restringido: el algoritmo de búsqueda directa y el algoritmo de gradiente.  

   

 Método de búsqueda directa  

Los métodos de búsqueda directa se aplican principalmente a funciones estrictamente unimo- dales de una variable. Aunque puede parecer trivial el caso, la sección 21.1.2 muestra que la optimización de funciones de una variable juega un papel clave en el desarrollo de los algorit­mos de varias variables, más generales.  

La idea de los métodos de búsqueda directa es identificar el intervalo de incertidum- bre que comprenda al punto de solución óptima. El procedimiento localiza el óptimo estre­chando en forma progresiva el intervalo de incertidumbre hasta cualquier grado de exactitud que se desee.  

En esta sección se presentan dos algoritmos estrechamente relacionados: los métodos de búsqueda dicótomo y de sección dorada (o áurea). Ambos buscan la maximización de una fun­ción unimodal/(x) en el intervalo a ^ x < b, que se sabe que incluye el punto óptimo x*. Los dos métodos comienzan con /₀ = (a, b) que representa el intervalo inicial de incertidumbre.  

Paso general i. Sea /, _ , = (x_D x_R) el intervalo actual de incertidumbre (en la iteración 0, x_L = a y x_R = b). A continuación se definen x_x y x₂ tales que  

xj^ ^ ^ x₂ ^ x_r  

El siguiente intervalo de incertidumbre, /_z, se define como sigue:  

1. Si f(x_x) > /(x₂), entonces x_L < x* < x₂. Se definen x_R = x₂ e /, = (x_L, x₂) (véase la figura 21.2[a]).
2. Si f(x_x) < f(x₂\ entonces x_x < x* < x_R. Se definen x_L = x_x e I¡ = (x_h x_R) (véase la figura 21.1 [b]). .
3. Si f{x\) = /(jc₂), entonces x_x < x* < x₂. Se definen x_L = x₂ e /, = (x_b x₂).

  

La manera en que se determinan x_x y x₂ garantiza que /, < /,_ _p como se demostrará en breve. El algoritmo termina en la iteración ksil_k< A, donde A es un grado de exactitud defi­nido por el usuario.                                                                                                                                                                                        *  

La diferencia entre los métodos dicótomo y de sección dorada estriba en la forma en que se calculan x_x y x₂. La tabla siguiente presenta las fórmulas.  

  

 

En el método dicótomo los valores jc, y x₂ se encuentran simétricos respecto del punto medio del actual intervalo de incertidumbre. Esto significa que 

 

La aplicación repetida del algoritmo garantiza que la longitud del intervalo de incertidumbre se acercará al nivel de exactitud deseado, A. 

En el método de la sección dorada la idea es de mayor involucramiento. Se puede apre­ciar que cada iteración del método dicótomo requiere calcular los dos valores/(jc,) y f(x₂), P^e” ro termina por descartar alguno de ellos. Lo que propone el método de la sección dorada es ahorrar cálculos mediante el reuso del valor descartado en la iteración inmediata siguiente. Para definir 0 < a < 1 

 

Cuando el intervalo de incertidumbre /, en la iteración i es igual a (jc_¿, x₂) o a (x_u x_R). Conside­re el caso en que /, = (jc_l, x₂), lo cual significa que x_x está incluido en /,. En la iteración /+1, seleccione x₂ igual a jc, de la iteración /, lo cual lleva a la siguiente ecuación: 

x₂(iteración i+l) = x_{(iteración i) 

 

 

Comparado con el método dicótomo, el método de la sección dorada converge más rápida­mente hacia el nivel deseado de exactitud. Adicionalmente, cada iteración en el método de la sección dorada requiere la mitad de los cálculos, en virtud de que recicla siempre un conjunto de los cálculos correspondientes a la iteración inmediata anterior. 

EJEMPLO

 

El máximo valor de f(x) ocurre en x = 2. La siguiente tabla muestra los cálculos para las iteraciones 1 y 2, usando el método dicotomo y el de la sección dorada. Supondremos que A = 0.1. 

 

Al continuar de la misma forma, el intervalo de incertidumbre terminará por estrecharse hasta la tolerancia A deseada. 

  

La plantilla ch21DichotomousGoldenSection.xls de Excel está diseñada para manejar cualquiera de estos dos métodos en forma automática. Los datos son/(*), a,b y A. La función f{x) se captura en la celda E3 como sigue: 

= IF(C3< = 2,3*C3, (-C3+20)/3) 

3.4 Optimizacion Clasica

La teoría de optimización clásica o programación matemática está constituida por un conjunto de resultados y métodos analíticos y numéricos enfocados a encontrar e identificar al mejor candidato de entre una colección de alternativas, sin tener que enumerar y evaluar explícitamente todas esas alternativas. Un problema de optimización es, en general, un problema de decisión.

Con el fin de ilustrar de forma adecuada la estructura y composición de un problema de optimización, introduciremos a continuación un sencillo ejemplo.

Ejemplo 1(Construcción de una caja con volumen máximo) Supongamos que queremos determinar las dimensiones de una caja rectangular de forma que contenga el mayor volumen posible, pero utilizando para ello una cantidad fija de material. El problema en forma abstracta se podría plantear en los siguientes términos Maximizar Volumen de la caja sujeto a Área lateral fija Con el fin de resolver este problema habrá que modelizarlo matemáticamente, es decir tendremos que expresarlo en términos matemáticos.

El primer paso para modelizar un problema de optimización es identificar y definir las variables que están implicadas en dicho problema, en este caso y puesto que estamos tratando de determinar el tamaño de una caja rectangular, la opción más clara es considerar como variables sus tres dimensiones rectangulares usuales (ancho, largo, alto) y que representamos con x, y, z. Con estas variables, la función para la que tenemos que encontrar el mejor valor será el volumen de la caja que puede expresarse como V (x, y, z) = xyz.

 A continuación debemos tener en cuenta las limitaciones existentes sobre el material. Como este material se utiliza para construir las paredes de la caja, necesitaremos considerar el área lateral de la misma, y si la caja tiene tapa, dicha área será A (x, y, z)= 2(xy + yz + zx).

Por último, teniendo en cuenta que las dimensiones de la caja no pueden ser negativas el problema puede expresarse matemáticamente como Maximizar xyz sujeto a 2 (xy + yz + zx) = A x, y, z ≥ 0.

3.4.1 Puntos De Inflexion

Puntos estacionarios.

 Procedemos entonces, tras haber establecido ciertos conceptos básicos en la sección anterior, a resolver el problema

 Maximizarsujeta a :f (x)g(x) ≤ b(PRD)

donde suponemos que se dan condiciones de diferenciabilidad sobre f y g y que el conjunto D es abierto. En esta situación, tenemos aseguradas ciertas condiciones de diferenciabilidad sobre la función de Lagrange L. Empezaremos definiendo el concepto de punto estacionario de Kuhn-Tucker a partir de L. Tras ello, estudiaremos su relación con las soluciones del problema (PRD). Como veremos, serán necesarias condiciones de convexidad en los teoremas de suficiencia, y no así en los de necesariedad (donde, eso sí, hará falta incluir cualificaciones de restricciones).

Así pues, definimos

supuesto que x0 es un punto factible:

Una  vez  definido  este  concepto,  veamos  seguidamente  los  teoremas  que  lo relacionan con las soluciones del problema (PRD). Empezaremos dando el teorema de condiciones necesarias, es decir, el teorema en el que se establecen qué condiciones necesariamente deben verificar los óptimos de (PRD).

Como se observa, gracias a la formulación de punto estacionario de Kuhn-Tucker (4), este teorema afirma que, si se verifica la cualificación de restricciones de independencia lineal en x0, entonces necesariamente todo óptimo local del problema es un punto estacionario   de   Kuhn-Tucker.   Existe   otro   concepto   de   punto   estacionario   (punto estacionario de Fritz-John) más general que el de Kuhn-Tucker, que no necesita de la cualificación de restricciones para que se establezca esta condición necesaria.

 Este  teorema  admite  exactamente  la  misma  formulación  para  el  problema  de mínimo,  teniendo  simplemente  en  cuenta  las  definiciones  de  punto  estacionario  para mínimo. Así, por ejemplo, la condición quedaría:

∇f (x ) + ∑ ëi∇gi (x ) = 0 .00i∈I

 Pasamos ahora a dar el teorema de condiciones suficientes, es decir, el teorema que afirma  bajo  qué  condiciones  un  punto  estacionario  de  Kuhn-Tucker  es  máximo  del problema. Ya se ha comentado que hace falta en este caso exigir condiciones de convexidad

sobre las funciones del problema. Realmente, basta con unas suposiciones un poco más suaves que la convexidad global, si bien aquí no vamos a especificarlas:

24 sobre las funciones del problema. Realmente, basta con unas suposiciones un poco más suaves que la convexidad global, si bien aquí no vamos a especificarlas

 Este teorema admite una formulación similar para el problema de mínimo, con las correspondientes definiciones de los puntos estacionarios, y suponiendo que la función f sea convexa.

 Si observamos con detenimiento las condiciones de punto estacionario que hemos desarrollado  en  esta  sección,  podremos  ver  su analogía con el caso en el que existan restricciones de igualdad. En concreto, desde un punto de vista intuitivo, el proceso se podría interpretar de la siguiente forma: en primer lugar, se identifican las restricciones activas en el punto en cuestión. Posteriormente, se toman las condiciones de primer orden para problemas con restricciones de igualdad, teniendo en cuenta sólo las mencionadas restricciones activas (que, en el punto bajo estudio, se pueden considerar de igualdad). Finalmente, se añade la condición adicional de no negatividad sobre los multiplicadores óptimos, que, según vimos previamente, garantizan que la función objetivo no mejora al moverse hacia el interior relativo de las restricciones activas.

3.4.2 Maximos Y Minimos

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. 

Pasamos ahora a dar los teoremas que relacionan los conceptos de punto de silla de L y punto minimax. Veremos que dicha relación es casi una equivalencia, en el sentido de que todo  punto  minimax  es  punto  de  silla,  y  todo  punto  de  silla  es  un  punto  minimax considerado sobre conjuntos mas restringidos. 

 

Como hemos expuesto anteriormente, para obtener el teorema recíproco es necesario restringir los conjuntos de definición del punto minimax. Previamente, hemos visto que la primera parte de la igualdad debe ser de la forma 

 

 Definimos, por tanto, 

N = {ë ∈ R m +  / ∃ Max ( f ( x ) − ët [g(x) − b ])},  N ⊂ R m + 

Entonces, la segunda parte de la igualdad se debe expresar como sigue: 

Min Max L (x, ë ) 

Por tanto, el punto minimax que buscamos ahora es de la forma: 

 

 

Para el problema de mínimo, el punto minimax toma la forma: 

  

tomando  además  la  función  lagrangiana  correspondiente  a  este  problema.  Con  esta definición, los teoremas 16 y 17 serían válidos de forma análoga para esta formulación. 

4.1.- Dualidad en Programación Matemática. 

El concepto de dualidad nace estrechamente ligado al de punto minimax que se desarrolló en la sección anterior. Así, dado nuestro problema original, recordemos la definición de punto minimax: se trata de un par (x0, ë0) que verifica: 

 L (x0 , ë0 ) = Max Min L (x, ë ) = Min Max L (x, ë ) , 

donde
L(x, ë) = f(x) – ët[g(x) 

que es, precisamente, el problema de partida, que llamaremos a partir de ahora Problema 

Primal (PP). 

Por  otro  lado,  el  segundo  término  de  la  igualdad  del  punto  minimax  se  puede expresar como:

Min 

N

õ (ë ),

tomando  además  la  función  lagrangiana  correspondiente  a  este  problema.  Con  esta definición, los teoremas 16 y 17 serían válidos de forma análoga para esta formulación. 

Primer Y Segundo Ejercicio