Spelling suggestions: "subject:"[een] PROGRESSIVE HEDGING"" "subject:"[enn] PROGRESSIVE HEDGING""
1 |
Considerando el cambio climático en un modelo de producción forestalZapata Tapia, Camila Beatriz January 2015 (has links)
Ingeniera Civil Industrial / El cambio climático puede impactar sustancialmente en el sector forestal, existen diversos estudios que demuestran que los inviernos serán más cálidos y las temporadas secas aumentarán. El objetivo de este proyecto es elaborar un método que permita incluir el factor del calentamiento global en las decisiones de producción forestal. Esto a partir de un trabajo anterior, el cual concluye que agregar incertidumbre en estos modelos aumenta el beneficio esperado a través de la inclusión de 32 escenarios climáticos, agrupados en un árbol de escenarios. El aporte de este trabajo será especificar hasta qué punto es provechoso seguir aumentando los escenarios considerados.
La complejidad del problema viene dada por la cantidad de datos a utilizar, ya que al aumentar el tamaño del árbol de escenarios, los tiempos de resolución incrementan considerablemente, esto ya que los escenarios comparten etapas, que deben tener valores comunes para las variables de decisión. Así, se obtiene un plan contingente, condicional a lo que ocurra en cada etapa, teniendo siempre la mejor respuesta.
La metodología considera generar los escenarios de clima basado en predicciones ya hechas en distintas estaciones meteorológicas de Portugal, país donde está ubicada la zona de estudio. Luego, se busca construir un modelo de programación lineal, donde la decisión corresponde a qué áreas de un bosque talar en cada periodo. Se busca maximizar los beneficios obtenidos según los precios que corresponden a cada escenario. Para llegar a una solución con una gran cantidad de escenarios, será necesario utilizar un algoritmo que permita simplificar la resolución, en este caso Progressive Hedging, cuyo principio es resolver a través de la descomposición por escenarios. Se estudian mejoras al algoritmo, además de opciones de reducción y agrupación de escenarios, para mejorar la eficiencia del mismo.
Los resultados obtenidos indican que la utilización de Progressive Hedging ofrece una eficiencia superior para instancias de gran tamaño. Esto a partir de las instancias mayores a los 300 escenarios, y además se concluye que el número óptimo de escenarios a considerar rodea los 650, en dicho punto el costo adicional para general la solución no se ve justificado, ya que la calidad de la misma no aumenta significativamente. Por otra parte, la técnica de clustering para la reducción de escenarios resultó efectiva para mejorar aún más los tiempos de resolución, considerando su correspondiente pérdida en la calidad de la solución.
|
2 |
Complete stochastic forestry planning problem using progressive hedging algorithmPais Martínez, Cristóbal January 2014 (has links)
Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / El trabajo desarrollado en esta tesis se enmarca dentro del área de investigación de operaciones, en el campo de la optimización estocástica para un problema de planificación forestal, el cual se modela como un problema lineal de carácter mixto.
El problema de planificación forestal abordado en esta tesis consiste en la maximización del valor presente del plan de explotación táctico de un conjunto de 17 bosques sujeto a incertidumbres internas (rendimiento de los diversos predios) y externas (precio de los productos y cantidad demandada de estos), incertidumbres que se representan a través de árboles de escenarios. Dentro de las principales decisiones a realizar se encuentra la construcción y/o mejora de caminos de la red interna junto a la cantidad de cada predio que será cosechada, almacenada y vendida durante cada periodo.
Llevar a cabo la resolución de este tipo de problemas estocásticos bajo las técnicas de optimización tradicionales se vuelve inabordable en la medida que el tamaño de la instancia aumenta, lo que justifica la utilización de un algoritmo adecuado para alcanzar resultados en tiempos razonables. La metodología de resolución utilizada se basa en el algoritmo de descomposición por escenarios Progressive Hedging (PH) sobre el cuál se realizan una serie de ajustes según las características del problema con tal de obtener mejores rendimientos. Junto a esto, se realizan una serie de comparaciones de diversas implementaciones del mismo algoritmo con respecto a técnicas de optimización tradicionales, determinando y analizando las ventajas que ofrece PH para el problema en estudio.
Se implementa una metodología de generación de árboles de escenarios basada en un modelo matemático robusto, utilizando como punto de partida un proceso estocástico para representar el movimiento de las variables aleatorias, lo que permite obtener soluciones rigurosas y de calidad.
Se lleva a cabo un estudio detallado respecto a técnicas de reducción de escenarios, así como del desarrollo de una metodología de simulación que permite comparar de forma cuantitativa el rendimiento de modelos estocásticos y determinísticos, permitiendo estimar el número suficiente de escenarios que logran representar de buena manera la realidad, manteniéndose óptimo el trade-off entre calidad de solución y tiempos de cómputo involucrados.
Los resultados concluyen que la utilización del algoritmo PH bajo las configuraciones y ajustes realizados ofrece rendimientos superiores a las técnicas de optimización clásicas y tradicionales para problemas estocásticos de gran escala, con la posibilidad de explotar de gran manera su implementación en paralelo, obteniéndose así rendimientos superiores en la medida que se cuente con mayores recursos computacionales. Se determinan los mejores métodos para llevar a cabo la reducción del número de escenarios de la instancia original, permitiendo así el manejo abordable de instancias que inicialmente se presentan complejas.
Finalmente, la aplicación de la metodología de comparación de rendimiento entre modelos determinísticos y estocásticos fue satisfactoria, determinándose un rango para el número suficiente de escenarios a utilizar dentro del modelo en estudio de tal forma de alcanzar un punto óptimo entre calidad de la solución y el rendimiento computacional del modelo.
|
3 |
Métodos de optimización bajo incertidumbre aplicados al problema de coordinación hidro-térmica chilenoPérez Pérez, Carlos Francisco January 2017 (has links)
Magíster en Gestión de Operaciones.
Ingeniero Civil Industrial / El presente trabajo, trata sobre metodologías de resolución de problemas estocásticos multi-etapa. El objetivo es comparar el algoritmo Stochastic Dual Dynamic Programming (SDDP), con la metodología Progressive Hedging (PH). La diferencia entre metodologías radica en que SDDP corresponde a un algoritmo de descomposición vertical o por períodos, mientras que PH representa una metodología de descomposición horizontal o por escenarios.
El estudio se desarrolla en el contexto eléctrico chileno, caracterizado por una red eléctrica compuesta por generadores, demandas y líneas de transmisión. Además de una red hídrica; en la que se modelan todos los generadores hidroeléctricos, flujos hídricos y capacidades de almacenamiento.
Para realizar las pruebas, se utilizan instancias de distintos tamaños y horizontes de planificación, bajo el supuesto uninodal (todas las centrales eléctricas y demandas, conectadas a un mismo nodo) y multinodal.
Las metodologías fueron testeadas mediante un árbol en común. Los resultados muestran que en general, SDDP presenta tiempos de ejecución mucho menores, atribuibles principalmente al lenguaje de ejecución (Fortran vs Python). En cuanto a la exactitud de la solución, PH muestra un mejor desempeño, con diferencias poco significantes.
Un segundo estudio, es la confrontación de generadores de árboles de escenarios. Se compara la metodología actual (nombrada PLP), con dos generadores desarrollados íntegramente en esta investigación. Estas metodologías se basan en probabilidades condicionales por período, y llevan el nombre de Synth y NSG, que corresponden a generación de escenarios sintéticos e históricos, respectivamente. Una de las ventajas de estas metodologías es que consideran tanto la correlación espacial, como la correlación temporal.
Bajo escenarios extremos, Synth muestra los menores costos operativos en un 60% de las pruebas realizadas, obteniendo costos comparativos hasta un 7% menores.
Por otro lado, bajo escenarios promedios, existe un desempeño muy parecido entre los generadores Synth y PLP, donde PLP muestra mayores ahorros comparativos.
|
4 |
Stochastická optimalizace toků v sítích / Stochastic Optimization of Network FlowsMálek, Martin January 2017 (has links)
Magisterská práce se zabývá stochastickou optimalizací síťových úloh. Teoretická část pokrývá tři témata - teorii grafů, optimalizaci a progressive hedging algoritmus. V rámci optimalizace je hlavní část věnována stochastickému programování a dvoustupňovému programování. Progressing hedging algoritmus zahrnuje také metodu přiřazování scénářů a modifikaci obecného algoritmu na dvou stupňové úlohy. Praktická část je věnována modelům na reálných datech z oblasti svozu odpadu v rámci České republiky. Data poskytl Ústav procesního inženýrství.
|
5 |
Algoritmy stochastického programování / Stochastic Programming AlgorithmsKlimeš, Lubomír January 2010 (has links)
Stochastické programování a optimalizace jsou mocnými nástroji pro řešení široké škály inženýrských problémů zahrnujících neurčitost. Algoritmus progressive hedging je efektivní dekompoziční metoda určená pro řešení scénářových stochastických úloh. Z důvodu vertikální dekompozice je možno tento algoritmus implementovat paralelně, čímž lze významně ušetřit výpočetní čas a ostatní prostředky. Teoretická část této diplomové práce se zabývá matematickým a zejména pak stochastickým programováním a detailně popisuje algoritmus progressive hedging. V praktické části je navržena a diskutována původní paralelní implementace algoritmu progressive hedging, která je pak otestována na jednoduchých úlohách. Dále je uvedená paralelní implementace použita pro řešení inženýrského problému plynulého odlévání ocelové bramy a na závěr jsou získané výsledky zhodnoceny.
|
6 |
Resolución de un problema estocástico de planificación minera de largo plazo para el proyecto Quetena de CODELCOVilla Muñoz, Carlos Alberto January 2012 (has links)
Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Quetena corresponde a un proyecto ubicado en las proximidades de la ciudad de Calama, región de Antofagasta, perteneciente al clúster Toki, comprendido por los recursos mineros de los cuerpos principales de Quetena, Genoveva, Toki y Opache.
Se caracteriza por la baja ley de sus recursos, lo que implica que la variabilidad del proyecto tenga una alta sensibilidad frente al precio del cobre. Es por esto que resulta particularmente interesante evaluar económicamente su explotación incorporando la variabilidad del precio del metal.
Se utilizó un modelo estocástico de optimización, que se combina con un árbol de escenarios de precios para obtener planes mineros robustos y flexibles. Este modelo estocástico resulta intratable computacionalmente por su gran tamaño y complejidad, por lo que se utiliza el método Progressive Hedging (PH) creado por Roger J-B Wets y R.T. Rockafellar, el que se basa en una resolución de descomposición por escenarios. PH se utilizó para encontrar soluciones que permitieran realizar fijación de variables, para reducir el espacio factible del modelo estocástico.
La hipótesis de este trabajo es que el problema de planificación minera de largo plazo con incertidumbre en el precio del cobre, modelado estocásticamente y resuelto mediante un método de separación de escenarios, entrega planes flexibles que son contingentes al precio del mineral y que permiten mejorar los indicadores económicos del negocio.
El principal resultado obtenido, es que el valor de la flexibilidad de los planes mineros aumenta cuando el precio promedio de largo plazo disminuye.
|
7 |
Planificación Forestal con Posibilidad de Incendio Resuelto a Través del Algorítmo Progressive HedgingSolari Díaz, Luis Fernando January 2012 (has links)
No description available.
|
8 |
Progressive hedging aplicado a coordinación hidrotérmicaIroume Awe, Andrés Guillermo January 2013 (has links)
El problema de Coordinación Hidrotérmica busca encontrar la operación óptima para un Sistema Eléctrico Mixto, combinando en la solución los efectos de las etapas futuras así como los efectos que la hidrología tiene en la operación del sistema.
Los Sistemas Eléctricos mixtos corresponden a aquellos sistemas en los que operan tanto centrales de generación hidráulicas, geotérmicos, térmicas y eólicas entre otras. Un ejemplo de estos sistemas es el Sistema Interconectado Central (SIC) chileno, que en particular tiene una alta presencia de centrales hidráulicas y térmicas, en el cual en un año promedio un cuarenta por ciento de la energía viene de fuentes hidráulicas y un sesenta de fuentes térmicas.
Desde el punto de vista de los costos de operación, estas dos fuentes de generación presentan importantes diferencias. Mientras los costos variables de una central hidráulica son bajos, los de una central térmica son más altos debido al combustible que requiere para la generación de energía. Por otro lado las centrales hidráulicas tienen costos de inversión más elevados que las centrales térmicas.
Otra diferencia entre estas tecnologías es que las centrales hidráulicas son capaces de generar energía de acuerdo a la cantidad de agua que reciben de sus afluentes o que son capaces de almacenar (en embalses o estanques de regulación). Esta característica las hace dependientes del clima, en particular de la hidrología de una determinada zona geográfica. Debido a que no es posible predecir la hidrología, ésta se modela como una variable aleatoria.
El problema de Coordinación Hidrotérmica busca la manera óptima de operar un sistema mixto en el mediano y largo plazo. Tiene una naturaleza estocástica, debido a la incertidumbre presente al modelar la operación de las centrales hidráulicas. Corresponde a un problema de gran escala que incorpora muchos elementos; centrales de generación, redes de distribución, centros de consumo y restricciones técnicas y ambientales.
En el presente trabajo se desarrollan y aplican metodologías de programación estocástica para la resolución de un problema de Coordinación Hidrotérmica, en particular para un sistema de generación mixto. Se estudian técnicas de descomposición para problemas estocásticos que permitan trabajar con problemas de gran escala y se trabajan métodos de generación y selección de escenarios hidrológicos con el objetivo de representar de manera adecuada las componentes estocásticas del problema.
La metodología utilizada para la resolución de este problema se basa en el algoritmo Progressive Hedging (PH). En este trabajo se busca resolver un problema de planificación eléctrica a través de PH. Sobre este algoritmo se desarrollan una serie de ajustes de acuerdo a las características especiales del problema. También se realizan comparaciones con las técnicas que se utilizan actualmente para resolver este problema y se analizan las ventajas que ofrece PH para este problema en particular.
El problema de Coordinación Hidrotérmica corresponde a un problema cuadrático debido a que cuenta tanto con función objetivo cuadrática como con algunas restricciones cuadráticas. La función de costos de las centrales térmicas es modelada de manera cuadrática, así como también las pérdidas de energía en las líneas de transmisión son cuadráticas. PH es un algoritmo de descomposición por escenarios que entrega soluciones exactas para programas convexos. Funciona resolviendo sucesivas veces cada escenario por separado, penalizado por desviarse de la solución promedio. Debido a su estructura, es de naturaleza fácilmente paralelizable.
Dentro de los resultados se logra solucionar el problema para una serie de instancias, incluyendo instancias de tamaño real del Sistema Interconectado Central chileno. Además se realizan comparaciones entre PH y SDDP, otro de los métodos de solución del problema, mostrando las ventajas y desventajas que PH ofrece.
Finalmente se concluye que PH ofrece buenas posibilidades como metodología de solución para el Problema de Coordinación Hidrotérmica. Si bien actualmente no es competitivo, en el futuro, se pueden desarrollar implementaciones basadas en computación paralela que puedan ser competitivas con las técnicas actuales de resolución.
|
9 |
Evaluación de la resolución en paralelo de un problema estocástico de planificación minera de largo plazoAlarcón Díaz, Jorge Eduardo January 2012 (has links)
Ingeniero Civil Industrial / La minería, que alcanza hoy en día casi un 20% de participación en el PIB nacional, corresponde a la principal actividad económica que ha tenido Chile desde la revolución industrial. Dentro de este contexto destaca la empresa estatal CODELCO como la mayor productora de cobre a nivel mundial.
Considerando el impacto que tiene la industria minera, los altísimos niveles de inversión involucrados, la larga vida útil de una mina y su complejidad, el apoyo a las decisiones mediante modelos de optimización matemáticos aparecen como altamente necesarios. Hoy en día estos modelos son capaces de planificar tanto la extracción como el procesamiento del mineral considerando sólo variables determinísticas.
Una variable muy importante dentro de estos modelos corresponde al precio del cobre. Es por ello que actualmente se trabaja en la implementación de modelos de planificación de largo plazo que incorporen la estocasticidad de esta variable con el fin de evaluar proyectos mineros y así dar apoyo a las decisiones de inversión.
Sin embargo, y debido a la complejidad y tamaño de los procesos, el problema estocástico es demasiado grande desde el punto de vista computacional. Para resolver esto se utiliza Progressive Hedging (PH), un algoritmo que reduce el problema estocástico en muchos sub-problemas determinísticos de menor tamaño. A pesar de esto, el tiempo necesario para su resolución puede llegar a ser del orden de días o incluso semanas.
Una de las cualidades que entrega el algoritmo PH es la independencia en la resolución de los sub-problemas, lo cual puede ser aprovechado para su procesamiento en paralelo de modo de reducir los tiempos de procesamiento. En este trabajo se estudia la complejidad y factores críticos en la implementación de la paralelización, además de la ganancia esperada en súper-computadores tipo clúster.
El anáĺisis algorítmico del problema da luces de que la paralelización es capaz de entregar ahorros en tiempo del orden de un 90%. Por otra parte una simulación en la escalabilidad de una pequeña implementación realizada entrega un ahorro de entre 93% y 98% dependiendo de la arquitectura de memoria del computador, compartida o distribuída, compuesto de 9 procesadores con 8 núcleos cada uno.
Considerando todo lo anterior, y lo que se puede observar con más detalle en este trabajo, la utilización de PH en paralelo es un camino tentador a seguir si lo que se pretende es incluir la estocasticidad de una variable como el precio del cobre en el modelo de planificación minera de largo plazo.
|
10 |
Prostorová dekompozice úloh stochastického programování s omezeními ve tvaru diferenciálních rovnic / Spatial Decomposition for Differential Equation Constrained Stochastic ProgramsŠabartová, Zuzana January 2012 (has links)
Rozsáhlá třída inženýrských optimalizačních úloh vede na modely s omezeními ve tvaru obyčejných nebo parciálních diferenciálních rovnic (ODR nebo PDR). Protože diferenciálních rovnice je možné řešit analyticky jen v nejjednodušších případech, bylo k řešení použito numerických metod založených na diskretizaci oblasti. Zvolili jsme metodu konečných prvků, která umožňuje převod omezení ve tvaru diferenciálních rovnic na omezení ve tvaru soustavy lineárních rovnic. Reálné problémy jsou často velmi rozsáhlé a přesahují dostupnou výpočetní kapacitu. Výpočetní čas lze snížit pomocí progressive hedging algoritmu (PHA), který umožňuje paralelní implementaci. PHA je efektivní scénářová dekompoziční metoda pro řešení scénářových stochastických úloh. Modifikovaný PHA byl využit pro původní přístup prostorové dekompozice. Aproximace diferenciálních rovnic v modelu problému je dosaženo pomocí diskretizace oblasti. Diskretizace je dále využita pro prostorovou dekompozici modelu. Algoritmus prostorové dekompozice se skládá z několika hlavních kroků: vyřešení problému s hrubou diskretizací, rozdělení oblasti problému do překrývajících se částí a iterační řešení pomocí PHA s jemnější diskretizací s využitím hodnot z hrubé diskretizace jako okrajových podmínek. Prostorová dekompozice byla aplikována na základní testovací problém z oboru stavebního inženýrství, který se zabývá návrhem rozměrů průřezu nosníku. Algoritmus byl implementován v softwaru GAMS. Získané výsledky jsou zhodnoceny vzhledem k výpočetní náročnosti a délce překrytí.
|
Page generated in 0.2012 seconds