T programacion lineal
Páginas: 9 (2018 palabras)
Publicado: 23 de octubre de 2010
Programacion No Lineal
En matemáticas, la 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, cuando alguna de las restricciones o la función objetivo no son lineales.
Fomulación matemática del problema. El problemade programación no lineal puede enunciarse de una forma muy simple:
maximizar unafunción objetivo ó minimizar una función objetivo (de coste) donde:
Los 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 concava (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étodoimplica el uso de técnicas de Ramificación, 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, aunqueposiblemente 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 deKarush-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 + x2 +x1 + x2 +x1 +x2 = 2
con una función objetivo a ser maximizada
f(x) = x1 + x2
donde x = (x1, x2)Ejemplo tridimensional
La intersección de la superfie superior con el espacio de restricciones en el centro representa la solución. Otro problema simple se define por la restricciones: x1 - x2 + x3 = 2
x1 + x2 + x3 = 10
con una función objetivo a ser maximizada
f(x) = x1×2 + x2×3
donde x = (x1, x2, x3)
Problemas De Programacion No Lineal
Algunos problemas de optimización matemática secomponen de variables enteras y/o binarias lo que los convierte en problemas de tipo enteros y/o combinatoriales respectivamente, por esta razón, su solución, a través de computadores, emplea tiempos grandes cuando se usan técnicas exactas como Branch and Bound, Benders, Balas, entre otras.
Procurando mejorar la búsqueda de soluciones a este tipo de problemas se han empleado, en los últimostiempos, técnicas heurísticas y técnicas inteligentes como Colonia de Hormigas, Recocido Simulado, Búsqueda Tabú, Algoritmos Genéticos, Partículas Swarm, entre otras. En general, están basados en la aleatoriedad y en algunos criterios obtenidos de la experiencia del diseñador para encontrar una buena solución. Estas técnicas usan la función objetivo solo para evaluar la calidad de las soluciones, enmuchas ocasiones ignorando la información matemática (gradiente) del problema que se encuentra en esta función.
En el trabajo planteado se plantea un problema sujeto a ciertas restricciones donde las variables de decisión son enteras. Matemáticamente, la restricción de que las variables de decisión deben ser enteras se plantea como un polinomio cuyas raíces corresponden a los valores enteros...
En matemáticas, la 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, cuando alguna de las restricciones o la función objetivo no son lineales.
Fomulación matemática del problema. El problemade programación no lineal puede enunciarse de una forma muy simple:
maximizar unafunción objetivo ó minimizar una función objetivo (de coste) donde:
Los 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 concava (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étodoimplica el uso de técnicas de Ramificación, 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, aunqueposiblemente 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 deKarush-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 + x2 +x1 + x2 +x1 +x2 = 2
con una función objetivo a ser maximizada
f(x) = x1 + x2
donde x = (x1, x2)Ejemplo tridimensional
La intersección de la superfie superior con el espacio de restricciones en el centro representa la solución. Otro problema simple se define por la restricciones: x1 - x2 + x3 = 2
x1 + x2 + x3 = 10
con una función objetivo a ser maximizada
f(x) = x1×2 + x2×3
donde x = (x1, x2, x3)
Problemas De Programacion No Lineal
Algunos problemas de optimización matemática secomponen de variables enteras y/o binarias lo que los convierte en problemas de tipo enteros y/o combinatoriales respectivamente, por esta razón, su solución, a través de computadores, emplea tiempos grandes cuando se usan técnicas exactas como Branch and Bound, Benders, Balas, entre otras.
Procurando mejorar la búsqueda de soluciones a este tipo de problemas se han empleado, en los últimostiempos, técnicas heurísticas y técnicas inteligentes como Colonia de Hormigas, Recocido Simulado, Búsqueda Tabú, Algoritmos Genéticos, Partículas Swarm, entre otras. En general, están basados en la aleatoriedad y en algunos criterios obtenidos de la experiencia del diseñador para encontrar una buena solución. Estas técnicas usan la función objetivo solo para evaluar la calidad de las soluciones, enmuchas ocasiones ignorando la información matemática (gradiente) del problema que se encuentra en esta función.
En el trabajo planteado se plantea un problema sujeto a ciertas restricciones donde las variables de decisión son enteras. Matemáticamente, la restricción de que las variables de decisión deben ser enteras se plantea como un polinomio cuyas raíces corresponden a los valores enteros...
Leer documento completo
Regístrate para leer el documento completo.