Spelling suggestions: "subject:"relación lagrange""
1 |
Evaluación Técnica de Códigos Computacionales para la Optimización de la Operación de Corto Plazo en el SINGRomero Hernández, Cristian Leonardo January 2008 (has links)
El objetivo general del presente trabajo de título es realizar, mediante la aplicación de criterios
técnicos de ingeniería, una evaluación técnica del desempeño de los algoritmos de Relajación
Lagrangeana (RL) y Branch and Bound (B&B) en la búsqueda de soluciones para el problema de
optimización de corto plazo en el sistema eléctrico interconectado del norte grande (SING).
En la primera parte de la memoria se muestra el planteamiento general del problema de optimización
de la operación de corto plazo, el cual corresponde a un problema de optimización entero-mixto y un
conjunto de restricciones lineales mediante las cuales se establecen las características técnicas del
sistema. Por otra parte, la función objetivo de dicho problema de optimización corresponde a la
minimización de los costos asociados a la operación de las unidades en el horizonte de tiempo
evaluado.
Posteriormente, se muestra una revisión del estado del arte presentando algunas de las principales
técnicas utilizadas para resolver este tipo de problema: Lista de Prioridad, Programación Dinámica,
Unit Decommitment, RL, Método de Benders, B&B y Algoritmos Genéticos.
Para realizar la evaluación sobre los algoritmos de RL y B&B, se realizan programas en Matlab de
dichos métodos con el objeto de realizar pruebas que permitan efectuar un análisis comparativo de los
rendimientos de ambos algoritmos.
Se aplican dichos programas para resolver problemas de predespacho en un modelo reducido del
SING. De esta forma se puede observar el rendimiento de cada algoritmo respecto de su capacidad de
obtener soluciones factibles, calidad de las soluciones, uso de heurística para generar soluciones y
tiempos de ejecución requeridos. Adicionalmente, se puede estudiar la flexibilidad de ambos
algoritmos para considerar restricciones de mayor complejidad y sus limitaciones para resolver
predespacho en sistemas de dimensiones reales.
Se concluye que el algoritmo que presenta un rendimiento que permite resolver de manera más
eficiente el problema de predespacho en el SING corresponde al algoritmo RL, lo anterior debido
principalmente a los tiempos de ejecución requeridos para su aplicación en sistemas de dimensiones
reales y a que las soluciones generadas presentan una precisión del orden del 99% respecto a las
soluciones generadas por el otro algoritmo. Adicionalmente, se puede acotar que las actuales políticas
de operación aplicadas en el SING no representan una gran complejidad de programación y por lo
tanto, la heurística requerida no presenta una complejidad adicional.
|
2 |
Evaluación de un enfoque de relajación Lagrangeana en un modelo de optimización estocástica para la planificación de cosecha forestalLagomarsino Gatica, Emanuel José January 2016 (has links)
Ingeniero Civil Industrial / En esta memoria se utilizará el método de Relajación Lagrangeana a un problema de la
vida real en el área de la planificación forestal. A esta planificación, además, se le agregará
incertidumbre en el precio de las maderas, en base a la consideración de un número N de
escenarios, lo cual aumenta la dificultad para la resolución de la instancia, lo que lleva a que
se quiera evaluar el desempeño de este enfoque para la resolución de problemas con estas
características.
El objetivo principal del proyecto es lograr encontrar una solución cercana al óptimo para
un modelo de programación lineal estocástico buscando maximizar el beneficio neto de la
planificación de la cosecha de bosques, para instancias con más de 200 escenarios a partir de
una Relajación Lagrangeana del problema y evaluar el desempeño de este enfoque conforme
al número de escenarios y en comparación a CPLEX.
Para lograr esto, se empleó la siguiente metodología:
1. Entender la Importancia de la evaluación de esta herramienta.
2. Plantear el Modelo de Programación Lineal Estocástico acorde al problema forestal.
3. Indagación en Bibliografía de la Relajación Lagrangeana.
4. Elección de restricciones a relajar, desarrollo de algoritmo y heurística de la Relajación
Lagrangeana.
5. Análisis de los Resultados.
Al evaluar los resultados, se pudo notar que la Relajación Lagrangeana no tenía un comportamiento
estable al resolver el problema con un grafo de 290 arcos, 223 nodos y 15 bosques,
esto comparado con casos más pequeños en el que su comportamiento es más típico en cuanto
a la suavidad del descenso de la curva hacia el óptimo. A pesar de ello, se logró mejorar su
comportamiento al normalizar los multiplicadores en cada iteración. Se emplearon métodos
en que se fijaron variables binarias al valor 1, cuando cumplían en cierto grado las restricciones
de no anticipatividad. Esto acompañado con la técnica de Warm Start entregaron
resultados satisfactorios hasta los 162 escenarios, donde los tiempos de la Relajación Lagrangeana
se dispararon dejando una fuerte impresión de que la metodología puede no ser la más
adecuada para este tipo de problemas. Sin embargo, esto puede estar sesgado por la elección
del software y/o las metodologías de programación empleadas por el alumno, por lo que no
se considera definitivo el que se deba cerrar la investigación de esta metodología para los
problemas de índole forestal.
|
3 |
Estudio comparativo de la relajación lagrangeana y la programación entera-mixta en el problema del pre-despacho de sistemas medianosLeañez Grau, Frank José Demetrio January 2013 (has links)
Magíster en Ciencias de la Ingeniería, Mención Ingeniería Eléctrica / El trabajo de tesis compara en forma sistemática las diferencias de rendimiento entre las principales metodologías de solución del problema de Predespacho (UC) y muestra la aplicación de la relajación lagrangeana a casos reales del Sistema Interconectado del Norte Grande (SING). Se propone una metodología para la creación de casos sintéticos de UC que permitan obtener diversidad a distintas escalas sin que resulten alejados de la realidad, siendo ésta la principal contribución del presente trabajo junto con los resultados estadísticos que favorecen MIP por sobre LR para sistemas de medianas dimensiones.
La relajación lagrangeana (LR) y la programación entero mixta (MIP) son los métodos de solución que han encontrado el mayor número de aplicaciones prácticas al UC. Sin embargo, las comparaciones de rendimiento y calidad entre ambas, aunque propuestas conceptualmente y cuyas nociones intuitivas se encuentran dispersas en la bibliografía especializada, adolecen de falta de generalidad, escasa representación de la realidad, ausencia de especificaciones computacionales o, inclusive, éstas pueden haber quedado obsoletas. Ante la escasez de librerías de modelos de UC o, al menos, de métodos de creación de casos de aplicación, en el presente trabajo se propone y aplica un generador de casos sintéticos de prueba de UC. Este método formula casos basados en la combinación de datos estandarizados con la generación aleatoria de parámetros. De esta forma, los problemas de UC creados adquieren diversidad (universalidad) sin que las instancias se alejen demasiado de la realidad. La diversidad de las instancias generadas es controlada mediante los parámetros de las funciones de distribución de probabilidades, tanto para la selección de unidades candidatas como para la variedad en los parámetros técnicos característicos. Estas instancias son resueltas por los métodos para resolver el UC en una misma plataforma computacional.
El método de LR encuentra soluciones factibles para 429 instancias de las 480 (89,4%), cumpliendo con el gap objetivo de 0,01% en tan sólo 90 casos (18,8%), mientras que el MIP encuentra la solución óptima para el 98,3% de los casos. Los resultados obtenidos verifican que para el rango de 10 a 100 unidades, la mejor solución entera factible alcanzada por LR tiene una menor calidad (valor mayor de la función objetivo en problemas de minimización) que la encontrada por el optimizador MIP. Los resultados permiten determinar que el sobrecosto (respecto al MIP) esperado de las soluciones mediante LR fue de 6,03%. El aumento de la dispersión en los parámetros técnicos beneficia ambos métodos al obtener la mejor solución factible en menores tiempos de ejecución. De esta forma se muestra que no sólo la calidad de la solución por LR se ve afectada por unidades similares, sino que también afecta al método MIP. Se comprueba que a medida que los problemas son más difíciles (juzgando por la adaptabilidad y por el número de unidades), la cota inferior de LR resulta en promedio mayor (mejor) a la cota inferior promedio por MIP.
Respecto al caso práctico inspirado en el SING, la calidad de la solución por LR se ve especialmente deteriorada cuando las restricciones de mínimos técnicos de las unidades obligan que la solución óptima entera se aleje de la relajación lineal. Si bien para este caso la resolución mediante MIP también se dificulta requiriendo de hasta un 60% más tiempo de ejecución, este efecto es comparativamente menor al deterioro de la calidad de la solución observada mediante LR (que resulta hasta 4.5% mayor que MIP). Conceptualmente, este hallazgo se explica por los valores de actualización de los multiplicadores en LR, lo que se traduce en imposibilidad para explorar zonas del espacio de soluciones.
Como conclusión general, el estudio entrega evidencia práctica a favor de la tendencia observada en la revisión bibliográfica en relación a privilegiar desarrollos de tipo MIP, la cual es aplicable a sistemas medianos como el caso real en estudio basado en el SING chileno. Esta conclusión no se extiende para otros sistemas reales de grandes dimensiones (eg. CAISO, MISO, UCTE). Como futuros desarrollos se sugiere explorar esquemas integrados LR-MIP explotando las mejoras de la cota inferior que proporciona LR en comparación con la relajación lineal del MIP y la creación de soluciones factibles por el método LR para inicializar el MIP.
|
4 |
Desarrollo de un Modelo Estocástico de Planificación Minera Utilizando Escenarios Probabilísticos del Precio del CobreCarvallo Löhr, Luis Felipe January 2009 (has links)
El problema abordado en este trabajo consiste en evaluar cuál es el mejor enfoque para
enfrentar la planificación minera considerando el precio como un valor incierto. Lo anterior
implica determinar la extracción óptima y como el flujo de material será manejado al interior
de la mina. Para ello se utilizó una modelación, basada en la mina de cobre de El Teniente,
que considera un horizonte de planificación de 5 periodos. Las restricciones principales
incluyen el secuenciamiento de la extracción, la construcción del túnel y el condicionamiento
a un ingreso mínimo. La incertidumbre en el precio del cobre es representada a través
de escenarios probabilísticos de precios, en los cuales cada uno tiene igual probabilidad
de ocurrencia, y se resuelve mediante los enfoques: estocástico de maximización del
valor esperado, determinístico estático de precio promedio, determinístico estático del peor
caso, determinístico dinámico de precio promedio, determinístico dinámico del peor caso
y el algoritmo del volumen con una heurística complementaria sencilla. Cada enfoque es
evaluado mediante el valor de su función objetivo, su tiempo de resolución y su capacidad
de entregar soluciones factibles.
Al finalizar, se observa que el enfoque estocástico presenta el mejor desempeño a nivel
de solución, pero con tiempos de resolución bastante superiores que los otros enfoques
y que, por lo tanto, hacen poco atractivo el uso de éste en problemas de gran tamaño,
donde la capacidad computacional se transforma en la principal limitante. Por este motivo y
dado que los métodos determinísticos dinámicos presentan soluciones muy superiores a los
casos estáticos y con valores muy cercanas al óptimo estocástico, se recomienda el uso de
estos últimos para este tipo de problemas. Además se sugiere que las empresas analicen
soluciones que acepten un cierto nivel de infactibilidad, pues se observó que la solución
óptima se condicionaba fuertemente por la secuencia de extracción y, por consiguiente, al
peor caso. En este sentido, un cambio marginal en dicho caso podría llevar a mejoras que
pueden resultar significativas para una empresa.
|
Page generated in 0.0603 seconds