Problema de flujo máximo en Excel
Formular el modelo | Prueba y error | Resolver el modelo
Usa el solucionador en Sobresalir para encontrar el flujo máximo del nodo S al nodo T en una red 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 como sigue en Excel.
1. Para formular esto. problema de flujo máximo, contesta las siguientes tres preguntas.
a. ¿Cuáles son las decisiones a tomar? Para este problema, necesitamos Excel para encontrar el flujo en cada arco. Por ejemplo, si el flujo en SB es 2, la celda D5 es igual a 2.
segundo. ¿Cuáles son las limitaciones de estas decisiones? El flujo neto (Flow Out - Flow In) de los nodos 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.
do. ¿Cuál es la medida general de rendimiento paraestas decisiones? La medida general del 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, nombre los siguientes rangos.
| Nombre del rango | Células |
|---|---|
| Desde | B4: B15 |
| A | C4: C15 |
| Fluir | D4: D15 |
| Capacidad | F4: F15 |
| SupplyDemand | K5: K9 |
| Flujo máximo | 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 en la columna de Flujo con una "A" en la columna De (Flujo de Salida). La segunda función SUMIF suma los valores en la columna Flujo con una "A" en la columna A (Flujo en). El flujo máximo es igual al valor en la celda I4, que es el flujo que sale del nodo S. Debido a que los nodos A, B, C, D y E tienen un flujo neto de 0, el flujo fuera del nodo S será igual al flujo de entrada del nodo T.
Prueba y error
Con esta formulación, resulta fácil analizar cualquier solución de prueba.
1. Por ejemplo, la ruta SADT con un flujo de 2. La ruta SCT con un flujo de 4. La ruta SBET con un flujo de 2. Estas rutas dan un flujo total de 8.
No es necesario utilizar prueba y error. A continuación describiremos cómo el Solucionador de Excel Se puede utilizar 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 Solver.
Nota: ¿no puede encontrar el botón Solver? Haga clic aquí para cargar el complemento Solver.
Introduzca los parámetros del solucionador (siga 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 MaximumFlow para el objetivo.
3. Haga clic en Max.
4. Ingrese el flujo para las celdas variables cambiantes.
5. Haga clic en Agregar para ingresar la siguiente restricción.
6. Haga clic en Agregar para ingresar la siguiente restricción.
7. Marque "Hacer variables no restringidas no negativas" y seleccione "LP simplex".
8. Finalmente, haga clic en Resolver.
Resultado:
La solución óptima:
Conclusión: el camino SADT con un flujo de 2. La ruta SCT con un flujo de 4. La ruta SBET con un flujo de 2. La ruta SCET con un flujo de 2. La ruta SACET con un flujo de 1. La ruta SACDT con un flujo de 1. Estas rutas dan un máximo flujo de 12.
