1 problemas de decisión tipo particular de problemas de optimización sistemas que evolucionan con...

1

Problemas de decisión Tipo particular de problemas de optimización

Sistemas que evolucionan con el tiempo Se toman decisiones en momentos sucesivos de

tiempo Decisiones dependen del estado del sistema

Políticas óptimas: mejores decisiones para un estado dado

Programación dinámica

2

Problema de inventarios Demanda prevista para los próximos 12 meses:

250 200 200 250 300 300 350 300 250 250 200 350

Costes Costes de pedido - fijos: 200

- variables: 10 Costes de inventario: 2 Costes de ventas perdidas: 25

Ejemplo 1

3

Variables: Meses en los que se hace un pedido Tamaño del pedido

Supondremos que los valores posibles son prefijados:

0 – 100 – 200 – 300 – 400 – 500

Función objetivo: Coste total de operación del sistema

Restricciones: Tamaño de los inventarios, ventas perdidas

Ejemplo 1

4

Generación de energía eléctrica Precios estimados para próximas 12 horas

45 45 47 49 51 49 51 47 45 49 52 49

Variables Niveles de producción de una unidad

Objetivo Máximo beneficio

Ejemplo 2

5

Costes de generación

C (€) = 41 E + 0.015 E 2

Zona de operación permisible:

100 – 300 Mwh Coste de arranque:

20000 € Costes de cambios en el nivel de generación:

150 € Máxima tasa de cambio:

50 Mwh/h

Ejemplo 2

6

Variables: Niveles de generación Supondremos los siguientes valores aceptables

0 - 100 - 150 - 200 - 250 - 300

Restricciones: Máximo cambio en los niveles de generación Máximo/mínimo nivel de generación

Incluido en los valores aceptables

Ejemplo 2

7

Formulación del problema

Elementos del problema Variables de estado

Información necesaria para conocer la situación del sistema, xt

Variables de decisión Acciones a tomar para modificar el estado, yt

Ley de movimiento Relación entre variables de estado y de decisión

xt+1 = gt ( xt , yt )

8

Formulación del problema

Elementos del problema (ii) Función de costes

t t ft ( xt , yt ) + ( xT ) Factor de descuento, t

Medida de preferencia por ingresos actuales frente a ingresos futuros

Solo es importante para horizontes largos

Valor final, ( xT ) Preferencia por que el sistema termine en un estado u otro T , horizonte de planificación

9

Formulación del problema

Problema de programación matemáticaMin t t ft ( xt , yt ) + ( xT )

s.a xt+1 = gt ( xt , yt )

yt Y Se quiere calcular la política óptima

Funciones yt = at ( xt ) que proporcionen el óptimo para el problema anterior No solo los valores óptimos de las variables Solución más robusta

10

Cálculo de soluciones Demasiado costoso explorar todas las alternativas Seleccionar algunas alternativas:

Principio del máximo Solo algunas alternativas satisfacen condiciones

necesarias para estar en un máximo Se estudian distintas partes de la solución Todas ellas deben parecer ser parte del óptimo

Principio del Máximo

11

Variables de estado: Situación del sistema en cada periodo

Inventarios, nivel de generación

Variables de control: Decisiones a tomar

Momentos de pedido, tamaños de pedido, cambios en niveles de generación

Principio del Máximo

12

Descripción Problema a resolver en un intervalo de tiempo

[0,T ] partiendo de x0

Trayectoria óptima de variables de estado,

xt*, t [0,T ]

Propiedad de la trayectoria óptima: Si empezamos desde xt

*, obtenemos la misma trayectoria

Principio del Máximo

13

Consecuencias: Construir una trayectoria óptima a partir de partes

pequeñas El problema se reduce a una serie de problemas de menor

tamaño Ventajoso si costes de solución crecen más rápido que

linealmente Problemas menores: para un periodo único Limitación:

Como xt* no se conoce, probar todos los valores

Principio del Máximo

14

Ilustración

xx

tt TT

xx00

Principio del Máximo

15

Ilustración

xx

t+1t+1 TTtt

xxtt

xxtt’’

11

22

1>2?1>2?

Principio del Máximo

16

Aplicación Partimos de la situación en T Para cada estado, coste del estado VT (x ) Para cada periodo de tiempo y cada estado,

calculamos: acción óptima en t compatible con costes óptimos de t +1 a T

Principio del Máximo

17

Aplicación Formalmente, calculamos una función de valor

Vt ( x ) = miny { ft ( x , y ) + Vt+1(gt ( x , y )) }

para cada valor de x y de t Una vez obtenidos los valores para t = 0

Seleccionar valor correspondiente a estado inicial Reconstruir camino de mínimo coste

Principio del Máximo

18

Principio del Máximo

Procedimiento de solución1. Se calcula el valor de la función VT ( x ) = ( x )

2. Para el periodo T – 1 se calcula VT-1 ( x ) como

VT-1 ( x ) = miny { fT-1 ( x , y ) + VT (gT-1 ( x , y )) } Para cada valor de x se calcula el valor de

fT-1 ( x , y ) + VT (gT-1 ( x , y ))

para todos los valores de y Se selecciona el menor y se conserva el valor de y(x) que

corresponde al mínimo (política óptima)

19

Principio del máximo

Procedimiento de solución3. Se repite el proceso hasta t = 0

Se obtiene V0 ( x0 )

4. Se reconstruye la trayectoria óptima a partir de los valores de y(x)

Se parte de x0 y se obtiene y0 = y(x0)

Se calcula x1 = g0 ( x0 , y0 )

Se repite el proceso hasta obtener xT

20

Gestión de inventarios Estado: nivel de inventario Variables de control: pedidos Objetivo: costes Horizonte de tiempo: 12 periodos Valor final

Valoración inventarios periodo 13

V13 (I13 ) = -10I13

Ejemplo 1

21

Aplicación del procedimiento Para el periodo 12,

V12 (I ) = minP {f (I,P ) + V13(I13(I ,P ))}

I13(I ,P ) = max (0, I + P - D12) Cálculo de valores (I = 100, P = 300):

I13 = I + P - D = 100 + 300 - 350 = 50

f (I,P ) = K + cP + hI = 100 + 10300 + 2100 = 3300

V (I,P ) = f (I,P ) + V (I13) = 3300 - 500 = 2800

Ejemplo 1

22

Valores para I = 100,

Valor óptimo para I = 100,V12 (100) = 2800, si P = 300 ó 400

Valores óptimos

Ejemplo 1

P 0 100 200 300 400 V 3950 3550 3050 2800 2800

I 0 50 100 150 200 250 300 V 3600 3200 2800 2400 2000 1600 1200 P 400 400-300 400-300 400-200 400-200 400-100 400-100

23

Repetir proceso para otros periodos Cálculos para I = 150, P = 0, t = 11:

I12 =I +P -D = 150 + 0 - 200 = -50, I12 = 0

f (I,P )= hI + sD = 2150 + 2550 = 1550

V (I,P )=f (I,P )+V (I12)=1550+3600=5150 Valor óptimo para I = 150, t = 11:

V11 (150) = 4600, si P = 100

Ejemplo 1

24

Resultados

Inicio del periodo 7 ¿Qué sucedería si I7 = 200?

Ejemplo 1

I 0 50 100 150 200 250 300 V13 0 -500 -1000 -1500 -2000 -2500 -3000 V12 3600 3200 2800 2400 2000 1600 1200 V11 5700/2 5400/2 4900/1 4600/1 4000/0 3700/0 3400/0 V10 8500/3 7900/2 7700/2 7100/1 6850/1 6200/0 6000/0 V9 11000 10700 10200 9900 9400 9000 8500 V8 14100 13900 13300 13100 12500 12250 11600 V7 17950 17300 17150 16500 16350 15700 15450

25

Solución óptima para I7 = 200

Calcular valores a partir del periodo 7 Usando el tamaño óptimo de pedido, calcular el

inventario en el periodo 8 Repetir hasta el periodo 13

Ejemplo 1

Periodo 7 8 9 10 11 12 13 Inventario 200 0 0 50 0 0 50 Pedido 100 300 300 200 200 400

26

¿Qué sucedería si I7 = 50? Utilizar la información en tabla óptima Repetir el procedimiento para obtener

Ejemplo 1

Periodo 7 8 9 10 11 12 13 Inventario 50 0 0 50 0 0 50 Pedido 300 300 300 200 200 400

27

Generación de energía eléctrica Estado: nivel de generación Variables de control: cambio de nivel Objetivo: beneficio Horizonte de tiempo: 12 horas Valor final: valoración de nivel de generación

500 si P13 > 0 V13(P13) = 0 si P13 = 0

Ejemplo 2

28

Cálculos Para t = 12,

V12 (P ) = max {f (P , ) + V13(P13(P,))}

P13(P , ) = P + , = 0 , 50 Valores para P = 100, = 50:

P13 = P + = 150

f (P,)=pP - aP - bP 2 - c = 61.6 (P = 125)

V (P,)=f (P , )+V (P13)=61.6+500=561.6

Ejemplo 2

29

Otros cálculosPara P = 100,

Valor óptimo para P = 100,

V12(100) = 565, si = 0Valores óptimos

Ejemplo 2

-50 0 50 V 21.25 565 561.5

P 0 100 150 200 250 300 V 0 565 586.3 600 606.3 605

30

Resultados

Inicio del periodo 7 ¿Qué sucede si P7 = 200?

Ejemplo 2

P 0 100 150 200 250 300 V13 0 500 500 500 500 500 V12 0 565 586.6 600 606.3 605 V11 0 685.3 731.6 762.8 787.5 800 V10 0 793.1 841.9 876.6 893.8 905 V9 0 853.4 885.6 896.6 900 890 V8 0 922.2 941.9 956.6 956.3 936.6 V7 0 1028.4 1070.6 1096.6 1112.5 1102.8

31

Solución óptima para P7 = 200

De los valores en la tabla óptimaValores de las variables de control

Código de colores en la tabla

Ejemplo 2

Hora 7 8 9 10 11 12 13 Generación 200 200 200 200 250 250 250 Cambio 0 0 0 50 0 0

32

Renovación de equipos Coste de compra: 100 Costes de operación:

Ejemplo 3

Año Coste Valor residual 1 9 75 2 10 55 3 12 35 4 15 20 5 20 10 6 25 2

33

Encontrar política de renovación óptima Para un horizonte de 6 años Para un horizonte de 7 años Para un horizonte infinito

Factor de descuento: 0.95 Condición inicial: edad del equipo Problema adicional: horizonte infinito

Ejemplo 3

34

Formulación del problema: Variable de estado:

Edad del equipo Variable de decisión:

Renovar o no en un periodo dado Costes: operación, compra, valor residual Función de valor: coste total

Ejemplo 3

35

Solución Suponiendo un horizonte a 5 años:

V6(e ) = Vr (e )

Periodo 5:V5 (e ) = min { Ca - Vr (e ) + Co (1) + V6(2) ,

Co (e ) + V6(e + 1) }

Ejemplo 3

36

Resultados Si el equipo tiene una edad de dos años

Horizonte a 6 años:

Renovar pasados 5 años Horizonte a 7 años:

Renovar pasados 4 años ¿Como seleccionar entre ambas opciones?

Resolver con horizonte infinito

Ejemplo 3

37

Para que el problema tenga solución Datos estacionarios Definir y trabajar con coste por periodo

Fórmula de soluciónJ (x ) = minu {c (u ) + J (y (x ,u ))}

Procedimientos de solución: Iteraciones sucesivas Iteración en políticas

Horizonte Infinito

38

Cálculos para horizonte infinitoJ0 = 0, Jk+1 = minu {cu + PuJk }

J100 = ( 530 548 567 584 599 610 ) Decisiones:

( NR NR NR NR NR R ) Política óptima:

Renovar tras 6 periodos

Ejemplo 3

39

Extensiones: Datos aleatorios

Se optimiza el valor esperado

Vt (x ) = minu E {ct (ut ,wt) + Vt+1(xt+1(x ,ut ,wt ))}

Tiempo continuo Solución directa solo es posible en casos especiales Discretizar el tiempo

Principio del Máximo

40

Resumen Técnica potente pero compleja Existen herramientas computacionales eficientes

Tanto para formulación como para solución Soluciones no son siempre intuitivas Herramientas adaptadas a propiedades del

modelo Programación lineal

Programación dinámica

41

Ejemplo 4

Hillier y Lieberman Un estudiante tiene 10 días para

preparar los exámenes de 4 cursos Asignar días de estudio a cada curso

Cada día asignado a un único curso Estimación de mejoras en

calificaciones Optimizando la mejora en las

calificaciones

A B C D

1 2 3 2 3

2 4 3 3 4

3 5 4 5 5

4 6 5 6 7

42

Ejemplo 5 Hillier y Lieberman

Se quiere diseñar un sistema que requiere de cuatro componentes Para mejorar la fiabilidad se

pueden instalar varias unidades de cada componente en paralelo

Las probabilidades de funcionamiento correcto y los costes se dan en las tablas siguientes

El presupuesto disponible es de 1000€

C1 C2 C3 C4

1 0,55 0,6

0,7

0,5

2 0,65 0,7

0,8

0,65

3 0,85 0,8

0,9

0,8

C1 C2 C3 C4

1 100

200

100

200

2 200

400

300

300

3 300

500

400

400

43

Ejemplo 6

Valoración de opciones Te ofrecen una opción para comprar acciones

Vencimiento en 3 meses Precio de ejercicio 24€

Estimación del comportamiento de la acción Promedio de cambio semanal 0,5€ Desviación típica 1€ En realidad estos valores debieran darse sobre las tasas

de cambio Valor de la opción en función del valor de la acción

44

Ejemplo 7

Hillier y Lieberman Campaña de publicidad

3 etapas: ofertas especiales, anuncios y fidelización Etapa 1:

m = 10 x1 - x12

Etapa 2:

f2 = 0.4 + 0.1 x2 Etapa 3:

f3 = 0.6 + 0.07 x3 Presupuesto total: 4 M€ Maximizar m f2 f3