ing civil


Instituto Tecnológico de La Paz
MODELO DE FLUJO DE REDES


Modelos de Optimización de Recursos

Prof. Ing. Guillermo Reyes Álvarez


Alumnos:
Pablo Aviles Cota
Fermín Humberto Avalos Martínez
Cesar Navarro Cisneros
Efrén Ernesto Espinoza Jaime

Modelo de flujo de redes
En investigación de operaciones se pueden resolver una multitud de situaciones por medio de un modelo y porredes o nodos, algunas encuestas recientes informan que hasta el 70% de los problemas de programación lineal se pueden expresar como modelos relacionados con redes.
Las principales aplicaciones posibles de las redes son:
-Minimizar el costo de construcción en alguna cosa.
-Determinar la ruta más corta entre 2 ciudades, carreteras, etc.
-Determinar la capacidad máxima que alguna cosa puedesoportar
-Determinar el programa de flujo con costo mínimo en distintos campos
-Determinar el cronograma de actividades en la construcción de un proyecto.
En este resumen mencionaremos 5 algoritmos de optimización de redes:
1- Árbol de expansión mínima (Situación 1)
2- Algoritmo a la ruta más corta (Situación 2)
3- Algoritmo del flujo máximo (Situación 3)
4- Algoritmo de red capacitada con costomínimo (Situación 4)
5- Algoritmo de la ruta crítica (Situación 5)
Una red consiste en una serie de nodos enlazados con arcos o ramas. La notación para describir una red es (N,A) donde N es el conjunto de nodos y A el conjunto de arcos.
Cada red se asocia a algún tipo de flujo, este flujo de la red está limitado por la capacidad de sus arcos que pueden ser finitos o infinitos. Se dice que unarco es dirigo u orientado si permite el flujo positivo en una dirección y flujo 0 en la dirección opuesta. Una red dirigida tiene todos sus arcos dirigidos.
Una ruta es una asociación de arcos que unen 2 nodos pasando por otros nodos, independientemente de la dirección de flujo a cada arco. Una ruta forma un ciclo si conecta un nodo consigo mismo pasando por otros nodos.
Una red conectada esaquella en que cada 2 nodos distintos están enlazados almenos por una ruta.
Un árbol es una red conectada que puede consistir solo en un subconjunto de todos los nodos en ella, donde no se permiten ciclos, y un árbol de expansión es un árbol que enlaza todos los nodos de la red también sin permitir ciclos.

1) Algoritmo del árbol de expansión minima.
Este algoritmo enlaza los nodos de una red, enforma directa o indirecta, con la minima longitud de las ramas enlazantes. Una aplicación características es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre 2 poblaciones puede pasar por 1 o mas poblaciones adicionales. El diseño mas económico del sistema de caminos indica que se minimiza la distancia total de caminos pavimentados, este es el resultadoque se obtiene implementando el algoritmo de expansión minima.
Los pasos de procedimiento de este algoritmo son los siguientes. Sea N=[1,2,…,n] el conjunto de nodos en la red y se definen:
Ck = Conjunto de nodos que se han conectado en forma permante en la iteración “k”,
k = Conjunto de nodos que todavía se deben conectar en forma permanente

2) Algoritmo de la ruta más corta
En el problemade la ruta más corta se determina cual es la ruta más corta, entre una fuente y un destino entre una red de transporte. Hay otras soluciones que se pueden representar con el mismo modelo, como se ve en el siguiente ejemplo.
--------Ejemplo.
En esta sección se presentan 2 algoritmos para resolver redes tanto cíclicas (bucles o lazos) como aciclicas:
-El algoritmo de Dijkstra.
- El algoritmo deFloyd.
El primero tiene por objeto determinar las rutas mas cortas entre el nodo fuente y todos los demás nodos de la red. El sehundo es general por que permite determinar la ruta mas corta entre 2 nodos cualquiera en la red.
Algoritmo de Dijkstra: Sea Ui la distancia mas corta del nodo fuente 1 hasta “i” y se define dij > 0 como la longitud del arco, entonces el algoritmo define la etiqueta...