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