Planteamiento del problema: Optimización de redes
Segunda parte
La red de telecomunicaciones por fibra óptica que instalaremos puede llegar a fallar si se corta un enlace. Como los ocho inmuebles que conectaremos son todos edificios altos, este problema lo resolveremos instalando una red de respaldo de enlaces mediante antenas de radio. Los enlaces de la red de respaldo son bastante menos costosos pero la habremos también de optimizar en la medida de lo posible.
El cuadro de costos (en miles de pesos) de la red de respaldo para los mismos ocho inmuebles es el siguiente.
B | C | D | E | F | G | H | |
---|---|---|---|---|---|---|---|
A | 10 | 20 | 10 | 10 | 10 | 30 | 10 |
B | 10 | 10 | 20 | 10 | 20 | 10 | |
C | 10 | 10 | 10 | 30 | 10 | ||
D | 10 | 10 | 20 | 10 | |||
E | 10 | 10 | 20 | ||||
F | 10 | 30 | |||||
G | 10 |
Como podemos apreciar en el cuadro, muchos costos son iguales. Lo anterior se debe a que estamos usando solo tres diferentes tipos de antenas parabólicas de diferentes precios.
Problema
Resumiendo, el problema que abordaremos en esta unidad
consiste en encontrar la lista de enlaces entre puntos de
tal forma que la suma de los costos correspondientes sea la
menor posible, pero que haya siempre una ruta que permita
comunicar dos puntos cualesquiera.
¿Tendría sentido este problema si pensamos en ciudades, en lugar de inmuebles, y carreteras, en lugar de enlaces? ¿Cambiaría en algo el problema o el formato del cuadro de costos?