Formular el modelo | Prueba y error | Resolver el modelo
Utilice el solucionador de Excel para encontrar el camino más corto del nodo S al nodo T en una red no dirigida. Los puntos de una red se denominan nodos (S, A, B, C, D, E y T). Las líneas de una red se llaman arcos (SA, SB, SC, AC, etc.).
Glosario
Formular el modelo
El modelo que vamos a resolver se ve como sigue en Excel.
1. Para formular este problema del camino más corto , responda a las siguientes tres preguntas.
a. ¿Cuáles son las decisiones a tomar? Para este problema, necesitamos que Excel averigüe si un arco está en el camino más corto o no (Sí=1, No=0). Por ejemplo, si SB es parte del camino más corto, la celda F5 es igual a 1. Si no, la celda F5 es igual a 0.
b. ¿Cuáles son las limitaciones de estas decisiones? El flujo neto (flujo de salida – flujo de entrada) de cada nodo debe ser igual a la oferta y la demanda. El nodo S sólo debe tener un arco de salida (Flujo neto = 1). El nodo T sólo debe tener un arco de entrada (Flujo neto = -1). Todos los demás nodos deben tener un arco saliente y uno entrante si el nodo está en el camino más corto (Flujo neto = 0) o no hay flujo (Flujo neto = 0).
c. ¿Cuál es la medida general del rendimiento de estas decisiones? La medida general de rendimiento es la distancia total del camino más corto, por lo que el objetivo es minimizar esta cantidad.
2. Para que el modelo sea más fácil de entender, nombra los siguientes rangos.
Nombre de la gama Células De B4:B21 A C4:C21 Distancia D4:D21 Vaya a F4:F21 NetFlow I4:I10 Oferta-Demanda K4:K10 TotalDistance F23
3. Inserte las siguientes funciones.
Explicación: Las funciones SUMIF calculan el flujo neto de cada nodo. Para el nodo S, la función SUMIF suma los valores de la columna Go con una «S» en la columna From. Como resultado, sólo la celda F4, F5 o F6 puede ser 1 (un arco saliente). Para el nodo T, la función SUMIF suma los valores de la columna Go con una «T» en la columna To. Como resultado, sólo la celda F15, F18 o F21 puede ser 1 (un arco de entrada). Para todos los demás nodos, Excel mira en la columna Desde y Hasta. Distancia Total es igual al producto de la suma de Distancia e Ir.
Prueba y error
Con esta formulación, se hace fácil analizar cualquier solución de prueba.
1. Por ejemplo, el camino SBET tiene una distancia total de 16.
No es necesario utilizar el método de ensayo y error. A continuación describiremos cómo se puede utilizar el Excel Solver para encontrar rápidamente la solución óptima.
Resolver 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 Resolver.
Nota: ¿no encuentras el botón del Solver? Haga clic aquí para cargar el complemento de Solver.
Introduzca los parámetros del solucionador (siga leyendo). El resultado debe ser consistente con la imagen de abajo.
Tienes la opción de escribir los nombres de los rangos o hacer clic en las celdas de la hoja de cálculo.
2. Introduzca la distancia total para el objetivo.
3. Haga clic en Min.
4. Introduzca «Go» para las celdas variables cambiantes.
5. 5. Haga clic en Agregar para introducir la siguiente restricción.
6. Marque ‘Make Unconstrained Variables Non-Negative’ y seleccione ‘Simplex LP’.
7. Por último, haga clic en Resolver.
Resultado:
La solución óptima:
Conclusión: SADCT es el camino más corto con una distancia total de 11.