Programacion no lineal
Páginas: 5 (1065 palabras)
Publicado: 20 de agosto de 2012
PROGRAMACION NO LINEAL
En matemáticas, 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 (o minimizar), cuando alguna de las restricciones o la función objetivo no son lineales.
La Programación No Lineal (PNL) proveeuna serie de herramientas que manipulan en forma estricta los espacios de búsqueda de solución de los problemas, aprovechan información matemática del problema para dirigirse en cada paso hacia un punto de buena calidad, mejorando de esta manera la llegada a la solución. Además, PNL permite el modelamiento de restricciones no lineales, una característica muy útil para la formulación dada en elpresente trabajo a los problemas que involucran variables enteras. Estas características mencionadas se deben a que en problemas de PNL, el cumplimiento de las condiciones de Karush-Kuhn-Tucker (condiciones de primer orden) y algunas condiciones de segundo orden son requeridas para evaluar la factibilidad y la optimalizad de los puntos que se van encontrando.
La metodología propuesta es aplicabletambién a problemas con no linealidad en la función objetivo, en las restricciones de desigualdad y de igualdad. Los resultados obtenidos muestran que esta propuesta es una alternativa eficiente para la solución de problemas de Programación Entera.
Formulación matemática del problema
El problema de programación no lineal puede enunciarse de una forma muy simple:
Maximizar una funciónobjetivo
o
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 poli topo, 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 deminimizació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 aresolver 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ónserá 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.Ejemplos
Ejemplo bidimensional
La intersección de la línea con el espacio de restricciones representa la solución.
Un problema sencillo puede definirse por las restricciones:
x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2
con una función objetivo a ser maximizada
f(x) = x1 + x2
Donde x = (x1, x2)
Ejemplo tridimensional
La intersección de la superficie superior con el espacio derestricciones en el centro representa la solución.
Otro problema simple se define por la restricciones: x12 − x22 + x32 ≤ 2
x12 + x22 + x32 ≤ 10
Con una función objetivo a ser maximizada
f(x) = x1x2 + x2x3
Donde x = (x1, x2, x3)
Dado el programa: Minimizar x2 - y2
s. a : x2 - y ≤ 1
Calcular sus puntos críticos y probar que no hay mínimos globales pero si que hay un mínimo local.
Solución...
En matemáticas, 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 (o minimizar), cuando alguna de las restricciones o la función objetivo no son lineales.
La Programación No Lineal (PNL) proveeuna serie de herramientas que manipulan en forma estricta los espacios de búsqueda de solución de los problemas, aprovechan información matemática del problema para dirigirse en cada paso hacia un punto de buena calidad, mejorando de esta manera la llegada a la solución. Además, PNL permite el modelamiento de restricciones no lineales, una característica muy útil para la formulación dada en elpresente trabajo a los problemas que involucran variables enteras. Estas características mencionadas se deben a que en problemas de PNL, el cumplimiento de las condiciones de Karush-Kuhn-Tucker (condiciones de primer orden) y algunas condiciones de segundo orden son requeridas para evaluar la factibilidad y la optimalizad de los puntos que se van encontrando.
La metodología propuesta es aplicabletambién a problemas con no linealidad en la función objetivo, en las restricciones de desigualdad y de igualdad. Los resultados obtenidos muestran que esta propuesta es una alternativa eficiente para la solución de problemas de Programación Entera.
Formulación matemática del problema
El problema de programación no lineal puede enunciarse de una forma muy simple:
Maximizar una funciónobjetivo
o
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 poli topo, 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 deminimizació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 aresolver 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ónserá 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.Ejemplos
Ejemplo bidimensional
La intersección de la línea con el espacio de restricciones representa la solución.
Un problema sencillo puede definirse por las restricciones:
x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2
con una función objetivo a ser maximizada
f(x) = x1 + x2
Donde x = (x1, x2)
Ejemplo tridimensional
La intersección de la superficie superior con el espacio derestricciones en el centro representa la solución.
Otro problema simple se define por la restricciones: x12 − x22 + x32 ≤ 2
x12 + x22 + x32 ≤ 10
Con una función objetivo a ser maximizada
f(x) = x1x2 + x2x3
Donde x = (x1, x2, x3)
Dado el programa: Minimizar x2 - y2
s. a : x2 - y ≤ 1
Calcular sus puntos críticos y probar que no hay mínimos globales pero si que hay un mínimo local.
Solución...
Leer documento completo
Regístrate para leer el documento completo.