Problemas Ecológicos Resueltos a Través de Análisis de Redes. Problemas de Flujo Máximo

1. Resumen
3. Desarrollo
4. Algoritmo de la trayectoria de aumento para el problema del flujo máximo
5. Ejemplo Propuesto
6. Conclusiones
7. Materiales y Métodos
8. Bibliografía y Referencias

Resumen

Apoyado en el análisis de redes como una técnica de modelación matemática se muestra una forma que no por ser muy simple deja de ser muy sumamente útil para resolver problemas ecológicos de flujo máximo como el que se expone. Se hace uso de un ejemplo hipotético que nos llevará a conocer el uso de la técnica de una forma muy fácil y compresible. Se debe decir que esta ha sido aplicada en problemas prácticos con excelentes resultados.

Introducción:

Problema:

El Parque "Cristóbal Colón" tiene la misión de crear y comercializar los productos turísticos extrahoteleros sobre la base de conservación, recuperación, enriquecimiento y uso sostenible de los recursos naturales, históricos y socioculturales en el polo turístico de Holguín. Sin embargo, existe una gran preocupación en la explotación del Sendero Ecológico "Las Guanas" en temporada pico, puesto la gran fluidez de turistas por la red de sus senderos puede traer cierto desequilibrio en la vida silvestre y autóctona del lugar. Por tal razón se ha impuesto restricciones estrictas en el número de excursiones que fluyen por sus senderos en busca de sus disímiles atracciones, estas restricciones difieren de una ruta del sendero a otra. Así durante las excursiones se pueden tomar rutas diferentes por donde podrán disfrutar de las peculiaridades del ecosistema y al finalizar la excursión los guías conducirán a los visitantes a un restauran donde podrán disfrutar de un almuerzo tradicional cubano.

Ahora, como podríamos planear las rutas para los diferentes grupos de excursiones de manera que se maximice el número total de excursiones que se pueden hacer al día sin violar los límites impuestos en cada ruta?. La respuesta a este problema la veremos en los resultados de este trabajo.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Figura 1. Sendero Ecológico "Las Guanas"

• E: Entrada
• I : Representación aborigen
• A: Museo Arqueológico
• B: Bohío campesino B: Bohío campesino
• M: Mirador
• T : Trapiche azucarero
• O: Restos arquelójicos
• Z: Minizoológico de fauna autóctona
• R: Restauran

Desarrollo:

Como podemos apreciar estamos delante de un problema de flujo máximo y para adentrarnos en él, es necesario hacer referencia a un aspecto que es su razón de ser, me refiero al Análisis de Redes. Los problemas de Redes surgen en una gran variedad de situaciones, por ejemplo en redes de transporte, redes eléctricas, y de comunicaciones, por citar algunos ejemplos.

Al analizar cada uno de estos ejemplos podemos distinguir características que como en el caso del Sendero Ecológico "Las Guanas" los identifica como redes, es decir: cada uno está formado por un conjunto de puntos o estaciones (E, B, I, A, etc.) y un conjunto líneas que unen ciertos pares de puntos. Que en el caso de este parque serían los caminos que unen cada estación

Los puntos se llaman nodos (o vértices).

Las líneas se llaman arcos (o ligaduras, aristas o ramas)

Los arcos se etiquetan dando nombre a los nodos en sus puntos terminales; por ejemplo EA es el arco entre los nodos E yA de la figura 1

Los arcos de una red pueden tener un flujo de algún tipo que pasa por ellos, por ejemplo, los grupos de excursiones sobre los caminos del sendero, información en los cables coaxiales de una línea telefónica, etc.

Si el flujo a través de un arco solo se permite en una dirección (como en las calles de un solo sentido), se dice que el arco es un arco dirigido. La dirección se indica con una cabeza de flecha al final de la línea que representa el arco.

Si el flujo se permite en ambas direcciones (como en una tubería que se puede bombear el fluido en ambas direcciones) se dice que es un arco no dirigido o ligadura.

Este caso donde el problema será determinar durante la temporada pico el número de algunas excursiones por rutas desde la entrada al sendero (estación E) al restauran (estación R) de manera que se maximice el número total de excursiones que se puedan hacer al día sin violar las limitaciones impuestas o límites superiores estrictos sobre el número de excursiones permitidos para cada camino individual en la dirección del nodo fuente (el nodo E ) y el nodo destino (el nodo R), donde el resto son nodos de trasbordo.

El número que aparece en la base de la flecha da el límite superior para ese camino en la dirección de salida de la estación.

Nuestro objetivo es determinar el patrón factible de flujos a través de la red que maximiza el flujo total, desde el nodo fuente hasta el nodo destino.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método símplex. En este caso dispondremos de un algoritmo de trayectorias aumentadas mucho más eficiente.

Este algoritmo se basa en dos conceptos intuitivos,

• El de una red residual
• El de una trayectoria aumentada.

Una ves que se han asignado flujos a los arcos de la red original, la red residual muestra las capacidades restantes (llamadas capacidades residuales) para asignar flujos adicionales. Por ejemplo consideramos el arco E →A en la figura anterior, que tiene una capacidad de arco de 90. Ahora suponga que los flujos asignados incluyen un flujo de 60 a través de este arco, lo que deja una capacidad residual 90-60=30 para cualquier asignación de flujo adicional a través de E →A. este estado se describe en la red de la siguiente manera:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

El número sobre el arco junto a un nodo da la capacidad residual para el flujo desde ese nodo hasta el otro. Por lo tanto, además de la capacidad residual de 30 para el flujo de E a A, el 60 de la derecha indica una capacidad residual de 60 para asignar un flujo desde A hasta E (es decir, para cancelar algún flujo previamente asignado de E a A).

En principio, antes de asignar cualquier flujo, la red residual tiene la apariencia mostrada en la figura 3

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Figura 3.

Cada arco en la red original (Fig.2) se cambió de un arco dirigido a un arco no dirigido. No obstante, las capacidades en la dirección original son las mismas y las capacidades en la dirección opuesta son cero. De manera que las restricciones sobre los flujos no cambian.

Subsecuentemente, siempre que se asigne alguna cantidad de flujo a un arco, esa cantidad se resta de la capacidad residual en la misma dirección y se suma a la capacidad residual en la dirección opuesta.

Una trayectoria de aumento es una trayectoria dirigida del nodo fuente al nodo destino en la red residual, tal que todos los arcos en esta trayectoria tienen la capacidad residual estrictamente positiva. El mínimo de estas capacidades residuales se llama capacidad residual de la trayectoria de aumento porque representa la cantidad de flujo que es factible agregar en toda la trayectoria. Por tanto, cada trayectoria de aumento proporciona una oportunidad de aumentar más el flujo a través de la red original.

El algoritmo de la trayectoria de aumento selecciona repetidamente alguna trayectoria de aumento y agrega un flujo igual a la capacidad residual de esa trayectoria en la red original. Este proceso continúa hasta que ya no hay trayectorias de aumento, con lo que el flujo del nodo fuente al nodo destino no puede crecer. La clave para asegurar que la solución final es necesariamente óptima es el hecho de que las trayectorias de aumento pueden cancelar flujos asignados con anterioridad en la red original; así, una selección indiscriminada de trayectorias para asignar flujos no puede evitar el uso de una combinación mejor de asignaciones de flujos.

Para resumir, cada iteración del algoritmo consiste en los tres pasos siguientes:

Algoritmo de la trayectoria de aumento para el problema del flujo máximo.

1. Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del nodo de origen al nodo destino en la red residual tal que cada arco sobre esta trayectoria tiene la capacidad residual estrictamente positiva. (Si no existe una, los flujos netos ya asignados constituyen un patrón de flujo óptimo.)
2. Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.
3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa al paso 1.

Al realizar el paso 1, con frecuencia habrá varias alternativas de trayectorias de aumento entre las cuales se podrá escoger. Aunque la estrategia algorítmica para elegir es importante para la eficiencia en las aplicaciones a gran escala, no se profundizará en este tema relativamente especializado. (más adelante se describe un procedimiento sistemático para encontrar una trayectoria aumentada.) Entonces, para el siguiente ejemplo la selección se hará de forma arbitraria.

Ejemplo Propuesto.

Viendo la red original (Fig.2) y comenzando con la red residual inicial dada en la Fig.3, se da la nueva red residual después de una o dos iteraciones, donde la cantidad total de flujo de E a R logrado hasta el momento

Iteración 1:

En la figura 2, una de las trayectorias de aumento es E→B→Z→R que tiene la capacidad residual igual {80, 40, 60} = 40. Si se asigna un flujo de 40 a esta trayectoria, la red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Iteración 2: Se asigna un flujo de 60 a la trayectoria de aumento E→A→Z→R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Iteración 3: se asigna un flujo de 25 a la trayectoria de aumento E→B→M→R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Iteración 4: Se asigna un flujo de 35 a la trayectoria de aumento E→B→T→R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Iteración 5: Se asigna un flujo de 20 a la trayectoria de aumento E→B→T→O→R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Iteración 6: Se asigna un flujo de 30 a la trayectoria de aumento E→I→T→R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Iteración 7: Se asigna un flujo de 30 a la trayectoria de aumento E→I→0 →R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Iteración 8: Se asigna un flujo de 45 a la trayectoria de aumento E→I→T →R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Iteración 9: Se asigna un flujo de 45 a la trayectoria de aumento E→I→M →R. La red residual que resulta es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Como podemos ver no existen trayectorias de aumento por lo que el patrón de flujo actual es óptimo.

Solución del Problema:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

También hemos resuelto este problema haciendo uso del paquete matemático WindQSB. Primeramente, luego de activar la opción de flujo máximo, entrar el nombre del problema y la cantidad de nodos a analizar, entramos los datos en la tabla que a continuación se muestra, luego hicimos correr el programa y obtuvimos los siguientes resultados:

Maximal Flow Problem Sendero Ecológico "Las Guanas"

Solution for Maximal Flow Problem Sendero Ecológico "Las Guanas"

Graphic Solution for Maximal Flow Problem Sendero Ecológico "Las Guanas"

Final Solution: Objetive Value=330

Conclusiones:

Como hemos podido apreciar los resultados del ejercicio por ambos métodos son los mismos por lo que hemos comprobado la garantía de ambos en la solución de problemas de flujo máximo. Comprobamos además que aunque los problemas de flujo máximo se pueden formular como problemas de programación lineal y se puedan resolver con el método simplex , la solución por el algoritmo de trayectorias aumentadas es mucho mas fácil y eficiente, solo basta tomar lápiz y hojas y manos a la obra, claro, que si se cuenta con un paquete como el que hemos utilizado en este ejercicio nos ahorraremos un inmenso tiempo y trabajo. Nos pareció interesante como los problemas de redes surgen en una gran variedad de situaciones y como una representación de las mismas nos proporciona un panorama general tan poderoso y una ayuda conceptual para visualizar las relaciones entre las componentes de los sistemas que se usa en casi todas las áreas científicas, sociales y económicas. Ahora podemos contar con una herramienta más que sin duda nos serán de gran utilidad en nuestra vida profesional.

Materiales y Métodos

Análisis de Redes.Metodo de Flujo Máximo.

-Algoritmo de la trayectoria de aumento.

-WindQSB.Flujo Máximo

Bibliografía y Referencias

Pedro Sánchez. Colección de Artículos, Universidad de Holguín, Cuba, 2003

Autor

Roberto Pinto O´Reilly

Estudiante de 5to año de Ingeniería Industrial de la Universidad de Holguín, Cuba.

Curso 2004-2005