ALGORITMO DE LA RUTA MÁS CORTA
Ya el nombre de este tipo de algoritmo es bastante sugestivo. El algoritmo de la ruta más corta consiste, si es necesario decirlo, en una modalidad de problemas de
redes, en la cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino, sin importar el
número de nodos que existan entre estos.
Esta modalidad de problemas puede solucionarse como un modelo de
transbordo normal, sin embargo la principal sugerencia es la de
establecer una oferta en el nodo fuente igual a una unidad (1) y
establecer una demanda en el arco destino igual a una unidad (1).
Vale la pena considerar, que en la práctica, es muy frecuente la
utilización del algoritmo resultante con variaciones que consisten en la
minimización de tiempos, no necesariamente de distancias.
Algoritmo de la Ruta más corta - Ejemplo
Un minero ha quedado atrapado en una mina, la entrada a la mina se
encuentra ubicada en el nodo 1, se conoce de antemano que el minero
permanece atrapado en el nodo 9, para llegar a dicho nodo
hay que atravesar una red de túneles que van conectados entre sí. El
tiempo de vida que le queda al minero sin recibir auxilio es cada vez
menor y se hace indispensable hallar la ruta de acceso
al nodo 9 más corta. Las distancias entre nodos de la mina se
encuentran en la siguiente gráfica dadas en cientos de metros. Formule
un modelo de transbordo y resuelva mediante cualquier paquete
de herramientas de investigación operativa que permita establecer la
ruta más corta para poder así auxiliar al minero.
VARIABLES DE DECISIÓN
El nombre de las variables en este caso poco importa, dado que de
ser escogida para la solución básica eso significa simplemente que será
empleada como ruta para ir a rescatar al minero, sin
embargo nada tiene de malo el que se le pueda asociar con el envío
de unidades desde la entrada de la mina hacia el minero, por ende puede
sugerirse este como nombre de las variables.
"Cantidad de unidades enviadas desde el nodo i hacia el nodo j".
X13 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3
X23 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3
X24 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4
X32 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2
X34 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4
X35 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5
X46 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6
X47 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7
X54 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4
X56 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 6
X57 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 7
X58 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 8
X67 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 7
X69 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 9
X76 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 6
X78 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 8
X79 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 9
X87 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 7
X89 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 9
RESTRICCIONES
Restricciones de Oferta y Demanda
Hay que recordar que el objetivo de este modelo es la consecución de
un plan de ruta que nos permita encontrar al minero lo más pronto
posible al recorrer la distancia mínima posible, por ende la
clave para plantear el modelo como si fuese de transbordo es
establecer una demanda y oferta igual a la unidad (1).
X69 + X79 + X89 = 1
Restricciones de Balance
X12 + X32 - X23 - X24 = 0
X13 + X23 - X32 - X34 - X35 = 0
X24 + X34 + X54 - X46 - X47 = 0
X35 - X54 - X56 – X57 – X58 = 0
X46 + X56 + X57 - X67 – X69 = 0
X67 + X47 + X57 + X87 – X76 – X78 – X79 = 0
X78 + X58 – X89 = 0
En palabras sencillas: "Todo lo que entra a cada nodo es igual a lo que sale de él"
FUNCIÓN OBJETIVO
ZMIN = 4X12 + 2X13 + 2X23 + 7X24 + 4X32 + 9X34 + 6X35 + 1X46 + 5X47 +
2X54 + 4X56 + 3X57 + 2X58 + 1X67 + 5X69 + 4X76 + 3X78 + 5X79 + 2X87 +
7X89
INGRESANDO LOS DATOS A WINQSB
SOLUCIÓN OBTENIDA MEDIANTE WINQSB
La ruta más corta para rescatar al minero tiene como distancia
total 1600 metros (dado que las distancias estaban dadas en cientos de
metros) y es tal como se muestra en la siguiente
gráfica.
Sin embargo, WinQSB cuenta con una metodología mucho más sencilla de
resolución de algoritmos de ruta más corta, metodología que
explicaremos más adelante, de todas formas hemos encontrado cómo,
aplicando debidamente la razón y un algoritmo conocido como el de
transbordo, podemos solucionar problemas distintos en teoría.
No hay comentarios.:
Publicar un comentario