problema de redes





PRACTICA DIRIGIDA

CURSO: INVESATIGACION DE OPERACIONES II
TEMA: PROBLEMAS DE REDES.
PROFESOR: Ing. LUIS MEDINA AQUINO

Problemas de la Ruta más Corta
1. Un individuo que vive en San Jorge y que trabaja en San Carlos busca una ruta automovilística que minimice el tiempo matutino de manejo. Esta persona ha registrado los tiempos de manejo (en minutos) en las principales rutas quecomunican las diferentes ciudades intermedias. Estos datos se muestran en la tabla. El aspa (X) indica los casos en que ninguna ruta une directamente a los puntos correspondientes.

San Jorge Los Arroyos Km.25 El Sauce Las Cañas San Carlos
San Jorge 0 18 X 32 X X
Los Arroyos 18 0 12 28 XX
Km.25 X 12 0 17 X 32
El Sauce 32 28 17 0 4 17
Las Cañas X X X 4 0 11
San Carlos X X 32 17 11 0

Obsérvese que la matriz es simétrica, es decir, el tiempo que demoraen ir de San Jorge a Los Arroyos es el mismo que el de ir de Los Arroyos a San Jorge.

2. El caso de Producción
Una firma ha ganado un contrato para producir cubiertas. El contrato tiene una duración de 4 años. El proceso de producción requiere de una máquina que carece la firma. Ésta puede comprarla, mantenerla durante los 4 años del contrato y luego venderla en el valor de su rescate, opuede reemplazarla por un modelo, al final de cualquier año dado. Los nuevos modelos requieren menos mantenimiento que los antiguos.
En la tabla se indica el costo neto estimado de reemplazo (precio de compra + mantenimiento - precio de venta) para una máquina comprada al inicio del año i y vendida al inicio del año j. Se trata de determinar en qué momento conviene remplazar la máquina.

Año 2Año 3 Año 4 Año 5
Año 1 12 19 33 49
Año 2 x 14 23 38
Año 3 x x 16 26
Año 4 x x x 13

Este problema puede verse como un problema de ruta más corta, donde se trata de decidir de qué manera "voy" desde el año 1 al año 5. Obsérvese que la matriz es no simétrica, ya que puedo 'ir' del año 1 al año3, pero no puedo volver, como lo indica la ruta prohibida.

3. Ejemplo de la constructora
La Compañía Constructora UPS tiene diversos proyectos de construcción distribuidos en una área de tres ciudades. En ocasiones los sitios de las construcciones se ubican hasta 50 kilómetros de distancia de la oficina general de la empresa. Como se efectúan varios viajes al día para llevar personal, equiposy suministros, hacia y desde los lugares de construcción, los costos relacionados con las actividades de transporte son importantes. En la siguiente tabla se muestran las alternativas de viajes entre la oficina y cinco de los lugares de construcción de la compañía.
Oficina 2 3 4 5 6
Oficina 0 15 10 X X X
2 15 0 6 5 X X
3 10 6 0 X 10 X4 X 5 X 0 4 6
5 X X 10 4 0 3
6 X X X 6 3 0
Determinar la ruta más corta entre la oficina (nodo 1) hasta cada uno de los lugares en donde se encuentran las obras.

Problemas de Árbol de Expansión Mínima

1. Mauro & Cía. quiere comunicar mediante cable telefónico la casa Matriz y las 5 sucursales. El objetivo es permitir la comunicación entre cualquier par desucursales o casa Matriz. Para esto, sin embargo, no es necesario tirar cables entre todos los pares, sino que pueden comunicarse dos sucursales a través de otra intermedia.
Se trata de encontrar el árbol que minimiza la longitud de cable.

Longitud del cable requerido en miles de metros para conectar cada par:

Matriz Suc1 Suc2 Suc3 Suc4 Suc5
Matriz 0 10 2 34 18...