Programación 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.

Estructura Del Problema

Los 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

Programación No Lineal

• DefiniciónProceso 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.

Formulación matemática del problema

• 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)Donde

Métodos de resolución del problema

• 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

Métodos de resolución del problema

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

• Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.

Tipos de problemas de programación no lineal

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.

Programación Nolineal (Non Linear Programming NLP)

• NLP: Conjunto de técnicas para optimizar funciones no-lineales sujetas a restricciones de igualdad o desigualdad. Tanto las funciones como las restricciones pueden ser de una o más variables

Formulación general de un problema de optimización• Encontrar x tal que

se minimice una función objetivo f(x)sujeto a restricciones: gi(x) = bi (i=1,…, m)

gj(x) bj (j=m,…, k)

Dondex es un vector de n variables independientes

Tipos de Problemas No-lineales

• Sin restricciones • Con restricciones

Tamaño de los Problemas• Una forma de medir la complejidad de los problemas es en función del

número de variables o del número de restricciones

• Pequeña Escala: hasta 5 variables y restricciones puede ser resuelto a mano

• Escala intermedia: de 5 a 100 variables y restricciones Computador Personal o Servidor de Propósito General

• Gran Escala: más de 100 y quizás 1000 variables y restricciones Mainframe para cálculo científico (cray), explotando la estructura del problema con algoritmos paralelos

Programación Lineal Programación No Lineal

Variables elevadas al exponente 1.

Elevadas al exponente n.

Número producto de variables

Si hay productos de variables

Proporcionalidad No siempre hay proporcionalidad

Solución óptima es factible

No siempre es factible

Aditividad

DIFERENCIAS ENTRE PROGRAMACIÓN LINEAL Y PROGRAMACIÓN NO LINEAL

FORMA ESTANDAR DEL MÓDELO

Sujeta a las restricciones:a11x1 + a12x2 +….+ a1nxn < b1a21x1 + a22x2 +….+ a2nxn < b2

am1x1 + am2x2 +….+ amnxn < bmX1 ³ 0, X2 ³0, …, Xn ³0.

En Datos necesarios para un modelo de programación lineal que maneja la asignación

de recursos a actividades particular, este modelo consiste en elegir valores de x1,x2,

….,xn

Para: Optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +….+ cnxn.

• FUNCIÓN CÓNCAVA:

Función cóncava: en ese punto si f”(x) <0.Función estrictamente cóncava: si f”(x) <0.Función cóncava: si f”(x) <= 0.

• EJEMPLO

Una compañía importa aceite de coco de su pueblo natal. Usa este aceite para poder producir 2 clases de crema; tostado y quemado. El precio por libra de lo que pueda vender depende de la cantidad que produzca. En concreto si la compañía produce x1 Libras de tostado y x2 Libras de quemado, podrá vender todo lo que produzca a los siguientes precios en dólares:

Precio/libra de tostado: = 80 -3 x1Precio/libra de quemado:= 60-2×2

El costo de fabricación de x1 de pan tostado y x de quemado es: 12×1+ 8×2+ 4×1+ x2

Suponiendo que puede vender todo lo que produzca, la compañía desea determinar cuantas libras da cada crema debe programar el la producción que maximice su ganancia.

Condiciones de Concavidad y Convexidad

• FUNCIÓN CONVEXA:

Función convexa: en ese punto si g”(x)>0.Función estrictamente convexa: en ese punto si g”(x) <0.Función convexa: si g´(x)>=0.

MÉTODO DE RESOLUCIÓN DEL PROBLEMA

Si la función objetivo f es lineal y el espacio restringido es un poli topo, el problema es de Programación lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programación lineal.

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

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

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

PROGRAMACÓN NO LINEAL RESTRINGIDALos problemas de optimización no restringida no tienen restricciones,

por lo que la función objetivo es sencillamenteMaximizar f(x)

sobre todos los valores x= (x1, x2,…,xn). Según el repaso del

apéndice 3, la condición necesa ria para que una solución

específica x = x* sea óptima cuando f(x) es una función

diferenciable esCuando 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 solu ción analítica simultánea.

¿QUÉ SE PUEDE HACER EN ESE CASO? Las secciones 13.4 y 13.5 descri ben procedimientos

algorítmicos de búsqueda para encontrar x* primero para n = 1 y luego para n > 1. Estos procedimientos también tienen un papel importante en la solución de varios tipos de problemas con restricciones, que se

describirán en seguida. La razón es que muchos algo ritmos para problemas restringidos están construidos de

forma que se adaptan a versiones no restringidas del problema en una parte de cada iteración.

Cuando una variable Xj tiene una restricción de no negatividad, x- >

0, la condición ne cesaria (y tal vez) suficiente anterior cambia

ligeramente apara cada j de este tipo. Esta

condición se ilustra en la figura 13.11, donde la solución óptima de un problema con una sola variable es x= 0 aun cuando la derivada ahí es negativa y no cero. Como este ejemplo tiene una función cóncava

para maximizar sujeta a una restricción de no negatividad, el

que su derivada sea menor o igual a 0 en # = 0, es una condición

necesaria y su ficiente para que x= 0 sea óptima.

Un problema que tiene algunas

restricciones de no negatividad y que no

tiene restriccio nes funcionales es un

caso especial (m = 0) de la siguiente

clase de problemas.

EJEMPLOS DE PROGRAMACION NO LINEAL

Respuesta: Si consideramos como variables de decisión X e Y que correspondan a las respectivas coordenadas de la bodega a instalar, se puede definir el siguiente modelo de optimización no lineal sin restricciones, donde la siguiente función objetivo de minimización de distancia (Min f(x,y))

Existen múltiples aplicaciones típicas para modelos no lineales. A continuación se resume una

• Localización de Instalaciones: Considere que una empresa distribuidora de productos farmacéuticos requiere determinar la localización de una bodega que funcionará como centro de distribución y abastecimiento para sus locales en el país. En especial se busca estar a la menor distancia de los 3 principales locales de venta al público denominados A, B y C, respectivamente. Las coordenadas geográficas de dichos locales se presentan en el siguiente gráfico:

Formule y resuelva un modelo de optimización que permita determinar la localización óptima de la bodega y que minimize la distancia a los distintos locales de la empresa. Asuma que la bodega puede ser ubicada en cualquier coordenada o punto del mapa.

Planteamiento de problemas de Programación no lineal y optimización

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, es frecuente que no sea 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.

De una manera general, el problema de programación no lineal consiste en

encontrar x=(x1,x2,…,xn) paramaximizar ƒ(x),

No se dispone de un algoritmo que resuelva todos los problemas específicos que se ajustan

a este formato. Sin embargo, se han hecho grandes logros en lo que se refiere a algunos

casos especiales, haciendo algunas suposiciones sobre las funciones, y la

investigación sigue muy activa.