Problemas io2

PROBLEMAS DE REDES

PROBLEMAS DE ARBOL DE EXPANSION MINIMA y RUTA CORTA

1.- El Ministerio de Energía está evaluando un proyecto para bombear la producción de los pozos de gas natural (ubicados mar adentro) hasta el pozo P1 el cual, por su cercanía a la playa, ya se encuentra conectado con el punto de entrega ubicado en tierra firme.
Las interconexiones entre pozos se realizará medianteductos y en la tabla adjunta se da el costo (cientos de miles de dólares) de conexión entre dos pozos.
Se desea determinar la red de ductos que transporte el gas natural desde cualquiera de los pozos hasta el pozo P1, de manera que el costo total sea mínimo.

Costo ductos entre A B C D E F G H I J

P1 5 9 20 - 4 - 14 15 - -
A - 6 - - - - - - - -
B 6 - 15 - 10 - - - - 6
C20 15 - 7 20 12 - - - 8
D - - - - 3 - - - 15 9
E 4 10 10 3 - 5 13 6 - -
F - - - - 5 - 7 - - -
G 14 - - - 13 7 - 5 10 -
H 15 - - - 6 - 5 - 12 -
I - - - 15 - - 10 12 - 10
J - 6 6 9 - - - - 10 -

2.- Una determinada provincia del país posee 8 distritos (A, B, C, D, E, F, G, H) que aún no cuentan con luz eléctrica. El gobierno regional desea realizar unproyecto para electrificar dichos poblados, conectándolos con la hidroeléctrica que se encuentra en la capital de la provincia (P). Un estudio técnico ha recomendado que los cables eléctricos deben seguir la ruta de los caminos que unen dichos poblados.
En la siguiente tabla se da las longitudes (en Km) de los caminos que unen en forma directa a dos poblados:

Distancia entre P A B C D E F GH

P - 20 35 - 24 30 - 15 -
A 20 - 18 25 15 - 20 - 30
B 35 18 - 30 - 20 25 - 27
C - 25 30 - - 18 26 - -
D 24 15 - - - 15 - 27 20
E 30 - 20 18 15 - 16 24 -
F - 20 25 26 - 16 - 25 15
G 15 - - - 27 24 25 - 18
H - 30 27 - 20 - 15 18 -

Se desea que la luz llegue a todos los poblados de manera que la longitud total decable sea mínimo. Resuelva el problema como un modelo de red aplicando el algoritmo adecuado y mostrando los pasos seguidos.

3.- Una reserva natural cuenta con 9 puestos de vigilancia unidos entre si por un sistema de caminos.
La longitud de los caminos que unen los puestos de vigilancia se da en la siguiente tabla:

Long. entre A B C D E F G H I J

A -- 7 6 2 -- -- 6 -- -- --B 7 -- 4 3 6 -- -- -- -- --
C 6 4 -- 3 -- -- 8 5 -- --
D 2 3 3 -- 11 9 -- 8 -- --
E -- 6 -- 11 -- 7 9 -- 9 --
F -- -- -- 9 7 -- -- 6 10 --
G 6 -- 8 -- 9 -- -- 11 12 8
H -- -- 5 8 -- 6 11 -- 8 4
I -- -- -- -- 9 10 12 8 -- --
J -- -- -- -- -- -- 8 4 -- --
a) Se desea diseñar una red de telefonía fija que conecte todas las estaciones almínimo costo total. Considere que el tendido de los cables telefónicos siguen la ruta de los caminos. (Nota: El costo de 1 km de cable telefónico incluido la mano de obra es de $2000).
b) Determine la ruta que debe seguir el supervisor de estaciones que se encuentra en A para llegar a la estación I en el menor tiempo posible. Considere que el supervisor viaja a pie a una velocidad de 4 km por hora.Nota: En ambos casos utilice el algoritmo heurístico apropiado, indicando los pasos seguidos.

4.- Diariamente el parque nacional de Iguazú es visitada por cientos de turistas de todo el mundo. Este parque posee 13 puntos de observación de las cataratas, los cuales se encuentran interconectados por un sistema de caminos. El punto de entrada al parque es la estación A en el que se encuentra elpuesto de primeros auxilios, puesto de bomberos, etc.
En la siguiente tabla se da las longitudes (en metros) de los caminos que unen los puntos de observación:

Camino Long. (m) Camino Long. (m) Camino Long. (m)
A – B 300 D – G 300 H – K 400
A – C 500 E – H 700 I – K 600
A – D 400 E – I 400 I – L 900
B – C...