PROGRAMACIÓN DINÁMICA Y DUALIDAD, APLICADA AL USO ÓPTIMO DE RECURSOS EN UN SISTEMA DE GENERACIÓN SIMILAR AL DE PANAMÁ

DYNAMIC AND DUALITY PROGRAMMING, APPLIED TO THE OPTIMAL USE OF RESOURCES IN A GENERATION SYSTEM SIMILAR TO PANAMA

Percy Ariel Garrido Zúñiga1, Manuela Foster Vega2

1Universidad de Panamá. ENEL. percygarrido@yahoo.com. 2Universidad de Panamá. Facultad de Ciencias Naturales, Exactas y Tecnología. manuelafoster@hotmail.com

RESUMEN

Al igual que en la región centroamericana, el sistema de generación panameño cuenta con un importante componente de energía renovable dentro de los cuales existe una significativa capacidad de almacenamiento mediante embalses, que permite planificar estrategias para mitigar costos entre estaciones. En la planificación del uso de los recursos de generación de estos sistemas, se toman decisiones que afectan la situación en el futuro. Una manera de organizar esta política de decisiones es mediante la asignación de precios a lo largo del tiempo para los recursos que pueden ser administrados. El planteamiento dual de este problema ofreció la posibilidad de abordar el problema desde el punto de vista de los precios sombra. Fue necesario descomponer el problema en sub-problemas que se entrelazan sucesivamente. Esta estrategia de resolver un problema de optimización complejo mediante la descomposición del problema en sub- problemas secuenciales corresponde a la Programación Dinámica. Se abordó el problema de optimización del uso de recursos de generación eléctrica aplicable al sistema panameño, con el uso de la Programación Dinámica y de la Dualidad de Programación Lineal.

PALABRAS CLAVE: Generación termoeléctrica, generación hidroeléctrica, recurso renovable, capacidad de almacenamiento, funciones de costos futuros e inmediatos, despacho económico.

ABSTRACT

Panama’s generation system has an important renewable energy component, similar to what happens in other Central American countries. There is a significant renewable energy storage capacity in reservoirs that allow planning strategies to mitigate costs between seasons. The decisions taken today affect situations in the future in this kind of problem. Scheduling of the hydro reservoirs use is necessary because it can save costs in the future. One way to implement this scheduling is by pricing the hydro resource over time. The dual approach to this problem offers the possibility of addressing it from the shadow prices point of view. To solve these problems, they must be broken down into sub-problems that are interrelated. The strategy of solving complex optimization problems by broken in sequential subproblems is dynamic programming. This paper focuses on the problem of optimizing the use of resources applicable to the Panamanian system, which apply Dynamic Programming and Dual approach of Linear Programming.

KEYWORDS: Thermal generation, hydro generation, renewable resources, storage capacity, future and immediate cost functions, economic dispatch.

INTRODUCCIÓN

Entre los problemas de uso de recursos de generación de electricidad, los renovables son los más apreciados debido a sus costos variables nulos o casi nulos, pero finitos.

Usar todo el recurso renovable no necesariamente significa optimalidad (Bertzekas, D., 1987). Cuando el recurso tiene capacidad de almacenamiento, el uso óptimo se define en función de la minimización de costos de suministros de requerimiento energético en un periodo de tiempo, que para propósitos de encontrar solución, debe estar acotado.

En el caso de generación termoeléctrica, los ahorros que pudieran lograrse dependen del escenario de precios de combustible que suceda. Por el lado de la generación hidroeléctrica, los ahorros que podría producir la planificación del uso de este recurso son más fiables, pues solo dependen de la propia disponibilidad del recurso. (King I. P., 2002)

Se busca explicar la forma como se aplica la Programación Dinámica (Bellman, R., 1954) y la Dualidad en Programación Lineal (Bazaraa y Jarvis, 1984) para resolver el problema de optimización del uso de recursos de generación eléctrica en Panamá, país en donde esta tarea se realiza con una herramienta de Programación Dinámica Dual Estocástica (SDDP), (PSR Inc, Marzo 2013)

Almacenamiento de Energía

Aunque la generación termoeléctrica es almacenable, es un hecho que para acceder a ella solo es necesario comprar más combustible; significa que para propósitos de modelación este recurso es infinito.

Al problema se le puede incluir proyecciones de precios de combustible, de manera que la solución minimice el costo de suministro, al menos en ese escenario de combustible asumido. No obstante, como estas proyecciones de precios pueden ser poco confiables, el estudio se concentra en la optimización de recursos renovables que pueden ser almacenables, debido a que se tiene mayor certeza que produce beneficios.

Las hidroeléctricas con embalses son el ejemplo más clásico de energía almacenable, además, cada vez más aparecen nuevas opciones como los proyectos fotovoltaicos e incluso eólicos con baterías, y algunos otros esquemas de almacenamiento de energía potencial. Esta capacidad de almacenar energía permite administrarla, lo cual puede utilizarse para reducir costos futuros.

Programación Dinámica

La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema. El procedimiento general de resolución de estas situaciones se basa en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir, comenzando por la última y pasando en cada iteración en orden inverso, es decir, comenzando por la última y pasando en cada iteración a la etapa anterior, como se observa en la figura 1.

Figura 1. Esquema de funcionamiento de la Programación Dinámica

La programación dinámica no cuenta con una formulación matemática estándar para resolver los problemas, se trata de un enfoque general para la resolución de problemas, en consecuencia, se deben desarrollar ecuaciones y algoritmos específicos para cada problema particular.

En un proceso de decisión de “n” etapas, la condición inicial del proceso en una etapa se denomina “estado” en esa etapa. La forma de completar una etapa, es una decisión y la secuencia de decisiones a lo largo de las etapas, se denomina política. En la resolución de un problema se busca la “política óptima” que resuelva el problema. (Toledo, 18 de diciembre de 2012)

Formulación del problema

Teniendo en cuenta que el recurso de generación renovable con capacidad de almacenamiento es limitado, se puede entender que existe relación entre el uso del recurso hoy y la reserva del mismo a futuro: a mayor volumen “turbinado” (para el caso de recurso hidráulico) hoy, menor volumen para turbinar quedará a futuro. En términos de costo se puede decir que el costo de la operación actual (costo Figura 1 Esquema de inmediato de operación) se reduce conforme el volumen turbinado aumenta hoy. Dicho de otro modo, el costo de la operación futura aumenta conforme el volumen turbinado futuro disminuye, lo cual puede graficarse como se observa en la figura 2.

Figura 1. Relación entre el Costo Inmediato y el Costo Futuro

Objetivo del problema

Cada una de las etapas que componen el horizonte de análisis tiene su respectivo costo de operación, pero es claro que la decisión óptima de uso del recurso debe ser la que hace mínima la suma del costo de operación de todas las etapas:

(1) Mínimo [Función de Costo Inmediato + Función de Costo Futuro] = Min [FCI + FCF]

Consideraciones de costos

Los únicos costos que pueden reducirse, dependiendo del esquema de despacho que se adopte, son los costos variables de la operación.

Los costos variables de la generación renovable son nulos o casi nulos, en cambio, los costos variables de la generación termoeléctrica no son despreciables, esto quiere decir que tanto los Costos Operativos Inmediatos como los Costos Operativos Futuros se calculan en función a los costos termoeléctricos que el esquema respectivo de despacho implica.

Como el problema de la primera etapa requiere considerar las consecuencias de la decisión sobre las etapas futuras, se necesita analizar primeramente cómo se comportan los Costos Futuros. En este análisis de Costos Futuros se busca definir una función que los describa, para que estos costos sean considerados como parte de los costos totales de la etapa actual.

Formulación del problema de minimización de costos de la última etapa

Para poder plantear los costos futuros es necesario acotar el horizonte del problema, lo cual significa que FCFn=0 debido a que no hay ningún costo posterior, pues no hay más etapas. Siendo que el objetivo del problema es minimizar los costos operativos, se puede decir que el resultado del problema debe considerar el uso de la totalidad del recurso almacenable (cuyos costos variables son prácticamente nulos). Esto, desde el punto de vista de la última etapa, quiere decir que el estado final del almacenamiento de recurso debe ser vacío (Estado final = 0).

Conociendo el estado final de la etapa “n”, pero teniendo aún como incógnita el estado inicial de esta etapa, se puede expresar una Función de Costo Inmediato de esta etapa (FCIn), la cual quedará dependiente del estado inicial de esta etapa “n” (Estadoninicial).

La FCIn puede expresarse (ecuación 2), como una función de costos termoeléctricos (P.Térmicon) en que se tendría que incurrir para suplir la demanda remanente, que sería dependiente del uso que se dé en esa etapa al recurso almacenable

(2)

Donde,

P.Térmicon es un término generalizado que considera el precio del recurso termoeléctrico en la etapa “n”

Estado n inicial es el estado del recurso almacenable renovable al inicio de la etapa “n”

Estado n final es el estado del recurso almacenable renovable al final de la etapa “n”, que es cero por ser la última etapa, por lo cual:

Como FCFn = 0, entonces FCTn = FCIn, por lo que, en lo que corresponde a la función objetivo del subproblema de la etapa “n”, quedaría planteada como sigue:

Entonces, el problema puede plantearse como:

En un problema real de despacho, es posible que todos los generadores juntos no sean capaces de cubrir la demanda, esto sucede cuando el sistema está en racionamiento o déficit. Para propósito de planteamiento del problema, la demanda que podría racionarse se plantea mediante una variable de holgura cuyo costo variable es el costo en que incurre el sistema ante un racionamiento que nunca puede ser mayor que la demanda, es decir, el planteamiento objetivo sería:

Aplicación de Programación Dinámica

El objetivo de la penúltima etapa n-1, sería la minimización de los costos termoeléctricos de suplir la demanda de esa penúltima etapa, (FCIn-1), más la Función de Costo Futuro de esa penúltima etapa (FCFn-

1):

(7) Min [FCIn-1 + FCFn-1]

Similar a como se planteó la FCIn en la ecuación 1, la FCIn-1 quedaría expresada así:

(8)

La FCFn-1 es la función de costo total de la etapa “n” (FCTn = FCIn), pero expresada en términos de energía almacenable disponible para la etapa n-1, se expresa:

Donde:

Recurso.Max.Almacenable es el total del recurso renovable almacenable

FCFn-1, que es una función del estado inicial de la etapa “n” (Estadon inicial), podría ser expresada en términos de estado final de la etapa “n-1” pues Estadon inicial = Estadon-1 final. Al expresar la FCF en términos del uso de recurso en la etapa en cuestión, se independiza el sub-problema de las etapas adyacentes.

Si se continúa con el análisis discretizado “hacía atrás”, se puede decir que el resultado del problema de la penúltima etapa sería una nueva función de costos que a su vez sería la FCF de la etapa antepenúltima. Continuando con este procedimiento de análisis, se logra descomponer el problema original de optimización del uso del recurso en una serie finita de sub-problemas secuenciados.

Sucede que en la etapa 1 las condiciones iniciales son conocidas, por tanto es posible hallar el nivel final óptimo del almacenamiento en la etapa 1.

Al encontrar la decisión óptima de uso de recurso de la primera etapa, se conoce la disponibilidad de recurso para la segunda etapa, o lo que es lo mismo, se conoce el estado inicial de la segunda etapa. Se observa que la política óptima para las siguientes etapas no depende de las decisiones tomadas en las etapas anteriores, pues solo depende del estado en el que se está, no de cómo se llegó hasta él. Este es el Principio de Optimalidad de la Programación Dinámica o de Bellman, que se traduce como que toda la información sobre el pasado se resume en el estado o nivel inicial del embalse, es este caso, en que se encuentra. (Toledo, 18 de diciembre de 2012).

Resolviendo secuencialmente cada una de las etapas sucesivas se obtiene un conjunto de decisiones que representarán la política óptima de uso del recurso.

APLICACIÓN

Datos del problema

Como aplicación de la programación dinámica y de la dualidad en programación lineal en el uso óptimo de recursos, se utilizará un problema del sistema panameño que consta de 4 generadores termoeléctricos más un generador hidroeléctrico con embalse, como recurso renovable con almacenamiento. Los datos se muestran en la figura 3:

• Problema de 2 etapas: Recurso hidroeléctrico total: 242 MW

  

  
  

  
  

• 4 generadores termoeléctricos (BLM-Carbón ubicado en Bahía la Minas de Colón, PanAm ubicada en Chorrera, Pacora ubicada en Chepo de la provincia de Panamá y Cativá ubicada en Bahía las Minas de Colón):

  
  

  

  
  

  
  

  
  

  Figura 3. Información de un sistema de generación panameño

  
  

  Función de Costos Futuros

  Como el problema de la primera etapa requiere considerar las consecuencias de las decisiones sobre la etapa futura, se necesita analizar primeramente cómo se comportan los Costos Futuros, de manera que se obtenga una función que describa los costos futuros de la operación.

  Para obtener una función de los costos futuros de la etapa 1, o lo que es lo mismo, la función de costos futuros de la penúltima etapa (ecuación 3), se necesita calcular los costos totales de operación para distintos niveles de uso del recurso hidráulico.

  Para este ejemplo se asumen niveles de uso del recurso hidráulico de 55 MW, 110 MW, 165 MW y 220 MW. Se excluye el valor de 0 MW debido a que es una solución inviable siendo que:

  1. el recurso total es de 242 MW,

  2. la capacidad máxima de generación es de 220 MW y

  3. se sabe que el recurso almacenable debe consumirse plenamente en las 2 etapas (220 MW < 242 MW).

  La formulación toma la forma:

  
  

  
  

  Soluciones:

  
  

• Solución Óptima para Bayano = 55 MW: Z = $ 25,292.80 o BLM = 107.63, PanAm

  = 83.08, Pacora = 50.49, Cativa = 53.8, Racionamiento = 0

• Solución Óptima para Bayano = 110 MW: Z = $ 19,575.40 o BLM = 107.63, PanAm

  = 83.08, Pacora = 49.29, Cativa = 0, Racionamiento = 0

• Solución Óptima para Bayano = 165 MW: Z = $ 14,363.70 o BLM = 107.63, PanAm

  = 77.37, Pacora = 0, Cativa = 0, Racionamiento = 0

• Solución Óptima para Bayano = 220 MW: Z = $ 9,299.88 o BLM = 107.63, PanAm = 22.37, ¨Pacora = 0, Cativa = 0, Racionamiento = 0

Nota: Para el cálculo de la FCF de las etapas previas a la última, se considera que a la ecuación 4 se le suma la FCF de la etapa siguiente. Esto, en el caso de la penúltima etapa, significa que se le suma la FCF que se calculó.

Para cada nivel de uso del recurso en la segunda etapa, existe un correspondiente costo de operación, que es el costo futuro desde el punto de vista de la primera etapa, lo que representa la función de costo total de la segunda etapa. También, cada nivel de uso futuro del recurso implica una cantidad de recurso remanente para la primera etapa (figura 4).

Figura 4. Cantidad de recurso remanente de la primera etapa

Para agregar los costos futuros en la función de costo total de la primera etapa, es necesario expresar la función de costo total de la segunda etapa en términos de la cantidad de recurso remanente para la primera etapa, tal como se aprecia en la figura 5.

Figura 5. Función de Costo Total

Se aproxima una FCF1 por regresión lineal, la cual podría introducirse a la función objetivo de minimización de costos totales de la primera etapa.

Planteamiento del problema de la primera etapa (hora 1)

La solución del problema de la primera etapa debe considerar el costo futuro (FCF):

La solución muestra el despacho óptimo del sistema para la etapa 1, donde se observa que al embalse de Bayano debe dársele un uso de 75.63 MW y el resto de la demanda es cubierto por la disponibilidad termoeléctrica, que se usará de menor a mayor costo variable.

Al conocer el estado final de la primera etapa se conoce el estado inicial de la siguiente etapa. Con esta información y la correspondiente FCF se pueden ir resolviendo secuencialmente todas las etapas.

Cálculo del precio sombra del recurso renovable almacenable con el planteamiento del problema dual de la hora 1

Problema Primal

La solución del Dual produce el valor de del recurso almacenable (Precio.Bayano). Como se ve en la figura 6, este precio sombra del recurso renovable es útil para producir el mismo resultado de despacho mediante un orden de mérito dado por el precio. Se observa además que el precio sombra para cada recurso térmico es igual a su costo variable, por lo que no tiene una utilidad especial en este caso.

Figura 6. Solución del Problema Dual

Consideración de variabilidad de las variables referente a recursos renovables

Los recursos renovables, tanto los que pueden ser almacenados cómo los que no, son variables estocásticas por lo que el planteamiento debe hacerse mediante Programación Dinámica Estocástica.

Para esto se analizan un conjunto de series estocásticas equi-probables. A cada una de las series se aplica el mismo procedimiento de análisis descrito arriba, pero los costos operativos que se consideran para las FCF (Ilustraciones 3 y 4) son el promedio de lo que sucede en cada serie separadamente (PSR Inc., Marzo 2013). De esta manera, la política óptima queda afectada por los costos que implica cada serie estocástica, alejándose naturalmente de las decisiones más arriesgadas.

CONCLUSIÓN

En este documento se ilustró una manera de resolver el problema de despacho económico, o de administración de uso de recurso, con la aplicación de la Programación Dinámica apoyada en una estrategia de descomposición del problema en sub-problemas de Programación Lineal.

Por otro lado, el problema Dual de este caso permitió calcular el precio sombra del recurso hidroeléctrico. Lo importante de este precio sombra es que con él se puede manejar la optimización de todo el sistema mediante una simple tabla de méritos dada por los costos variables del recurso termoeléctrico, conjugados con el precio sombra calculado para el recurso hidroeléctrico. Esta simplicidad de aplicación permite la flexibilidad de que el sistema pueda ser manejado manualmente por un operador valiéndose únicamente de una lista de precios.

La herramienta que se utiliza en Panamá, y que aplica todo el desarrollo matemático aquí explicado, es capaz de darle soporte a las decisiones de despacho de los recursos de generación del país. Además, con esta herramienta es posible hacer estudios de sensibilidad ante variación de diversas variables como precios de combustible o disponibilidad de recursos.

REFERENCIAS BIBLIOGRÁFICAS

Balas, E. and Simonetti, N. (2001) Linear time dynamic programming algorithms for new classes of restricted TSP’s: A computational study. INFORMS Journal on Computing 13 (1), 56–75.

Bazaraa, M. & Jarvis, J. (1984), s.f. Programación Lineal y Flujo en Redes. México: Editorial Limusa..

Bellman, R. (1954), "The theory of dynamic programming", Bulletin of the American Mathematical Society 60: 503–516, doi:10.1090/S0002-9904-1954-09848-8, MR0067459.

Bertsekas, D., 1987. Dynamic Programming: Deterministic and Stochastics Models. Prentice - Hall, Inc.. Chapra, S. & Canale, R., 1985. Métodos Numéricos para Ingenieros. México: McGraw-Hill.

Eddy, S. R., What is dynamic programming? Nature Biotechnology, 22, 909-910 (2004).

Giegerich, R.; Meyer, C.; Steffen, P. (2004), "A Discipline of Dynamic Programming over Sequence Data" (http://bibiserv.techfak.uni-bielefeld.de/adp/ps/GIE-MEY-STE-2004.pdf), Science of Computer Programming 51 (3): 215–263, doi:10.1016/j.scico.2003.12.005.

King, I. P. (2002). A Simple Introduction to Dynamic Programming in Macroeconomic Models.http://www.business.auckland.ac.nz/Departments/econ/workingpapers/full/Text230.pdf.

Lew, A. (2002) A Petri net model for discrete dynamic programming. International Workshop on Uncertain Systems and Soft Computing, Beijing.

Lew, A. and Mauch, H. (2006) Dynamic Programming: A computational tool. Springer, Berlin.

Mauch, H. (2006) DP2PN2Solver: A flexible dynamic programming solver software tool. Control and Cybernetics 35 (3), 687-702.

Piunovskiy, A.B. (2006) Dynamic programming in constrained Markov decision processes. Control and Cybernetics 35 (3), 645-660.

Popova-Zeugmann, L. (2006) Time Petri nets state space reduction using dynamic programming. Control and Cybernetics 35 (3), 721-748.

PSR Inc., Marzo 2013. Manual de Metodología del SDDP (Programación Dinamica Dual Estocástica), Versión 12. Rio de Janeiro, Brasil: s.n.

Sniedovich, M and Voss, S. (2006) The corridor method: a dynamic programming inspired metaheuristic.

Control and Cybernetics 35 (3), 551-578.

Sniedovich, M. (2010), Dynamic Programming: Foundations and Principles, Taylor & Francis, ISBN 9780824740993

Tereso, A.P., Mota, J.R.M. and Lameiro, R.J.T. (2006) Adaptive resource allocation to stochastic multimodal projects: a distributed platform implementation in Java. Control and Cybernetics 35 (3), 661-686.

Toledo, W., 18 de diciembre de 2012. Programación Dinámica, Santiago del Estero, Argentina: UNIVERSIDAD NACIONAL DE SANTIAGO DEL ESTERO.

Waner, S., s.f. Matemáticas Aplicadas y Cálculo Aplicado, Un Recurso de Matemáticas Finitas y Cálculo Aplicado Para Alumnos. [En línea]

Werner, M. (2006) A timed Petri net framework to find optimal IRIS schedules. Control and Cybernetics 35 (3), 703-719.