Ejercicios propuestos

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=110

B-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…………min

A-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

Rresolver el siguiente problema de control, utilizando programación dinámica.

〖Min〗┬(u(0),u(1),u(2) )⁡〖[x(1)-10]^2+[x(2)-15]^2+u(0)+u(1)+u(2)〗

Sujeto a: x(k+1)=2x(k)+u(k),parak=0.1.2.

Con:

x(0)=6

x(3)=20

Solución:

Observaciones:

K=3

∑_0^2▒〖F(x(k),u(k),k)〗=[x(1)-10]²+[x(2)-15]²+u(0)+u(1)+u(2)

S[x(3)]=0

x(k+1)=2x(k)+u(k)

k=0 →x(1)=2x(0)+u(0)

f(x(0),u(0),0)

k=1 →x(2)=2x(1)+u(1)

f(x(1),u(1),1)

k= 2 →x(3)=2x(2)+u(2)

f(x(2),u(2),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 a continuació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:

J_3 {x(3)}=S[x(3)]=0

PERIODO 3: sea x(2) dado,

La expresión relevante de la “ecuación de Bellman” es;

J_k {X(k)}=min┬(u(k))⁡{F(x(k),u(k),k)+J_(k+1) {f(x(k),u(k),k)}}

J_2 {X(2)}=min┬(u(2))⁡{F(x(2),u(2),2)+J_3 {f(x(2),u(2),2)}}

J_2 {X(2)}=min┬(u(2))⁡{F(x(2),u(2),2)+J_3 {x(3)}}

Siendo;

X (3)=0=2x (2)+u (2)

u*(2)=-2x(2)

J_2 { X(2)}=[x(2)-15]²-2x(2)

...