Programacion Dinamica

EJERCICIOS:
1. Roxie LaMothe, propietaria de una gran granja criadora de caballos cerca de Orlando planea instalar un sistema de agua que conecte todos los establos y granero. La ubicación de lasinstalaciones y las distancias entre ellas se dan en la red que se muestra en la figura. Roxie LaMothe debe determinar la forma mas barata de suministrar agua a cada instalación. ¿Que recomiendausted?

SOLUCION:
Este es un problema de árbol de expansión mínima típico que puede ser resuelto a mano. Se inicia mediante la selección del nodo 1, el cual se conecta al nodo más cercano, esto es, elnodo 3. Los nodos 1 y 2 son los siguientes que se van a conectar, seguido por los nodos 1 y 4. A continuación se conecta el nodo 4 al 7 y al 6. En este momento, los únicos puntos restantes que debenser conectados con el nodo 6 al 8 y el 6 al 5. La solución final se presenta en la figura:

2. Petro Chen, una refinería de petróleo localizada sobre el rio Mississppi al sur de Baton Ruge,Louisiana esta diseñando una nueva planta para producir combustible diesel. La figura muestra la red de los centros de procesamiento principales junto con la velocidad de flujo existente (en miles degalones de combustible). A la administración de Petro Chen le gustaría de terminar la cantidad máxima de combustible que puede fluir a través de la planta, del nodo 1 al nodo 7.

0
3
1
1
4
6
0
12
3
3
4
4
5
8
5
0
1
1
0
2
3
0
3
1
3
5
4
6
7
2
0
3
1
1
4
6
0
1
2
3
3
4
4
5
8
5
0
1
1
0
2
3
0
3
1
3
5
4
6
7
2

SOLUCION:
Este problema puede serresuelto siguiendo los pasos de la técnica de flujo máximo. Se inicia mediante la selección arbitraria de la trayectoria 1 – 2 – 5 – 7. El flujo es 3 a lo largo de esta trayectoria. La siguientetrayectoria que se elige 1 – 2 – 4 – 7. El flujo máximo posible, considerando el flujo a través de 1 – 2 – 5 – 7 es 1. El flujo a través de 1 – 7 es 4, y a través de 1 – 5 – 6 - 7 es 1. Por ultimo, el...