UNIDAD 3

                              INVESTIGACIÓN DE OPERACIONES

                          UNIDAD 3: PROGRAMACIÓN 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 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.

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:

 
3.2 ILUSTRACIÓN GRÁFICA DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL

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

La figura 13.5 muestra lo que ocurre con este problema si los únicos cambios que se hacen al modelo de la sección  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 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.

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.


3.3 TIPOS DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL

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 de problemas de programación no lineal.Optimización no restringida

Los problemas de optimización no restringida no tienen restricciones, por lo que la función

objetivo es sencillamente

Maximizar /(x)

sobre todos los valores x= (jíj, x2,…,xn). Según el repaso del apéndice 3 , la condición necesaria

para que una solución específica x = x* sea óptima cuando /(x) es una función diferenciable

es

Cuando f (x) es cóncava, esta condición también es suficiente, con lo que la obtención de x* se

reduce a resolver el sistema de las n ecuaciones obtenidas al establecer las n derivadas parciales

iguales a cero. Por desgracia, cuando se trata de funciones no lineales f (x), estas ecuaciones

suelen ser no lineales también, en cuyo caso es poco probable que se pueda obtener una solución

analítica simultánea.

Cuando una variable Xj tiene una restricción de no negatividad, x- > 0, la condición necesaria

(y tal vez) suficiente anterior cambia ligeramente a  para cada j de este tipo.

Optimización linealmente restringida                                                                                                Los problemas de optimización linealmente restringida se caracterizan por restricciones que

se ajustan por completo a la programación lineal, de manera que todas las funciones de restricción

g¡ (x) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho

si sólo se tiene que tomar en cuenta una función no lineal junto con una región factible de

programación lineal. Se han desarrollado varios algoritmos especiales basados en una extensión

del método símplex para analizar la función objetivo no lineal.

Un caso especial importante descrito a continuación es la programación cuadrática.                                                                                                                                                                                   Programación cuadrática

De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora

la función objetivo /(x) debe ser cuadrática. Entonces, la única diferencia entre éstos y un problema de programación lineal es que algunos términos de la función objetivo incluyen el

cuadrado de una variable o el producto de dos variables.

Programación convexa

La programación convexa abarca una amplia clase de problemas, entre ellos como casos especiales,

están todos los tipos anteriores cuando /(x) es cóncava. Las suposiciones son

1. /(x) es cóncava.

2. Cada una de las g¿(x) es convexa.

Programación separable

La programación separable es un caso especial de programación convexa, en donde la suposición

adicional es

3. Todas las funciones / ( x ) y g¡(x) son funciones separables.

Una función separable es una función en la que cada término incluye una sola variable, por lo

que la función se puede separar en una suma de funciones de variables individuales. Por ejemplo,

si /(x) es una función separable, se puede expresar como                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           3.4 OPTIMIZACIÓN CLÁSICA                                                                                                                                                                       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.                                                                                                                                                                                                                                                                                                          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.

 Fundamentos de Optimización 

En este ejemplo se distinguen tres elementos fundamentales: las variables del problema, una función de esas variables y un conjunto de relaciones que deben cumplir las variables del problema. Estos elementos se repetirán en todos los problemas de optimización y se definen formalmente a continuación:

1.- Variables de decisión: El primer elemento clave en la formulación de problemas de optimización es la selección de las variables independientes que sean adecuadas para caracterizar los posibles diseños candidatos y las condiciones de funcionamiento del sistema. Como variables independientes se suelen elegir aquellas que tienen un impacto significativo sobre la función objetivo.

Representaremos las variables independientes se representarán mediante vectores columna de Rn x = x1  . . .  + xn o vectores fila xt= (x1,...,xn) Aunque para los casos n = 1, 2 y 3 se emplearán las notaciones usuales de x, (x, y) y (x, y, z) respectivamente.

2.- Restricciones: Una vez determinadas las variables independientes, el siguiente paso es establecer, mediante ecuaciones o inecuaciones las relaciones existentes entre las variables de decisión. Estas relaciones son debidas, entre otras razones, a limitaciones en el sistema, a leyes naturales o a limitaciones tecnológicas y son las llamadas restricciones del sistema. Podemos distinguir dos tipos de restricciones:

(a) Restricciones de igualdad: Son ecuaciones entre las variables de la forma h (x) = h (x1,....xn)=0 donde g : A ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.

(b) Restricciones de desigualdad: Son inecuaciones entre las variables de la forma g (x) = g(x1,....xn) ≤ 0 donde A : C ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.                                                                                                                                                                                                                                                                               Puntos de Inflexión

Se define un punto de inflexión como el punto en que la función pasa de ser convexa a cóncava o de cóncava a convexa.

En la siguiente gráfica podemos ver que cuando x = 0, la gráfica pasa de ser cóncava a ser convexa, por lo que podemos decir que el punto de inflexión está en X = 0.

Una característica de los puntos de inflexión es que son los puntos donde la función derivada tiene máximos y mínimos. Si nos fijamos, cuando nos acercamos a un punto de inflexión la función cada vez crece más (o decrece menos), pero al sobrepasar el punto de inflexión la función empieza a crecer menos (o decrecer menos). Esto significa que justamente donde haya un punto de inflexión la derivada tendrá un máximo o un mínimo. Consecuentemente encontraremos los puntos de inflexión buscando ceros de la segunda derivada.                                                                                                                                                                                                                                                    Máximos y Mínimos

Loas máximos y mínimos de una función son los valores más grandes o más pequeños de ésta, ya sea en una región o en todo el dominio.

Los máximos y mínimos en una función f son los valores más grandes (máximos) o más pequeños (mínimos) que toma la función, ya sea en una región (extremos relativos) o en todo su dominio (extremos absolutos).

         

                                 

                 

                      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.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: