Formule el modelo | Trial and Error | resolver el modelo

Utilizar el solucionador en Excel para encontrar el flujo máximo desde el nodo S al nodo T en una red dirigida. Puntos de una red se denominan nodos (S, A, B, C, D, E y T). Líneas en una red se llaman arcos (SA, SB, SC, AC, etc).

Formular el Modelo

El modelo que se va a resolver el siguiente aspecto en Excel.

Maximum Flow Problem in Excel

  1. Formular este problema de flujo máximo, responda a las siguientes tres preguntas.

\un. ¿Cuáles son las decisiones que se harán? Para este problema, necesitamos Excel para encontrar el flujo en cada arco. Por ejemplo, si el flujo en SB es 2, célula D5 es igual a 2.

\segundo. ¿Cuáles son las limitaciones de estas decisiones? El flujo neto (Flujo de salida – Flow In) de nodo A, B, C, D y E deben ser iguales a 0. En otras palabras, el flujo de salida = Flujo In. También, cada arco tiene una capacidad fija. El flujo en cada arco debe ser inferior a esta capacidad.

\C. ¿Cuál es la medida global de rendimiento para estas decisiones? La medida global de la actuación es el caudal máximo, por lo que el objetivo es maximizar esta cantidad. El caudal máximo es igual al flujo de salida del nodo S.

  1. Para hacer el modelo más fácil de entender, por nombrar los siguientes rangos.

Range Name

Cells

From

B4:B15

To

C4:C15

Flow

D4:D15

Capacity

F4:F15

SupplyDemand

K5:K9

MaximumFlow

D17

  1. Inserte las siguientes funciones.

Insert Functions

Explicación: El enlace: / ejemplos-función SUMIF [función SUMIF] funciones calcular el flujo neto de cada nodo. Para el nodo A, la primera función de cálculo SUMAR.SI suma los valores de la columna de flujo con una «A» en la columna De (Flujo de salida). La segunda función de cálculo SUMAR.SI suma los valores de la columna de flujo con una «A» en la columna A (Flow In). De flujo máxima es igual al valor en la celda I4, que es el flujo de nodo S. Debido a que el nodo A, B, C, D y E tienen un flujo neto de 0, Flujo de salida de nodo S será igual Flow En de T. nodo

Ensayo y error

Con esta formulación, se hace fácil para analizar cualquier solución de prueba.

  1. Por ejemplo, la SADT camino con un flujo de 2. El SCT camino con un flujo de 4. El SBET camino con un flujo de 2. Estas trayectorias de flujo givea total de 8.

Trial Solution

No es necesario el uso de ensayo y error. Vamos a describir a continuación cómo el Solver de Excel se puede utilizar para encontrar rápidamente la solución óptima.

resolver el modelo

Para encontrar la solución óptima, ejecutar los siguientes pasos.

  1. En la ficha Datos, en el grupo Analizar, haga clic en Solver.

Click Solver

Nota: no puede encontrar el botón Solver? Haga clic aquí para cargar el complemento Solver.

Introduzca los parámetros de Solver (leyendo). El resultado debe ser consistente con la imagen de abajo.

Solver Parameters

Usted tiene la opción de escribir los nombres de rango o haciendo clic en las celdas de la hoja de cálculo.

  1. Introduzca MaximumFlow para el objetivo.

  2. Haga clic en Max.

  3. Introduzca de flujo para las celdas variables cambiantes.

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

Net Flow Constraint

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

Capacity Constraint

  1. Comprobar ‘Make variables sin restricciones no negativo’ y seleccione ‘Simplex LP’.

  2. Por último, haga clic en Resolver.

Resultado:

Solver Results

La solución óptima:

Maximum Flow Problem Result

Conclusión: la SADT camino con un flujo de 2. El SCT camino con un flujo de 4. El SBET camino con un flujo de 2. El SCET camino con un flujo de 2. El Sacet camino con un flujo de 1. El SACDT camino con un flujo de 1. Estas trayectorias givea flujo máximo de 12.