MODELOS DE FLUJO DE REDES
RUTA MÁS CORTA
1. Usted debe hacer un viaje en automóvil a una ciudad que nunca ha visitado. Estudia un plano
para determinar la ruta más corta hasta su destino. Según la ruta que elija, hay otras cinco
ciudades (llamadas A, B, C, D, E) por las que puede pasar en el camino. El plano muestra las
millas de cada carretera que son una conexión directa entre dos ciudades sin que otra
intervenga. Estas cifras se resumen en la siguiente tabla, donde un guion indica que no hay
conexión directa sin pasar por otras ciudades.
a) Formule éste como un problema de la ruta más corta al trazar una red donde los nodos son
ciudades, los arcos son carreteras y los números la distancia en millas.
b) Use el algoritmo descrito en la sección 9.3 para resolver este problema de la ruta más corta.
La ruta más corta será O-A-B-D-T con un total de 165 millas.
2. Una compañía aérea local piensa comprar un tractor nuevo para mover el tren de carros que
llevan y traen el equipaje de los aviones que aterrizan en un pequeño aeropuerto que está en
pleno crecimiento. Dentro de tres años se instalará un nuevo sistema mecanizado de
transporte de equipaje, por lo que después no se necesitará el tractor. No obstante, tendrá una
carga de trabajo pesada y los costos de operación y mantenimiento aumentarán rápido y
podría resultar costeable reemplazarlo en uno o dos años. La siguiente tabla proporciona los
costos descontados netos totales asociados con la compra del tractor (precio de compra
menos valor de venta del tractor en uso más costos de operación y mantenimiento) al final del
año i y si se reemplaza al final del año j (donde el momento presente es el año 0).
El problema es determinar en qué momento (si existe) debe reemplazarse el tractor para
minimizar el costo total durante los tres años.
a) Formule éste como un problema de ruta más corta.
b) Utilice el algoritmo descrito en la sección 9.3 para resolver este problema de ruta más corta.
La ruta más corta para tener el costo mínimo será 0-1-3 con un total de $46000 durante los 3 años.
3. Utilice el algoritmo descrito en la sección 9.3 para encontrar la ruta más corta a través de las
redes a) y b), en las cuales los números representan las distancias reales entre los nodos
correspondientes.
a)
Hay dos rutas que son las más cortas las cuales son O-A-B-E-D-T y O-A-B-D-T con un total de 16
b)
La ruta más corta es O-C-F-G-T con un total de 17
4. Un vuelo de Speedy Airlines está a punto de despegar de Seattle sin escalas a Londres. Existe
cierta flexibilidad para elegir la ruta precisa, según las condiciones del clima. La siguiente red
describe las rutas posibles consideradas, donde SE y LN son Seattle y Londres,
respectivamente, y los otros nodos representan varios lugares intermedios.
El viento a lo largo de cada arco afecta de manera considerable el tiempo de vuelo, y, por ende, el
consumo de combustible. Con base en el informe meteorológico actual, junto a los arcos se
muestran los tiempos de vuelo (en horas). Debido al alto costo del combustible, la administración
ha adoptado la política de elegir la ruta que minimiza el tiempo total de vuelo.
a) ¿Qué juega el papel de “distancias” en la interpretación de este problema?
Que el tiempo dependerá de la distancia
b) Use el algoritmo descrito en la sección 9.3 para resolver este problema de la ruta más corta.
La ruta más corta es SE-C-E-LN para poder tener el menor tiempo posible con 11.3 horas de vuelo.
5. La empresa de transportes “Emtrafesa” Trujillo ofrece las salidas diarias a Chiclayo, Lima, Piura.
Además, basados en un análisis de mercado desean incorporar la ruta Tumbes-Tacna,
incluyendo distritos aledaños para llegar a su destino. (Distancia en millas). Determinar las
rutas más cortas entre la ciudad de Tumbes (Nodo A) y la ciudad de Tacna (Nodo H).
a) Utilice el algoritmo descrito en la sección 9.3 para encontrar la ruta más corta a través de
las redes.
La ruta más corta es A-C-G-H para poder tener la menor distancia de 9.
DISTANCIA MÍNIMA
FLUJO MÁXIMO
