Modelo de redes

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Defensa
Universidad Nacional Experimental
Politécnica de la Fuerza Armada Nacional
Núcleo Caracas- Sede Chuao
Contaduría Pública. 7mo Semestre
Sección: LCP-D01 Aula: 1101
Asignatura: Investigación de Operaciones

Integrantes:
JennyGraterol C.I: 19.220.042
José Chávez C.I: 15.836.062
Miriam Carreño C.I: 6.300.623
Nancy Valladares C.I: 14.277.752
Sarelis Córdova C.I: 11.968.820

Prof.: Reiza Garcías

Caracas, 7 de Julio de 2010

Introducción

Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes de 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, los cables, las tuberías y el flujo lo representan los camiones, mensajes y fluidosque 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 de redes se presentan varias opciones para tomar como el modelo de la ruta más corta, el árbol de expansión mínima, algoritmo del flujomáximo, algoritmo de redes capacitadas de costo mínimo, algoritmo de la ruta crítica (CPM), 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 pararepresentarlos como una red.

Índice
Pág.

Introducción…………………………….……………………………………………......2

Definición de Red…………………………………………………………………………4

Características de Red…………………………………………………………………..4

Modelos para optimizar las Redes:

1. Árbol de expansión mínima………………………………………………………7

2. Algoritmo de la ruta más corta…………………………………………………...8

3. Algoritmo del flujomáximo……………………………………………………....12

4. Algoritmo de redes capacitadas de costo mínimo…………………………….14

5. Algoritmo de la ruta crítica (CPM)……………………………………………....20

Conclusión……………………………………………………………………………....24

Bibliografía………………………………………………………………….………...…25

Modelo de Redes

Definición de Red

Una red consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos. Los puntos sellaman nodos (o vértices). Las líneas se llaman arcos (o ligaduras, aristas o ramas).
Los arcos se etiquetan para dar nombres a los nodos en sus puntos terminales, por ejemplo, AB es el arco entre lo nodos A Y B.
En un problema de programación lineal, las redes pueden representar un conjunto de estaciones, campos petrolíferos, almacenes, fabricas, sucursales, ciudades, interconectadas entre si através de caminos, conductos, tuberías que permiten fluir productos para la comercialización o la distribución.

Características de Red

Un modelo de Red presenta las siguientes características:

Arcos Dirigidos: Se dice que un arco es dirigido cuando 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íneaque representa el arco.
Al etiquetar un arco dirigido con el nombre de los nodos que une, siempre se coloca primero al nodo de donde viene y después el nodo a donde va, esto es, un arco dirigido del nodo A al nodo B debe etiquetarse como AB y no como BA. Otra Manera es A B.
Arcos No Dirigidos: Si el flujo a través de un arco se permite en ambas direcciones (como una...