Modelos Lineales de Optimización

FLUJO MÁXIMO DE REDES

Definición y aplicaciones según Ing. José Luis Albornoz Salazar. OPTIMIZACIÓN DE REDES. Páginas 23-24.

" En términos generales, un problema de flujo máximo de red se puede describir como:

1) Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.

2) Los nodos restantes son nodos de trasbordo.

3) Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco (flecha). En la fuente, todos los arcos (flechas) señalan hacia afuera. En el destino, todos señalan hacia el nodo.

4) El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.

Algunas aplicaciones

1) Maximizar el flujo a través de la red de distribución de la compañía de sus fábricas a sus clientes.

2) Maximizar el flujo a través de la red de suministros de la compañía de los proveedores a las fábricas.

3) Maximizar el flujo de petróleo por un sistema de tuberías.

4) Maximizar el flujo de agua a través de un sistema de acueductos.

5) Maximizar el flujo de vehículos por una red de transporte.

Para algunas de estas aplicaciones, el flujo a través de la red se puede originar en más de un nodo y también puede terminar en más de un nodo, aunque el problema de flujo máximo puede tener sólo un origen y un destino.

Por ejemplo, una red de distribución de una compañía tiene varias fábricas y múltiples clientes. Se usa una reformulación ingeniosa para ajustar esta situación al problema de flujo máximo. Se trata de aumentar la red original para que incluya una fuente ficticia, un destino ficticio y algunos arcos o flechas nuevos. La fuente ficticia se maneja como el nodo que da origen a todo el flujo que en realidad se origina en algunos otros nodos. Para cada uno de estos otros nodos, se inserta un nuevo arco que va de la fuente ficticia a este nodo, donde la capacidad del arco es igual al flujo máximo que se puede originar en este nodo. De manera similar, el destino ficticio se trata como el nodo que absorbe todo el flujo que, en realidad, termina en algún otro nodo. Por lo tanto, se coloca un nuevo arco desde cada uno de los otros nodos al destino ficticio con capacidad igual al flujo máximo que en realidad termina en este nodo. Debido a estos cambios, todos los nodos de la red original ahora son nodos de trasbordo para que la red aumentada tenga un solo origen (la fuente ficticia) y un solo destino (el destino ficticio) y se ajuste al problema del flujo máximo. "

EJEMPLO:

El ejemplo que se presenta es similar al del Ing. José Luis Albornoz Salazar. OPTIMIZACIÓN DE REDES. Páginas 24-32.

La figura siguiente muestra el sistema de bombeo de aguas blancas desde el Origen “O” hasta el Destino “D”; los otros nodos representan las ciudades intermedias que poseen estaciones de bombeo; las flechas representan las tuberías que conducen el agua desde una ciudad hasta otra (en un solo sentido); y los números representan el flujo o caudal máximo (en litros/seg) que se puede trasladar por cada tubería.

Se desea determinar la cantidad máxima de agua (en litros/seg) que puede recibir el nodo “D” utilizando las tuberías y bombas existentes.

SOLUCIÓN:

A continuación se orienta sobre la utilización de la hoja de cálculo EXCEL para la solución de este tipo de problemas de Flujo Máximo con la herramienta Solver, que posee el software.

Para poder usar Solver, primero es necesario que se vacíen los datos en una hoja de cálculo de la siguiente forma:

En la columna Condición (I) coloque ceros al lado de las ciudades intermedias (condición de las estaciones de trasbordo). No se coloca ningún valor al lado del Origen “O” ni del Destino “D” porque esos valores son justamente los buscados (el máximo positivo que sale del origen y el máximo negativo que entra al destino final).

Cada cero en las estaciones de trasbordo se refiere al hecho de que en dichas ciudades no se puede almacenar agua, es decir, se tiene que enviar la misma cantidad que se reciba:

Flujo neto = Flujo de salida - Flujo de entrada

es decir, Flujo neto = cero

Todas las celdas están llenas con la información tal y cómo se muestra en la imagen anterior, excepto por la columna de Flujo Neto (L) y la celda correspondiente a Flujo Máximo (L16), las cuales contienen ecuaciones.

Las ecuaciones para los flujos netos de cada “nodo” o ciudad se incluirán en la columna L, en donde cada celda de esta columna (L) calcula el flujo neto real en ese nodo sumando el flujo que sale y restando el que entra.

Conociendo la ecuación que debemos incluir en las celdas “L4” hasta “L10” tomamos en cuenta las siguientes consideraciones, tomadas parcialmente del libro citado al principio de este artículo:

· Como las celdas de la columna E reflejarán los resultados (Flujo que debe enviarse por esa ruta), serán éstas las que se tomen en cuenta para la elaboración de las ecuaciones.

· Como el flujo neto generado en un nodo es el flujo que sale menos el flujo que entra, las ecuaciones se reducen a la suma y resta de los valores que debe reflejar SOLVER en las celdas de la columna E

· Las celdas de la columna E que se colocarán en las ecuaciones serán aquellas que se encuentren en la misma “Fila” donde esté ubicado el “nodo” estudiado. Si la letra que identifica al nodo se encuentra en la columna C (DESDE) se sumará; cuando se encuentre en la columna D (HASTA) se restará.

En la celda L5 se incluirá la ecuación relacionada con el Origen (“O”).

Notamos que la letra “O” se encuentra ubicada en las filas 5, 6 y 7, por lo tanto debo utilizar en la ecuación las celdas E5, E6 y E7.

En las filas 5, 6 y 7, podemos ver que existen tres rutas que incluyen a “O”, a saber:

O→A (Fila 5)

O→B (Fila 6)

O→C (Fila 7)

Como en los tres casos el flujo sale de “O” (La flecha empieza después de “O” y termina en ”A”,”B” ó “C”), en la ecuación se sumarán los tres valores:

Celda L5 = E5 + E6+ E7

En el resto de las celdas correspondientes a Flujo Neto quedarían con las siguientes ecuaciones:

Celda L6 = -E5+E8-E9

Celda L7 = -E6+E9+E10+E11-E12

Celda L8 = -E7+E12+E13

Celda L9 = -E8-E10+E14

Celda L10 = E11-E13-E14

En estas celdas se reflejarán inicialmente ceros hasta que apliquemos Solver.

La celda donde queremos que se refleje el flujo máximo que debe llegar hasta el destino “D”, o lo que es lo mismo el flujo máximo que debe salir del origen “O”. Como la celda L5 debe reflejar el flujo que sale de “O”, ese mismo valor será el flujo máximo que representará la función objetivo. En este caso, la celda destinada como la celda objetivo es E16 y en ella debemos incluir:

Celda E16 = L5

Una vez vaciada toda la información que tenemos en la hoja de cálculo, procedemos a ejecutar Solver, cuyo botón se encuentra en la pestaña Datos del programa. Al hacer clic se mostrará un cuadro de diálogo “Parámetros de Solver”.

Antes de que Solver pueda resolver el problema, necesita conocer con exactitud, donde se localizan los componentes del modelo en la hoja de cálculo. Es posible escribir las direcciones de las celdas o hacer clic en ellas.

Donde se solicita “Establecer objetivo” indique la celda E16. Coloque: $E$16

Donde se solicita “Cambiando las celdas de variables” indique las celdas donde se propuso anteriormente que se mostrarán los resultados. En este caso son las celdas E5 hasta E14, coloque: $E$5:$E$14

Indique las restricciones o condiciones del problema, para lo cual haga clic en “Agregar”. En este momento aparecerá en la pantalla el cuadro de diálogo “Agregar Restricción”.

En este problema existen dos restricciones:

La primera:

$E$5:$E$14 ≤ $G$G:$E$14

La segunda:

$J$6:$J$9 = $L$6:$L$9

Haga clic en “Aceptar”. Ahora el cuadro de diálogo resume el modelo completo.

Hacer clic en “Resolver” y después de unos segundos Solver indicará los resultados en las celdas E5 hasta E14, en la celda objetivo E16 aparecerá el FLUJO MAXIMO que sale del origen y llega al destino.

En el cuadro final “Resultados de Solver”, haga clic en “Aceptar”.