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.
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".
X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2 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).
El problema de asignación consiste en encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a productos, de vendedores a territorios, de postores a contratos, etc. Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende maximizar cierta cantidad.
Formalmente, el problema de la asignación consiste en encontrar un emparejamiento de peso óptimo en un grafo bipartitoponderado. El problema de asignación es un caso particular del problema de transporte, en el que la oferta en cada origen y la demanda en cada destino son ambas de valor.
ejercicios de problemas de transporte
miércoles, 26 de septiembre de 2018
Método vogel
El método de Vogel, o aproximación de Vogel, es un método que permite llegar a una solución inicial factible del problema de transporte.
El procedimiento de este método es el siguiente:
Tener los valores de costos de envíos desde cada origen a cada destino tabulados (matriz de costos). En caso de que la matriz no este equilibrada (el numero de filas es diferentes del numero de columnas), agregar una fila o columna de ceros según corresponda. Esto quiere decir que según sea el caso se creara un origen o un destino ficticio.
Realizar el cálculo de las penalizaciones para cada fila y columna. Las penalizaciones se calculan restando los dos valores más pequeños de cada fila y cada columna. Las penalizaciones tienen valor absoluto.
Identificar la fila o columna con la mayor penalización (en caso de que exista un empate en las penalizaciones, se puede elegir cualquiera de las que tiene el mayor valor), y asignar la mayor cantidad de material posible a la casilla con el menor costo en esa fila o columna.
Se sombrean (eliminan) las filas o columnas que hayan sido satisfechas, reduciendo así la matriz.
Se repite el procedimiento desde en paso 2.
Una vez satisfechos todos los orígenes y destinos (sombreadas todas las filas y columnas) se puede proceder a calcular el costo del programa de envió encontrado mediante este método (cabe resaltar que la solución factible encontrada con este método no es necesariamente la optima).
