Ejercicios Resueltos Programacion Dinamica

EJERCICIOS PROPUESTOS
Ejercicio N°01:
Se trata de construir una autopista entre dos ciudades A y K, existiendo varias ciudades por las que puede pasar la autopista, tal como se indica en el siguiente grafo, pudiendo clasificarse estas ciudades e grupos o fases y habiéndose asignado a los arcos del grafo el importe de los costes totales en cientos de millones de pesetas (costes de realización,costes de expropiación, etc.)
Determinar, utilizando programación dinámica la autopista de coste mínimo que une las ciudades A y K.

SOLUCION:
* Como podemos observar el problema costa de IV etapas:
* ETAPA IV.- Se tiene 4 opciones:
G-K=30
H-K=25
I-K=20
J-K=35
* ETAPA III.- Se tiene varias opciones, de las cuales solo escogeremos los valores mínimos.

* Desde el punto"E”:
E-G-K=40+30=70
E-H-K=35+25=60………min
E-J-K=25+35=60………min

* Desde el punto “F”:
F-H-K=45+25=70
F-I-K=30+20=50………min
F-J-K=40+35=75

* Por lo tanto las trayectorias mínimas serán
E-H-K=35+25=60
E-J-K=25+35=60
F-I-K=30+20=50

* ETAPA II.- Con los resultados anteriores, hallaremos valores para le etapa II:

* Desde el punto “B”:

B-E-H-K=50+60=110
B-E-J-K=50+60=110B-F-I-K=30+50=80…….min

* Desde el punto “C”:

C-E-H-K=20+60=80………min
C-E-J-K=20+60=80………min
C-F-I-K=45+50=95

* Desde el punto “D”:

D-F-I-K=25+50=75………min

* Los valores mínimos para la etapa II son
B-F-I-K=80
C-E-H-K=80
C-E-J-K=80
D-F-I-K=75

* ETAPA I: en esta ultima etapa encontraremos el costo mínimo
* Desde el punto “A”

A-B-F-I-K=15+80=95…………minA-C-E-H-K=20+80=100
A-C-E-J-K=20+80=100
A-D-F-I-K=30+75=105

* El costo mínimo que une las ciudades de “A” y “K” es:

EJERCICION°2
a) Rresolver el siguiente problema de control, utilizando programación dinámica.

Minu0,u1,u2x1-102+x2-152+u0+u1+u2

Sujeto a: xk+1=2xk+uk, parak=0.1.2.
Con:
x0=6
x3=20
Solución:
Observaciones:
* K=3
* 02F(xk,uk,k)=x1-10²+x2-15²+u0+u1+u(2)
*Sx3=0
* xk+1=2xk+uk

* k=0 →x1=2x0+u(0)
f(x0,u0,0)

* k=1 →x2=2x1+u(1)
f(x1,u1,1)

* k= 2 →x3=2x2+u(2)
fx2,u2,2





Gráficamente se tiene;

u(o) u(1) u(2)

x(0) x(1) x(2) x(3)

periodo1 periodo 2 periodo 3

Para resolver el problema por programación dinámica, comenzamos situándonos en el instante final, analizando acontinuación cada uno de los periodos de final a principio de horizonte temporal.
* FINAL: sea x(3) dado
X (3)=0 ya que no aparece en el funcional objetivo del problema, la ecuación de Bellman relevante será la siguiente:
J3x(3)=Sx3=0
* PERIODO 3: sea x(2) dado,
La expresión relevante de la “ecuación de Bellman” es;
JkX(k)=minu(k)Fxk,uk,k+Jk+1f(xk,uk,k)J2X(2)=minu(2)Fx2,u2,2+J3f(x2,u2,2)
J2X(2)=minu(2)Fx2,u2,2+J3x(3)
Siendo;
X (3)=0=2x (2)+u (2)
u*(2)=-2x(2)
J2 X(2)=x2-15²-2x(2)

* PERIODO 2: Sea x (1) dado.
La relevante ecuación de Bellman es;
J1X(1)=minu(1)Fx1,u1,1+J2f(x1,u1,1)
J1X(1)=minu(1)Fx1,u1,1+J2x(2)

* PERIODO 1: Sea x(0)=6, dado:
La ecuación de Bellman para el periodo 1 es:J0X(0)=minu(0)Fx0,u0,0+J1f(x0,u0,0)
J0X(0)=minu(0)Fx0,u0,0+J1x(1)











EJERCICIO N°02
Resolver los siguientes problemas, utilizando la programación dinámica:
b).
Máx J=k=0410xk-0.1uk2
sujeto a :xk+1=xk+uk
con :x0=0,
SOLUCIÓN
* Observaciones:
Según la restricción se puede definir lo siguiente:
* x(5)=x4+u4…(a)
* x(4)=x3+u3…(b)* x3=x2+u2…(c)
* x2=x1+u1…(d)
* x(1)=x0+u0…(e)
* x0=0 …(f)

* Para T=5
* La ecuación de relevante de Bellman
JTx(T)=Sx(T)⇒J5x(5)=Sx(5)…(1)
* Sabemos que:
Sx(5)=J5x(5)…(2)
* Pero como en la función la aportación a la función objetivo de Sx(5)=0 ya que no aparecen la funcional objetivo del problema.
J5x(5)=Sx(5)=0 …(3)...