Programación lineal. Flujo de redes



Alumno:
Cesar Augusto Hernández Rubio

Materia:
Administración de proyectos

Profesor(a):
García Alvarado Ma. Elena

Trabajo:
Modelo de programación lineal para reducción de redes


Numero de control: Semestre:
10070807 5º


Programación lineal. Flujo de redes
Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redesde transporte, redes de comunicación, sistema de vuelos de los aeropuertos, rutas de navegación de los cruceros, estaciones de bombeo que transportan fluidos a través de tuberías, rutas entre ciudades, redes de conductos y todas aquellas situaciones que puedan representarse mediante una red donde los nodos representan las estaciones o las ciudades, los arcos, los caminos, las líneas aéreas, loscables, las tuberías y el flujo lo representan los camiones, mensajes y fluidos que pasan por la red. Con el objetivo de encontrar la ruta mas corta si es una red de caminos o enviar el máximo fluido si es una red de tuberías.
Cuando se trata de encontrar el camino más corto entre un origen y un destino, la técnica, algoritmo o el modelo adecuado es el de la ruta más corta; aunque existenotros modelos de redes como el árbol de expansión mínima, flujo máximo y flujo de costo mínimo cada uno abarca un problema en particular. En este trabajo se mencionan los modelos de redes existentes y los problemas que abarca cada uno de ellos, además se describen los algoritmos que aplican estos modelos para encontrar la solución optima al problema. Utilizando la terminología utilizada para representarloscomo una red.
MODELOS DE REDES
Los problemas de optimización de redes se pueden representar en términos generales a través de uno de estos cuatro modelos:
Modelo de minimización de redes (Problema del árbol de mínima expansión).
Modelo de la ruta más corta.
Modelo del flujo máximo.
Modelo del flujo del costo mínimo.
Terminología de redes
* Arcos Dirigidos Se dice que un arco es dirigidocuando el arco tiene flujo en una dirección (como en una calle de un sentido).La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco.
* Arcos No Dirigidos: Si el flujo a través de un arco se permite en ambas direcciones (como una tubería que se puede usar para bombear fluido en ambas direcciones),se dice que es un arco no dirigido.
* Capacidad de Arco:Es la cantidad máxima de flujo(quizá sin finito)que puede circular en un arco dirigido.
* Nodo Fuente:(o nodo de origen) tiene la propiedad de que el flujo que sale del nodo excede al flujo que entra a él.
* Nodo Demanda:(o nodo destino) es el caso contrario al nodo fuente, donde el flujo que llega excede al que sale de él.
* Nodo de Trasbordo:(o nodo intermedio) satisface la conservación delflujo, es decir, el flujo que entra es igual al que sale.
* Algoritmo: Conjunto de instrucciones concretas y detalladas para realizar una acción determinada.



Los problemas de optimización de redes se representan generalmente a través de tres modelos:

•Modelo de minimización de redes (problema del árbol de mínima expansión) El modelo de minimización de redes o problema del árbol de mínimaexpansión tiene que ver con la determinación de los ramales que pueden unir todo los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos .No se deben incluir ciclos en la solución del problema. Algoritmo para construir el árbol de expansión mínima:
* Se selecciona, de manera arbitraria, cualquier nodo y se conecta(es decir, se agrega una ligadura) al nododistinto más cercano.
* Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estos dos nodos. Este paso se repite hasta que todos los nodos están conectados.
* Empates: los empates para el nodo más cercano distinto o para el nodo no conectado más cercano, sé pueden romper en forma arbitraria y el algoritmo debe llegar a una solución óptima.

•Modelo del flujo máxima Se...