Teoria De Redes

INSTITUTO TECNOLOGICO SUPERIOR DE ACAYUCAN
Unidad 5: Optimización de Redes
Ingeniería industrial
704-C
Investigación de operaciones II
05/12/2012
Unidad 5: Optimización de Redes
Ingeniería industrial
704-C
Investigación de operaciones II
05/12/2012





INDICE

Unida V: Optimización de redes

OBJETIVO
INTRODUCCION
JUSTIFICACIÓN
5.1 Terminología
5.2 Problema de la ruta máscorta
5.3 Problema de árbol de mínima expansión
5.4 Problema de flujo máximo
5.5 Problema de flujo de costos mínimos
5.6 Uso de software
CONCLUSION
BIBLIOGRAFIA

OBJETIVOS
* Conocer conceptos como nodos, arcos, redes, rutas, flujos, etc., que serán utilizados a lo largo de la unidad en la solución de problemas de redes.
* Ser capaces de desarrollar ejercicios de redes, queincluyen los de árbol de expansión mínima, problemas de la ruta más corta, algoritmo de flujo máximo, y algoritmo de costo mínimo.

INTRODUCCIÓN
En el siguiente se trataran acerca de lo que son los nodos, los arcos y de cómo estos se relacionan para formar una red y de la relación de que tienen para algún tipo de flujo, hablaremos acerca de la notación para describir las redes que son (N, A), en dondeN es el conjunto de nodos y A es el conjunto de arcos. El problema de la ruta más corta tiene que ver con la determinación de las ramas conectadas en una red de transporte que constituyen, en conjunto, la distancia más corta entre una fuente y un destino. Se llevara a cabo la explicación de la forma de realizar el algoritmo de árbol de expansión mínima, este algoritmo se refiere a las redes endonde se forman por nodos que se conectan entre sí.

JUSTIFICACION
Tener la capacidad de entender y explicar a los compañeros cada uno de los temas asignados. Y el de desarrollar habilidades con la capacidad de transmitir los conocimientos adquiridos en la unidad.

5.1 TERMINOLOGÍA
Muchos problemas de optimización importantes se analizan mejor por medio de una representación grafica o de red.En este capítulo, se consideran cuatro modelos específicos de red: problemas de trayectoria más corta, problemas de flujo máximo, modelos de programación de proyecto CPM-PERT y problemas de árbol de expansión mínima, para los que existen procedimientos de soluciones eficientes. También se estudian problemas de redes en flujo mínimo o costo mínimo (FMOCM), de los cuales los problemas detransporte, asignación, transbordo, trayectoria más corta, flujo máximo, y los modelos de programación de proyecto CPM, son casos especiales. Por último, se analiza una generalización del simplex de transporte, el simplex de red, que se puede utilizar para resolver problemas de flujo de red de costo mínimo. El capitulo comienza con algunos términos básicos utilizados para describir graficas y redes.DEFINICIONES BASICAS
Una grafica, o red, se define mediante dos conjuntos de símbolos: nodos y arcos. Primero se define, se define un conjunto (llámelo v) de puntos extremos o vértices. Los vértices de una grafica o red también se llaman nodos.
También se define un conjunto de arcos A.
Un ARCO consiste en un par ordenado de puntos extremos y representa una posible dirección de movimiento que podríaocurrir entre puntos extremos (o vértices).
Para los fines que aquí se persiguen, si una red contiene un arco (j, k), entonces el movimiento es posible del nodo j al nodo k. suponga que los nodos 1, 2, 3 y 4 de la figura 1 representa ciudades y cada arco representa una carretera (de un solo sentido) que enlaza dos ciudades. Para esta red, V= [1, 2, 3, 4] Y A= [(1,2), (2,3), (3,4), (4,3), (4,1)].Para el arco (j, k), el nodo j es el nodo inicial y el nodo k es el nodo terminal. Se dice que el arco (j, k) va del nodo jal nodo k.
Por consiguiente, el arco (2,3) tiene el nodo inicial 2 y el nodo terminal 3, y va del nodo 2 al nodo 3. El arco (2,3) se podría viajar de la ciudad 2 a la ciudad 3. En la figura 1, los arcos muestran que se permite viajar de la ciudad 3 a la ciudad 4 y de la...