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

...