• Author / Uploaded
• AaronLopezR

Citation preview

LA RUTA MAS CORTA El método de la ruta más corta es un método de programación lineal, que permite buscar la solución a un problema de optimización que resulte de una combinatoria y de diferentes aplicaciones, el objetivo de este método esta en encontrar rutas cortas o de menor costo, según sea el caso, que va desde un nodo especifico hasta cada uno de los demás nodos de la red. En este sentido un nodo es una representación gráfica en forma de circulo, este nodo es muy importante ya que denota los orígenes y destinos del problema que se realice, asimismo una red representa un conjunto de puntos y líneas que conectan pares de puntos, estos puntos son los que llamaremos nodos y las líneas serían las aristas., por ejemplo:

 APLICACIONES: En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la vida práctica, dentro de las que podemos mencionar: 

Transporte.



Horarios de operadores telefónicos.



Planeación de tráfico urbano.



Trasbordo.



En las redes eléctricas.



Diseño de rutas de vehículos.



Telecomunicaciones.



Planeación de inventarios.



Planeación de producción, entre otros

 IMPORTANCIA. El problema de la Ruta más Corta es fundamental en muchas áreas, como son: investigación de operaciones, ciencia de la computación e ingeniería. Algunas de las razones son:

I. La amplia variedad de aplicaciones prácticas como es el envío de algún material entre dos puntos específicos de la forma más eficiente, económica o rápida.

II. Existen métodos de solución eficientes, los cuales al ser aplicados a una red con características específicas (a cíclica y con costos no negativos), proveen una solución exacta a un tiempo y costo razonables.

III. Se puede utilizar como inicio en el estudio de modelos complejos de redes, esto es, cuando no se conoce la estructura de la red se pueden aplicar algoritmos para conocer algunas características de la red (presencia de ciclos negativos).

IV. Se utiliza frecuentemente como sub-problemas (subrutinas) en la solución de problemas combinatorios y redes, así en el caso de problemas para los cuales no existe un algoritmo de solución exacto (p. e. problemas NP-completos), la aplicación de algoritmos de ruta más corta, resultan auxiliares para encontrar una buena solución.  EJERCICIOS DE MINERÍA.

1.- Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir de la

bocamina principal (nodo1) a la galería 49 (nodo 8) de la mina “La Viesca”.

El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son: 

Ruta 1-2-5-7-8: 4+8+17+9 = 38[km]



Ruta 1-3-4-7-8: 3+12+20+9 = 44[km]



Ruta 1-3-4-6-8: 3+12+2+22 = 39[km]



Ruta 1-3-4-8: 3+12+15 = 30[km]



Ruta 1-3-6-8: 3+4+22 = 29[km]

La ruta o camino más corto está dada por la secuencia 1-3-6-8 con una distancia total de 29[km].

A continuación se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:

Variables de Decisión:

Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:

Restricciones:



La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1.



La restricción (2) determina que si se visitó el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2.



La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos).



La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.



La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodos: 7, 8 o 6.



La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8.



La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8.



Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.

2.- Se tiene la red de ruta de la figura 1. Suponer que se desea determinar la ruta más corta del nodo 1 al nodo 2; esto es, s = 1 y t = 2. La figura 1 muestra como entra el flujo unitario en el nodo 1 y sale en el nodo 2.

Figura 1: Inserción de un flujo unitario para determinar la ruta más corta entre el nodo s = 1 y t = 2. El número junto a cada camino corresponde a su largo respectivo. La lista del programa lineal asociado, usando la formulación 1, se ve a continuación:

Las restricciones representan la conservación de flujo en cada nodo. Por ejemplo, en el nodo 2 “flujo que entra = flujo que sale” es x12 + x42 = 1 + x23. Nótese que una de las restricciones siempre es redundante. Por ejemplo, si se suman las últimas cuatro restricciones en forma simultanea se obtiene x12+x13 = 1, que es igual que la restricción 1.

La solución ´optima es z = 55, x13 = 1, x34 = 1, x42 = 1. Esta solución expresa la ruta más corta del nodo 1 al nodo 2 como 1→3→4→2, y la distancia asociada es z = 55 (millas).