PROGRAMACION DINAMICA DETERMINISTICA




























ACTIVIDAD 2: CONCEPTOS BÁSICOS YAZMIN PATIÑO RIVERA
DE PROGRAMACIÓN DINÁMICAING. INDUSTRIAL

Resuelve el siguiente ejercicio.
La familia Simpsons va a salir de vacaciones desde su ciudad natal Springfield. La familia desea visitar n ciudades y dispone de un total de Mdías para hacerlo. La familia desea saber cuántos días permanecer en cada ciudad de modo de maximizar la satisfacción total de sus vacaciones sabiendo que para cada ciudad i existe una función desatisfacción gi que es función del número de días de permanencia.
Suponga que n = 3 y M = 5 y que las funciones de beneficio gk (xk ) vienen dadas por:

g1(x1)
g2(x2 )
g3 (x3)
xk = 0
0
0
0
xk =1
1
1
1
xk = 2
2
4
3
xk = 3
3
6
3
xk = 4
4
8
2
xk = 5
5
8
1

1. Plantee un modelo de programación dinámica para resolver la planificación de las vacaciones de losSimpsons. Para ello define lo siguiente:
Etapas
Variables de decisión
Estado

2. ¿Cuál es la política ‘optima de permanencia de los Simpsons en cada ciudad si existen 3 ciudades para 5días?
Suponga que no se pierde un tiempo considerable en el traslado de una ciudad a otra.







Supongamos que los Simpsons ya consideraron el orden para visitar cada una de las ciudades ypodemos definir lo siguiente:
xi = Número de días en la ciudad i (variable de decisión de la etapa i).
yi = Número de días sobrantes después de visitar la ciudad (variable de estado i).

Acontinuación se muestra cada etapa para seleccionar la mejor.

Ciudad 3:
No es factible porque a la familia no le queda esa cantidad de días

y3
g3(0)
g3(1)
g3(2)
g3(3)
g3(4)
g3(5)
f3(y3)
x∗ 30
0
i
i
i
i
i
0
0
1
0
1
i
i
i
i
1
1
2
0
1
3
i
i
i
3
2
3
0
1
3
3
i
i
3
2,3
4
0
1
3
3
2
i
3
2,3
5
0
1
3
3
2
1
3
2,3









Ciudad 2:...