Formular el modelo | Prueba y error | Resolver el modelo
Utilice el solucionador de Excel para encontrar el flujo máximo del nodo S al nodo T en una red 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 de flujo máximo , responda a las siguientes tres preguntas.
a. ¿Cuáles son las decisiones a tomar? Para este problema, necesitamos que Excel encuentre el flujo en cada arco. Por ejemplo, si el flujo en el SB es 2, la celda D5 es igual a 2.
b. ¿Cuáles son las limitaciones de estas decisiones? El flujo neto (Flow Out – Flow In) del nodo A, B, C, D y E debe ser igual a 0. En otras palabras, Flow Out = Flow In. Además, cada arco tiene una capacidad fija. El flujo en cada arco debe ser menor que esta capacidad.
c. ¿Cuál es la medida general del rendimiento de estas decisiones? La medida global de rendimiento es el flujo máximo, por lo que el objetivo es maximizar esta cantidad. El flujo máximo es igual al flujo de salida del nodo S.
2. Para que el modelo sea más fácil de entender, nombra los siguientes rangos.
Nombre de la gama Células De B4:B15 A C4:C15 Flujo D4:D15 Capacidad F4:F15 Oferta-Demanda K5:K9 MaximumFlow D17
3. Inserte las siguientes funciones.
Explicación: Las funciones SUMIF calculan el flujo neto de cada nodo. Para el nodo A, la primera función SUMIF suma los valores de la columna Flujo con una «A» en la columna Desde (Flujo hacia afuera). La segunda función SUMIF suma los valores de la columna de Flujo con una «A» en la columna To (Flujo de Entrada). El Flujo Máximo es igual al valor de la celda I4, que es el flujo de salida del nodo S. Debido a que los nodos A, B, C, D y E tienen un Flujo Neto de 0, el Flujo de Salida del nodo S será igual al Flujo de Entrada del nodo T.
Prueba y error
Con esta formulación, se hace fácil analizar cualquier solución de prueba.
1. Por ejemplo, el camino SADT con un flujo de 2. El camino SCT con un flujo de 4. El camino SBET con un flujo de 2. Estos caminos dan un flujo total de 8.
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 el flujo máximo para el objetivo.
3. Haga clic en Max.
4. Introduzca el flujo para las celdas variables cambiantes.
5. 5. Haga clic en Agregar para introducir la siguiente restricción.
6. 6. Haga clic en Agregar para introducir la siguiente restricción.
7. Marque ‘Make Unconstrained Variables Non-Negative’ y seleccione ‘Simplex LP’.
8. Por último, haga clic en Resolver.
Resultado:
La solución óptima:
Conclusión: el sendero SADT con un flujo de 2. El sendero SCT con un flujo de 4. El sendero SBET con un flujo de 2. El sendero SCET con un flujo de 2. El sendero SACET con un flujo de 1. El sendero SACDT con un flujo de 1. Estos senderos dan un flujo máximo de 12.