Programacion No Lineal

INTRODUCCIÓN

La Programación no Lineal (PNL) es una parte de la Investigación Operativa cuya misión es proporcionar una serie de resultados y técnicas tendentes a la determinación de puntos óptimos para una función (función objetivo) en un determinado conjunto (conjunto de oportunidades), donde tanto la función objetivo, como las que intervienen en las restricciones que determinan el conjunto de oportunidades pueden ser no lineales. Evidentemente, la estructura del problema puede ser muy variada, según las funciones que en él intervengan (a diferencia de la Programación Lineal (PL) donde la forma especial del conjunto de oportunidades y de la función objetivo permiten obtener resultados generales sobre las posibles soluciones y facilitan los tratamientos algorítmicos de los problemas). Ello ocasiona una mayor dificultad en la obtención de resultados, que se refleja también en la dificultad de la obtención numérica de las soluciones. En este sentido, hay que distinguir entre las diversas caracterizaciones de óptimo, que sólo se emplean como técnicas de resolución en problemas sencillos, y los métodos numéricos iterativos, cuyo funcionamiento se basa en estas caracterizaciones, para la resolución de problemas más generales.

Programación no lineal

En matematicas, Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restriccioneProgramacion no lineales sobre un conjunto de variables reales desconocidas, con un función objetivo a maximizar, cuando alguna de las restricciones o la función objetivo no son lineales.

El problema de programación no lineal puede enunciarse de una forma muy simple:

maximizar una función objetivo

minimizar una función objetivo (de coste)

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.

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

Por supuesto, si son funciones lineales, entonces (1) será un problema de programa¬ción lineal y puede resolverse mediante el algoritmo simplex

3.2 Ilustración Gráfica de Problemas de Programacion No Lineal abril 14, 2010

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{ + 5x2 < 216. Compare las figuras 13.5 y 3.3. La solu¬ció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 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 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 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 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 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.1 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.2 (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 xx 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 -(x2 – x¿ )2 es una función de x2 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

...