Problema y Plantemiento:
Un banco ha decidido conectar terminales de computadora de cada sucursal a la computadora central de su oficina matriz mediante líneas telefónicas especiales con dispositivos de telecomunicaciones. No es necesario que la línea telefónica de una sucursal esté conectada directamente con la oficina matriz. La conexión puede ser indirecta a través de otras sucursales que esté conectada (directamente o indirectamente) a la matriz. El único requisito es que exista alguna ruta que conecte a todas las sucursales con la oficina matriz.
El cargo por las líneas telefónicas especiales es directamente proporcional a la distancia cableada, en donde esta distancia en millas es:
| | Principal | Suc. 1 | Suc. 2 | Suc. 3 | Suc. 4 | Suc. 5 |
| Principal | -- | 190 | 70 | 115 | 270 | 160 |
| Suc. 1 | 190 | -- | 100 | 110 | 215 | 50 |
| Suc. 2 | 70 | 100 | -- | 140 | 120 | 220 |
| Suc. 3 | 115 | 110 | 140 | -- | 175 | 80 |
| Suc. 4 | 270 | 215 | 120 | 175 | -- | 310 |
| Suc. 5 | 160 | 30 | 220 | 80 | 310 | -- |
La administración desea determinar qué pares de sucursales conectar directamente con las líneas telefónicas especiales para que todas queden conectadas ( de modo directo o indirecto) a la oficina matriz con un costo total mínimo.
La red nos queda de la siguiente forma:
Siguiendo el algoritmo de PRIM la red nos queda de la siguiente forma:
Interpretación y resultado:
Las lineas rojas indican que suscursales se deben de conectar para que todas puedan estar conectadas directa o indirectas.
La sucursal 2 debe estar conectada con la principal y la 4
La sucursal 1 con la 5 y la 2
La sucursal 4 con la 5
Min Z= 420
No hay comentarios:
Publicar un comentario