Programacin dinmica (DP)

Andrs Ramos Universidad Pontificia Comillas

http://www.iit.upcomillas.es/aramos/ Andres.Ramos@upcomillas.es

PROGRAMACIN DINMICA

Programacin dinmica (DP)

1. Definiciones 2. Principio de optimalidad y formalizacin del procedimiento 3. Ejemplo del viajero 4. Ejemplos de sistemas de energa elctrica Planificacin de la expansin de la generacin Asignacin de unidades trmicas

PROGRAMACIN DINMICA

Definiciones
Tcnica matemtica orientada a la solucin de problemas con decisiones secuenciales en etapas sucesivas donde se debe minimizar el coste total de dichas decisiones. En cada etapa se valora no slo el coste actual de tomar una decisin sino los costes futuros que se originan a partir de ella. Etapas: k Decisiones en cada etapa: uk Estados (situaciones en que puede encontrarse el sistema en cada etapa):

xk

El nmero de estados puede ser finito o infinito.

PROGRAMACIN DINMICA

Mediante una decisin uk se va de un estado al comienzo de una etapa xk a otro estado al comienzo de la siguiente xk +1 . Variables estado de etapa k Variables estado de etapa k + 1 Decisiones uk xk +1

xk

En cada etapa se evala la decisin ptima para cada uno de sus estados xk . Cada estado guarda toda la informacin necesaria para tomar las decisiones futuras sin necesidad de conocer cmo se ha alcanzado dicho estado. Es un procedimiento recursivo que resuelve de manera iterativa, incorporando cada vez una etapa, partes cada vez mayores del problema original. El procedimiento puede hacerse hacia delante o hacia atrs.

PROGRAMACIN DINMICA

Principio de optimalidad de la DP o de Bellman

Dado un estado, la poltica ptima para las siguientes etapas no depende de la poltica tomada en las etapas anteriores.

La decisin de ptima inmediata slo depende del estado en el que se est, no de cmo se lleg hasta l. Toda la informacin sobre el pasado se resume en el estado en que se encuentra.

Una vez conocida la solucin ptima global, cualquier solucin parcial que involucre slo una parte de las etapas es tambin una solucin ptima.

Todo subconjunto de una solucin ptima es a su vez una solucin ptima para un problema parcial.

PROGRAMACIN DINMICA

Ejemplo Buscamos el camino ms corto entre Madrid y Barcelona y averiguamos que la solucin ptima del problema pasa por Zaragoza.
Andorra Lrida
Barcelona

Lrida
Zaragoza

Castelln Zaragoza
Madrid

Valencia

Si nos preguntamos por el camino ms corto entre Zaragoza y Barcelona, es obvio que ser el mismo que el utilizado en la solucin del problema global (Madrid - Barcelona). Si existiera un camino ms corto entre Zaragoza y Barcelona (problema parcial), lo habramos tomado como parte de la solucin del problema global.

PROGRAMACIN DINMICA

Relacin recursiva (hacia atrs)

Define la poltica ptima en la etapa k conocida la poltica ptima en cualquier estado de la etapa k + 1
f k* ( xk ) = min cxk uk + f k*+1 ( xk +1 )
uk

estado actual en la etapa k estado al que se llega en la etapa k + 1 dependiente del estado inicial xk y de la decisin uk variable de decisin en la etapa k uk f k ( xk ) valor acumulado de la funcin objetivo para el estado xk desde la etapa k hasta N valor inmediato de tomar la decisin uk desde el estado xk cxk uk Coste acumulado desde una etapa k hasta el final para un estado xk , f k* ( xk ) = Coste inmediato de dicha etapa cxk uk +

xk xk +1

PROGRAMACIN DINMICA

Coste acumulado desde una etapa k + 1 hasta el final para un estado xk +1 , f k*+1 ( xk +1 )

PROGRAMACIN DINMICA

Ejemplo: problema del viajero

El viajero desea ir de la ciudad A a la J por el camino ms corto.

2
A

6
3

4
F

3
J

4
3
D

4
I

3
1
5
G

PROGRAMACIN DINMICA

DP hacia atrs (backward DP)

Empezamos por la etapa k = 4 * Estados x4 Distancia acumulada f 4* Decisin ptima u4 H 3 J I 4 J

Para la etapa k = 3

Estados x3

E F G

Estados x4 H I 4 8 9 7 6 7

* Distancia acumulada f 3* Decisin ptima u3 4 H 7 I 6 H

Para la etapa k = 2

Estados x3
PROGRAMACIN DINMICA 10

Estados x2

B C D

E 11 7 8

F 11 9 8

G Distancia acumulada f 2* 12 11 10 7 11 8

* Decisin ptima u2

E, F E E, F

Finalmente en la etapa k = 1 Estados x2 * Estado x1 B C D Distancia acumulada f1* Decisin ptima u1 A 13 11 11 11 C, D

Ruta ptima: A A A

C D D

E E F

H H I

J J J

4+3+1+3=11 3+4+1+3=11 3+1+3+4=11 A B F I J 2+4+3+4=13

El ptimo no coincide con la decisin miope

PROGRAMACIN DINMICA

11

DP hacia adelante (forward DP)

Para la etapa k = 2

Estados x2

B C D

Estado x1 * Distancia acumulada f 2* Decisin ptima u2 A 2 2 A 4 4 A 3 3 A

Para k = 3

Estados x3

E F G

Estados B C 9 7 6 6 8 8

x2 * D Distancia acumulada f 3* Decisin ptima u3 7 7 C, D 4 4 D 8 8 B, C, D

PROGRAMACIN DINMICA

12

Para k = 4

Estados x4

H I

Estados E F 8 10 11 7

x3 * G Distancia acumulada f 4* Decisin ptima u4 11 8 E 11 7 F

Finalmente para la etapa k = 5 Estados x4 Estados x5 H I J 11 11

* Distancia acumulada f 5* Decisin ptima u5 11 H, I

Ruta ptima: J J J

H H I

E E F

C D D

A A A

3+1+3+4=11 3+1+4+3=11 4+3+1+3=11

PROGRAMACIN DINMICA

13

Ejemplos caractersticos de DP de sistemas de energa elctrica

1. Planificacin de la expansin de la generacin 2. Programacin semanal de grupos trmicos 3. Coordinacin hidrotrmica

PROGRAMACIN DINMICA

14

Planificacin de la expansin de la generacin

Minimizar los costes totales (fijos y variables) de expansin del equipo generador para un alcance de varios aos. Decisiones: Potencia a instalar de cada tipo de generacin en cada ao del alcance del modelo. Restricciones de expansin: Potencia instalada inicial conocida. Mxima (mnima) potencia instalable, inversin mxima (mnima), nmero mximo (mnimo) de generadores instalables en cada ao. Restricciones de operacin: Balance generacin demanda en cada ao. Estados: Nmero total de generadores instalados al comienzo de cada ao.

PROGRAMACIN DINMICA

15

Ejemplo de planificacin de la expansin de la generacin

Ao Demanda (MW) Coste de inversin por generador de 1 GW [/GW ao] 50 55 60 65 45 40

1999 2000 2001 2002 2003 2004

1000 2000 4000 6000 7000 8000

Existe un coste adicional de 15 /ao por ao si se construye al menos un generador No se pueden instalar ms de 3000 MW de generacin en ningn ao Se parte de un sistema elctrico sin ningn generador instalado

PROGRAMACIN DINMICA

16

Etapa
Estado

k = 2004
8000 Cst fut Inst pt

7000

15+40=55

55

1000

8000

Etapa
Estado

k = 2003
7000 8000 Cst fut Inst pt

6000

15+45+55=115 15+90=105

105

2000

7000

55

15+45=60

55

8000

PROGRAMACIN DINMICA

17

Etapa
Estado

k = 2002
6000 7000 8000 Cst fut Inst pt

4000

15+130+105=250 15+195+55=265

250

2000

5000

15+65+105=185

15+130+55=200

15+195=210

185

1000

6000

105

15+65+55=135

15+130=145

105

7000

55

15+65=80

55

8000

Etapa
Estado

k = 2001
4000 5000 6000 7000 8000 Cst fut Inst pt

2000

15+120+250=385 15+180+185=380

380

3000

3000

15+60+250=325

15+120+185=320 15+180+105=300

300

3000

4000

250

15+60+185=260

15+120+105=240 15+180+55=250

240

2000

5000

185

15+60+105=180

15+120+55=190 15+180=195

180

1000

6000

105

15+60+55=130

15+120=135

105

PROGRAMACIN DINMICA

18

Etapa
Estado

k = 2000
2000 3000 4000 5000 6000 Cst fut Inst pt

1000

15+55+380=445 15+110+300=425 15+165+240=420

420

3000

2000

15+55+300=365 15+110+240=365 15+165+180=360

360

3000

3000

15+55+240=305 15+110+180=305 15+165+105=285

285

3000

Etapa
Estado

k= 1999
1000 2000 3000 Cst fut Inst pt

15+50+420=485 15+100+360=475 15+150+285=450

450

3000

Solucin ptima en potencia a instalar en cada ao

1999 2000 2001 2002 2003 2004

3000 3000 0 0 2000 0

Coste total = 15 + 150 + 15 + 165 + 15 + 90 = 450

PROGRAMACIN DINMICA

19

MTODO DE PROGRAMACIN DINMICA

Andrs Ramos Mariano Ventosa

Mayo 1996

PROGRAMACIN DINMICA

20

CONTENIDO
1. Introduccin. 2. Algoritmo de la Programacin Dinmica. 3. Ejemplo: Gestin de un embalse de bombeo puro. 4. Programacin Dinmica Estocstica. 5. Formulacin Matemtica. 6. Modelo de gestin hidrotrmica desarrollado por Red Elctrica de Espaa (MITRE): 6.1. Modelo bsico. 6.2. Proceso de clculo. 6.3. Tratamiento de la aleatoriedad en la demanda y los fallos trmicos. 6.4. Tratamiento de la aleatoriedad en las aportaciones 6.5. Consideracin de mltiples embalses.

PROGRAMACIN DINMICA

21

REFERENCIAS

[1] Bertsekas, 87. "Dynamic Programming. Deterministic and Stochastic Models". Prentice-Hall, Inc. New Jersey, 1987. [2] REE. Modelos Hidrotrmicos. Documento interno de Red Elctrica de Espaa.

PROGRAMACIN DINMICA

22

INTRODUCCIN
Problemas que aborda la Programacin Dinmica:
- Metodologa matemtica orientada a la solucin de problemas en los que se deben tomar decisiones en etapas sucesivas, con el objetivo final de minimizar el coste total de dichas decisiones. - Las consecuencias de las decisiones pueden no ser completamente predecibles. - Un aspecto fundamental de este tipo de problemas es que al tomar una opcin en una de las etapas, no tenemos que valorar slo el coste actual de dicha decisin sino los costes futuros en que incurriremos por causa de ella.

PROGRAMACIN DINMICA

23

 El principio de optimalidad de Bellman.

- La idea clave en la bsqueda de la opcin de menor coste en una toma de decisiones dividida en varias etapas es que conocida la solucin ptima global, cualquier solucin parcial que involucre slo a una parte de las etapas, tambin es una solucin ptima. - Ejemplo: + Buscamos el camino ms corto entre Madrid y Barcelona y averiguamos que la solucin del problema pasa por Zaragoza.
Andorra Lrida
Barcelona

Lrida
Zaragoza

Castelln Zaragoza
Madrid

Valencia

PROGRAMACIN DINMICA

24

+ Si nos preguntamos por el camino ms corto entre Zaragoza y Barcelona, es obvio que ser el mismo que el utilizado en la solucin del problema global (Madrid - Barcelona). + Si existiera un camino ms corto entre Zaragoza y Barcelona (problema parcial), lo habramos tomado como parte de la solucin del problema global. - Esta idea que se conoce como el principio de optimalidad de Bellman es la clave para elaborar el algoritmo de programacin dinmica: Todo subconjunto de una solucin ptima es a su vez una solucin ptima para un problema parcial.

Aplicaciones de la Programacin Dinmica.

PROGRAMACIN DINMICA

25

- La programacin dinmica se adapta bien a problemas de carcter secuencial como por ejemplo: + Bsqueda del camino ms corto entre dos puntos. + Planificacin de tareas. + Gestin de recursos escasos. + Gestin de stocks. + Coordinacin hidrotrmica.

PROGRAMACIN DINMICA

26

ALGORITMO DE LA PROGRAMACIN DINMICA

Descripcin formal del sistema.
- Sistema que evoluciona de forma discreta con el tiempo, con un horizonte finito de N etapas: * k: * xk: * uk: ndice de cada etapa. k = 0 N-1. estado del sistema en la etapa k. decisin tomada en el periodo k y cuya influencia se nota en el periodo k+1. * wk: perturbacin sobre el sistema en el periodo k y cuya influencia se nota en el periodo k+1. Puede no ser perfectamente predecible. - El estado siguiente a cada etapa depende del estado actual del sistema, de las decisiones tomadas en esa etapa y de las perturbaciones exteriores:
PROGRAMACIN DINMICA 27

* xk+1 = fk (xk, uk, wk)

Escenario wk Operaciones uk Estado siguiente xk+1

SISTEMA xk

Resolucin del problema:

- El principio de Bellman sugiere abordar los problemas de programacin dinmica de forma parcial. - Llamaremos P0 al problema global y Pk al problema resultante de considerar slo las etapas a partir de la k hasta el final.

PROGRAMACIN DINMICA

28

- La solucin del problema PN-1 (considerando slo la ltima etapa) se obtiene como sigue: + El coste futuro en que incurrimos por estar en un determinado estado final xN es conocido por ser la etapa final. + Para cada estado xN-1 al principio de la etapa podemos calcular el coste asociado a cada una de las posibles decisiones uN-1. + Nos quedamos para cada posible estado xN-1 con la decisin de coste mnimo. + La solucin del problema PN-1 consiste en una estrategia y un coste asociado para cada estado inicial posible.

- Ahora podemos enfrentarnos al problema PN-2: + Para cada estado xN-2 se calcula el coste asociado a cada una de las posibles decisiones uN-2 que estar compuesto por dos trminos. * El coste de la etapa N-2 debido a la decisin tomada.
PROGRAMACIN DINMICA 29

* El coste en que incurriremos en el futuro debido al estado final del sistema xN-1. Este valor es la solucin del problema PN-1, ya resuelto. + El coste futuro para el estado final del sistema xN-1 obtenido como ptimo del problema PN-1 forma parte de nuestra solucin ptima segn el principio de Bellman. + Nuevamente nos quedamos para cada estado xN-2 con la decisin de coste mnimo, obteniendo as la solucin del problema PN-2. - Se procede de forma recursiva hasta llegar a la solucin del problema P0.

PROGRAMACIN DINMICA

30

- La siguiente figura ilustra este procedimiento.

Etapa 0
x0 x1

Etapa 1
x2

Etapa N-2 Etapa N-1

xN-2
xN-1 xN

PN-2 P0 P1

PN-1

PROGRAMACIN DINMICA

31

Ejemplo: Gestin de un embalse de bombeo puro

Datos del embalse:
- Alcance de la optimizacin 3 semanas (N = 3 etapas). + Etapas k = 0, 1 y 2. - Estados posibles del embalse xk: 0, 1, 2 3. + Lleno (3): tres unidades de volumen. + Semilleno (2): dos unidades de volumen. + Semivaco (1): una unidad de volumen. + Vaco (0): cero unidades de volumen. - Sabemos que x0 = 1. - Las decisiones posibles son acerca del bombeo del embalse en cada semana uk: 0, 1 2.

PROGRAMACIN DINMICA

32

+ Mxima capacidad de bombeo: 2 unidades. - El coste de las decisiones es de una unidad econmica por cada unidad de volumen bombeado. - Existe un coste de almacenamiento, debido a las prdidas por filtraciones y evaporacin, de 0.1 unidades econmicas por cada unidad embalsada y no turbinada al final de la semana. - Los valores de la demanda de agua a turbinar wk: + Semana 1: w0 = 2 unidades. + Semana 2: w1 = 1 unidades. + Semana 3: w2 = 3 unidades. - El coste de la demanda no satisfecha es de 2 unidades econmicas por cada unidad de volumen no disponible.

Solucin de la ltima semana (etapa 2):

PROGRAMACIN DINMICA

33

- La demanda vale w2 = 3. - Debemos obtener la gestin ptima y su coste (bombeo + demanda no satisfecha +almacenamiento) para cada estado posible al principio del periodo.
Estado Inicial x2 Decisin u2 0 1 2 0 1 2 0 1 2 0 1 2 Estado Final x3 0 0 0 0 0 0 0 0 1 0 1 2 Coste

0+2+3+0 = 6 1+2+2+0 = 5 2+2+1+0 = 4 0+2+2+0 = 4 1+2+1+0 = 3 2+2+0+0 = 2 0+2+1+0 = 2 1+2+0+0 = 1 2+2+0+0.1 = 2.1 0+2+0+0 = 0 1+2+0+0.1 = 1.1 2+2+0+0.2 = 2.2

PROGRAMACIN DINMICA

34

 Solucin de la segunda semana (etapa 1):

- La demanda vale w1 = 1. - Debemos obtener la gestin ptima y su coste para cada estado posible al principio del periodo, agregando los costes de la etapa 2.

Estado Inicial x1

Decisin u1 0 1 2 0 1 2 0 1 2 0

Estado Final x2 0 0 1 0 1 2 1 2 3 2

Coste

0+2+1+0+4 = 6 1+2+0+0+4 = 5 2+2+0+0.1+2 = 4.1 0+2+0+0+4 = 4 1+2+0+0.1+2 = 3.1 2+2+0+0.2+1 = 3.2 0+2+0+0.1+2 = 2.1 1+2+0+0.2+1 = 2.2 2+2+0+0.3+0 = 2.3 0+2+0+0.2+1 = 1.2

PROGRAMACIN DINMICA

35

1 2

3 Imposible

1+2+0+0.3+0 = 1.3 -

PROGRAMACIN DINMICA

36

 Solucin de la primera semana (etapa 0):

- La demanda vale w0 = 2. - El estado inicial x0 = 1. - Debemos obtener la gestin ptima y su coste para un slo estado posible al principio del periodo, agregando los costes de la etapa 1.

Estado Inicial x1

Decisin u1 0 1 2

Estado Final x2 0 0 1

Coste

0+2+1+0+4.1 = 6.1 1+2+0+0+4.1 = 5.1 2+2+0+0.1+3.1=5. 2

PROGRAMACIN DINMICA

37

- La solucin de esta etapa nos proporciona el coste mnimo total de 5.1 unidades econmicas, con la siguiente poltica de decisiones: + Bombeo de la semana 1: u0 = 1 + Bombeo de la semana 2: u1 = 2 + Bombeo de la semana 3: u2 = 2 - La siguiente figura es una representacin grfica del problema, donde los costes acumulados aparecen recuadrados.

PROGRAMACIN DINMICA

38

x0=1 lleno = 3

x1=0
1.2
u1=0

x2=1
0
u2=0 u2=1

x3=0

semilleno = 2
5.1
u0=1

2.1
u1=0

semivaco = 1

3.1 u1=1

vaco = 0
4.1

u1=2

u2=2 u2=2

w0=2
semana 1

w1=1
semana 2

w2=3
semana 3

- Ntese que el nmero de evaluaciones de la funcin de coste responde a la expresin (N-1)+Nx+ Nu+ Nu - z. En la que N es el nmero de etapas, Nx es el nmero de estados posibles de cada etapa, Nu es el nmero de decisiones posibles para cada estado y z el nmero de alternativas imposibles.

PROGRAMACIN DINMICA

39

- En nuestro ejemplo: 2 + 4 + 3 + 3 - 1 = 26 evaluaciones.

PROGRAMACIN DINMICA

40

PROGRAMACIN DINMICA ESTOCSTICA

Determinista vs Estocstica:
- Determinista: + Las perturbaciones wk que actan sobre el sistema son perfectamente predecibles. - Estocstica: + Las perturbaciones wk que actan sobre el sistema se consideran variables aleatorias. + No se conoce el valor exacto de wk, pero si su funcin de distribucin. + En este caso la decisin ptima es la que minimiza el coste esperado.

PROGRAMACIN DINMICA

41

 Ejemplo:
- En el caso anterior del embalse de bombeo la demanda se conoca previamente y esto ha permitido optimizar la gestin del bombeo (determinista). - Hubiera sido ms realista considerar una demanda wk de funcin de distribucin conocida. Por ejemplo: w0,1,2= 1 con probabilidad 0.3 w0,1,2= 2 con probabilidad 0.5 w0,1,2= 3 con probabilidad 0.2 - Cuando se calcula el coste de cada decisin de bombeo, deber hacerse para cada valor de la demanda wk y luego ponderar estos costes con sus probabilidades para obtener el coste esperado.

PROGRAMACIN DINMICA

42

 Programacin Dinmica Estocstica aplicada a la Coordinacin Hidrotrmica:

- En los modelos de planificacin de los sistemas elctricos las estocasticidades que ms influyen son: + Demanda Elctrica. + Hidraulicidad. + Fallos de los grupos. - Estas estocasticidades son consideradas en los modelos basados en programacin dinmica estocstica mediante: + Perturbaciones wk modeladas como variables aleatorias definidas por sus distribuciones de probabilidad. + Directamente en el clculo de los costes de cada etapa.

PROGRAMACIN DINMICA

43

FORMULACIN MATEMTICA
- Tenemos un sistema dinmico en tiempo discreto: xk+1= fk (xk, uk, wk) - Donde + k = 0, 1, ... N-1. + xk pertenece a un espacio de estados posibles. + uk pertenece a un espacio de controles posibles y puede estar restringido en cada estado de cada etapa a un subconjunto del mismo. + wk pertenece a un espacio de perturbaciones posibles y est caracterizada por una funcin de probabilidad que puede depender explcitamente de xk y uk pero no de valores anteriores wk-1 ...w0.

PROGRAMACIN DINMICA

44

- Llamamos = {0, 1, ..., N-1} a una ley de control que para cada estado xk proporciona un control uk: uk = k (xk)

PROGRAMACIN DINMICA

45

- Dado un estado inicial x0 el problema es encontrar una ley de control ptima * = {*0, *1, ..., *N-1} que minimice la esperanza (E) del coste definida como:
N 1 J 0 ( x0 ) = E g N ( xN ) + g k [ f k ( xk , k ( xk ), wk ) ] wk k =0

- Sujeto a la restriccin xk+1= fk(xk, k(xk),wk), y conocidas las funciones de coste gk. - Si llamamos Jk(xk) al coste ptimo para la etapa k, el principio de Bellman se formula como:

PROGRAMACIN DINMICA

46

J k ( xk ) = min E { g k ( xk , uk , wk ) + J k +1 [ f k ( xk , uk , wk ) ]} uk wk
- Donde k = 0,1, ...,N-1.

PROGRAMACIN DINMICA

47

MODELO DE GESTIN HIDROTRMICA DESARROLLADO POR

RED ELCTRICA DE ESPAA (MITRE):

Modelo bsico:
- Caracterizacin del sistema elctrico (simplificado): + Subsistema hidrulico reducido a un embalse, descrito por el caudal mximo de turbinacin, el salto mximo y mnimo, la eficiencia en funcin del salto ... + Subsistema trmico formado por varios grupos, caracterizados por su potencia mxima, eficiencia, costes ... + Red elctrica supuesta como nudo nico. + Demanda elctrica modelada por su curva duracin-carga por escalones. + Hidraulicidad conocida en primera aproximacin.
PROGRAMACIN DINMICA 48

- El problema de programacin dinmica es el siguiente: + La variable de estado x en nuestro problema es el volumen de agua embalsado. + La decisin u que queremos tomar en cada etapa (semana) es la cantidad de agua a emplear en la generacin ptima. + Las perturbaciones w del entorno son la demanda y los fallos de los grupos. - Lo que pretendemos es calcular el coste y la estrategia ptima a partir del estado actual mediante programacin dinmica. + Para cada estado inicial posible de x (nivel de agua) calculamos el coste de explotacin de la semana considerada, para distintos valores de generacin hidrulica. + Se tendrn en cuenta los costes futuros en que incurriremos por dejar el embalse con un determinado nivel de agua: + Coste del combustible trmico al que sustituira en el futuro.

PROGRAMACIN DINMICA

49

+ Es necesario disponer de la curva de costes futuros del agua en funcin del nivel, para cada semana. - Debido al desconocimiento de los costes futuros, el algoritmo de la programacin dinmica se plantea hacia atrs, desde la ltima semana hasta la primera. - La ltima semana se toma lo suficientemente alejada como para que no influya en el presente (6 aos), de este modo le asignamos coste futuro cero. - La curva de costes futuros del agua de la etapa k se calcula a partir de la curva de costes futuros de la etapa k+1. - Este enfoque de la programacin dinmica es determinista, ya que se consideran conocidos a priori los factores de incertidumbre: + Demanda. + Aportaciones.

PROGRAMACIN DINMICA

50

+ Fallos de los grupos.

PROGRAMACIN DINMICA

51

 Proceso de Clculo.
- La siguiente figura esquematiza el proceso de clculo de las dos ltimas etapas.

PROGRAMACIN DINMICA

52

xN-2

xN-1

xN= 0

CN-23

CN-13 3 CT1+CN-13

LLENO

CN-22 CT1+CN-12

CN-12 2

CN-21

CT1+CN-11 CT1+CN-10 CN-20

CN-11 1

CN-10

VACIO
0

etapa N-2

etapa N-1

PROGRAMACIN DINMICA

53

C N -1 = C o s t e s f u t u r o s d e l a g u a
C N -1 0 C N -1 1 C N -1 2 C N -1 3

L a p e n d ie n te d e e sta c u r v a e s e l v a lo r m a r g in a l d el a g u a en la eta p a N -1

x N -1 0 1 2 3

- Dado que el coste futuro del agua para la etapa N es igual a cero, la trayectoria ptima en cada caso es la de mxima turbinacin. - La curva de costes futuros CN-1 para la etapa xN-2 se obtiene de los costes calculados para cada estado xN-1. - Para la etapa N-2 hay que calcular los costes para cada estado xN-2. La figura muestra el proceso para el nivel 1.

PROGRAMACIN DINMICA

54

+ Se ha supuesto que el coste total mnimo (trmico + futuro del agua) se obtiene para XN-1 igual a 2. + Por tanto CN-21 = CT1 + CN-12 . + La trayectoria ptima para cada xk debe coincidir con aqulla que iguale el valor marginal del agua en la curva de costes futuros Ck+1, con el coste marginal del equipo trmico CT de la etapa k.

PROGRAMACIN DINMICA

55

 Tratamiento de la aleatoriedad en la demanda y los fallos trmicos.

- La demanda se modela mediante su curva duracin carga, con tres o cinco niveles de carga, distinguiendo entre das laborables y festivos en el segundo caso. - Se plantean dos situaciones: + Fallo del 4 % de todo el equipo generador con probabilidad 0.7. + Fallo del 14 % de todo el equipo generador con probabilidad 0.3. - El algoritmo de la programacin dinmica no se ve modificado por este tratamiento de la demanda y de los fallos, pero se multiplican por 10 (5 demandas y 2 tasas de fallo) el nmero de clculos necesarios en cada etapa.

PROGRAMACIN DINMICA

56

PROGRAMACIN DINMICA

57

 Tratamiento de la aleatoriedad en las aportaciones.

- Las aportaciones de cada semana del ao son modeladas mediante sus funciones de distribucin, obtenidas de datos histricos, y discretizadas en cinco niveles de aportaciones. - Para cada estado inicial se calcula la trayectoria ptima en base al coste mnimo esperado. Se calculan cinco costes distintos, uno para cada nivel de aportaciones, ponderndose con sus probabilidades. Esto es equivalente a calcular cinco curvas de costes futuros y luego ponderarlas.

- El enfoque anterior puede mejorarse considerando la correlacin existente entre las aportaciones de semanas consecutivas: + Esto se representa mediante una tabla de probabilidades compuestas (55), es decir, la probabilidad condicionada de que a un

PROGRAMACIN DINMICA

58

determinado nivel de aportaciones le siga otro cualquiera de los cinco posibles.

PROGRAMACIN DINMICA

59

+ Ahora las cinco curvas de coste futuro (k+1) se ponderan con las probabilidades compuestas, obtenindose cinco curvas, una para cada nivel de aportaciones de la etapa k.

Mltiples Embalses.
- Para una representacin realista del caso espaol son necesarios entre 30 y 40 embalses. - El nmero de estados posibles de cada etapa crece de forma exponencial al considerar mltiples embalses (7 40), as como el nmero de trayectorias a tantear para encontrar la ptima. - Esto implica que la solucin del problema usando programacin dinmica sobre los 40 embalses sea inviable (maldicin de la dimensionalidad). - Para evitar este inconveniente de la programacin dinmica el problema se resuelve de la siguiente forma:

PROGRAMACIN DINMICA

60

+ La trayectoria ptima para cada estado inicial no se obtiene tanteando todas las posibles, sino directamente, mediante tcnicas de programacin lineal con restricciones y funcin objetivo no lineales: + Se utiliza la herramienta MINOS. + La funcin objetivo es el coste total, suma del trmico (lineal), ms el coste futuro del agua (no lineal). + En este clculo se incluye toda la red hidrulica en detalle agrupada en unos 40 subsistemas. + Los resultados obtenidos del problema de optimizacin planteado, para cada estado inicial, son: + La trayectoria ptima. + El coste de la trayectoria ptima, para construir las curvas de costes futuros. + Los costes marginales del agua para cada embalse.

PROGRAMACIN DINMICA

61

+ Para limitar el nmero de estados iniciales, o lo que es lo mismo para limitar el nmero de trayectorias ptimas que hay que buscar, el algoritmo de la programacin dinmica reduce el nmero de estados iniciales posibles de forma apriorstica.

- Mediante el artificio anterior se obtienen resultados desagregados del nivel de cada embalse utilizando sus costes marginales, pese al reducido nmero de estados iniciales. - El algoritmo de programacin dinmica planteado se considera suficientemente aproximado por REE, pese a la simplificacin en los estados posibles.

PROGRAMACIN DINMICA

62