Problema de flujo máximo

Formular el modelo | Prueba y error | Resolver el modelo

Utilice el solucionador en 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 denominan arcos (SA, SB, SC, AC, etc.).

Formular el modelo

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.

a. ¿Cuáles son las decisiones que se deben tomar? Para este problema, necesitamos Excel para encontrar el flujo en cada arco. Por ejemplo, si el flujo en la CCI 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) 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.

c. ¿Cuál es la medida general de desempeño para estas 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 Para C4:C15 Flujo D4:D15 Capacidad F4:F15 OfertaDemanda 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 de la columna Flujo con una “A” en la columna De (Salida). La segunda función SUMIF suma los valores de la columna Flujo con una “A” en la columna Para (Flow In). 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 que sale del nodo S es 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 ficha Datos, en el grupo Analizar, haga clic en Solucionador.

Nota: ¿no encuentra 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.

Puede elegir entre 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. Introducir movimiento para modificar celdas variables.

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

6. Haga clic en Agregar para introducir la siguiente restricción.

7. Marque’Make Unconstrained Variables Non-Negative’ y seleccione’Simplex LP’.

8. Finalmente, haga clic en Resolver.

Resultado

La solución óptima:

Conclusión: el camino SADT con un flujo de 2. El camino SCT con un flujo de 4. El camino SBET con un flujo de 2. El camino SCET con un flujo de 2. El camino SACET con un flujo de 1. El camino SACDT con un flujo de 1. Estos caminos dan un flujo máximo de 12.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *