Excel para solucionar el problema de la ruta más corta en redes

El problema de la ruta más corta

Excel Easy


Formular el modelo | Prueba y error | Resuelve el modelo

Utilice el solucionador en Excel para encontrar la ruta más corta desde el nodo S al nodo T en una red no dirigida. Los puntos en una red se llaman nodos (S, A, B, C, D, E y T). Las líneas en una red se llaman arcos (SA, SB, SC, AC, etc.).

Formular el modelo

El modelo que vamos a resolver se ve de la siguiente manera en Excel.

Problema de ruta más corta en Excel

1. Para formular este problema de ruta más corta, responda las siguientes tres preguntas.

a. ¿Cuáles son las decisiones que se tomarán? Para este problema, necesitamos Excel para saber si un arco está en la ruta más corta o no (Sí = 1, No = 0). Por ejemplo, si SB es parte de la ruta más corta, la celda F5 es igual a 1. De lo contrario, la celda F5 es igual a 0.

b. ¿Cuáles son las limitaciones de estas decisiones? El flujo neto (salida de flujo - entrada de flujo) de cada nodo debe ser igual a Suministro / Demanda. El nodo S solo debe tener un arco de salida (flujo neto = 1). El nodo T solo debería tener un arco entrante (flujo neto = -1). Todos los otros nodos deben tener un arco de salida y un arco de entrada si el nodo está en la ruta más corta (Flujo neto = 0) o no tiene flujo (Flujo neto = 0).

c. ¿Cuál es la medida general de rendimiento para estas decisiones? La medida general de rendimiento es la distancia total de la ruta más corta, por lo que el objetivo es minimizar esta cantidad.

2. Para que el modelo sea más fácil de entender, nombre los siguientes rangos.

Nombre del rango	Celdas
From	B4:B21
To	C4:C21
Distance	D4:D21
Go	F4:F21
NetFlow	I4:I10
SupplyDemand	K4:K10
Total Distancia	F23

3. Inserta las siguientes funciones.



Explicación: Las funciones SUMAR.SI calculan el flujo neto de cada nodo. Para el nodo S, la función SUMAR SUMA los valores en la columna Ir con una "S" en la columna De. Como resultado, solo las celdas F4, F5 o F6 pueden ser 1 (un arco de salida). Para el nodo T, la función SUMAR SUMA los valores en la columna Ir con una "T" en la columna Para. Como resultado, solo las celdas F15, F18 o F21 pueden ser 1 (un arco entrante). Para todos los demás nodos, Excel busca en la columna Desde y Hasta. La distancia total es igual al subproducto de Distance y Go.

Prueba y error

Con esta formulación, resulta fácil analizar cualquier solución de prueba.

1. Por ejemplo, el camino SBET tiene una distancia total de 16.



No es necesario usar prueba y error. A continuación describiremos cómo se puede usar Excel Solver para encontrar rápidamente la solución óptima.

Resuelve el modelo

Para encontrar la solución óptima, ejecute los siguientes pasos.

1. En la pestaña Datos, en el grupo Analizar, haga clic en Solucionar.



Nota: no puede encontrar el botón Solver? Haga clic aquí para cargar el complemento Solver.

Ingrese los parámetros del solucionador (sigue leyendo). El resultado debe ser consistente con la imagen de abajo.



Tiene la opción de escribir los nombres de rango o hacer clic en las celdas de la hoja de cálculo.

2. Ingrese TotalDistance para el objetivo.

3. Haga clic en Min.

4. Ingrese Ir para cambiar las celdas variables.

5. Haga clic en Agregar para ingresar la siguiente restricción.



6. Marque 'Hacer que las variables no restringidas sean no negativas' y seleccione 'Simplex LP'.

7. Finalmente, haz clic en Resolver.

Resultado:



La solución óptima:



Conclusión: SADCT es el camino más corto con una distancia total de 11.