xcel Fácil
Utilice el solucionador en Excel para encontrar el flujo máximo desde el 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 denominan arcos (SA, SB, SC, AC, etc.).
El modelo que vamos a resolver tiene el siguiente aspecto en Excel.
1. Para formular este problema de flujo máximo , responda las siguientes tres preguntas.
una. ¿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.
B. ¿Cuáles son las limitaciones de estas decisiones? El flujo neto (flujo de salida - flujo de entrada) del nodo A, B, C, D y E debe ser igual a 0. En otras palabras, flujo de salida = flujo de entrada. 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 de desempeño para estas decisiones? La medida general de rendimiento es el caudal 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 facilitar la comprensión del modelo, cree los siguientes rangos con nombre .
| Nombre de rango | Células |
|---|---|
| Desde | B4: B15 |
| Para | C4: C15 |
| Flujo | D4: D15 |
| Capacidad | F4: F15 |
| OfertaDemanda | 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 de salida). La segunda función SUMIF suma los valores de la columna Flujo con una "A" en la columna A (Flujo entrante). El flujo máximo es igual al valor de la celda I4, que es el flujo de salida del nodo S. Dado 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.
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 se puede utilizar Excel Solver para encontrar rápidamente la solución óptima.
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 .
Ingrese los parámetros del solucionador (siga leyendo). El resultado debe ser coherente con la imagen siguiente.
Tiene la opción de escribir los nombres de los rangos 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 que las variables no restringidas no sean negativas' y seleccione 'LP simplex'.
8. Por último, haga clic en Resolver.
Resultado:
La solución óptima:
Conclusión: la ruta 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. Estos caminos dan un flujo máximo de 12.
5/7 Completado! Obtenga más información sobre el solucionador>
Siguiente capítulo: Herramientas de análisis