Inv De Op 2

INSTITUTO TECNOLOGICO DE CHIHUAHUA

EAD

Investigación de operaciones II.

Optimización de redes.

Prof. Enrique Hernandez.

Jesús Alfredo López Ruiz

N.C: 05060081
13-jun-2012

Introducción:
Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en la vida diaria. Larepresentación de redes se utiliza ampliamente en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera, para nombrar sólo unos ejemplos.
De hecho, una representación de redes proporciona un panorama general tan poderoso y una ayuda conceptual para visualizar lasrelaciones entre los componentes de los sistemas, que se usa casi en todas las áreas científicas, sociales y económicas.
Uno de los mayores desarrollos recientes en investigación de operaciones (IO) ha sido el rápido avance tanto en la metodología como en la aplicación de los modelos de optimización de redes. La aparición de algunos algoritmos ha tenido un impactoimportante, al igual que las ideas de ciencias de la computación acerca de estructuras de datos y la manipulación eficiente de los mismos. En consecuencia, ahora se dispone de algoritmos y paquetes de computadora y se usan en forma rutinaria para resolver problemas muy grandes que no se habrían podido manejar hace dos o tres décadas.
Muchos modelos de optimización de redes son enrealidad tipos especiales de problemas de programación lineal.

Optimización de redes
Una representación de redes proporciona un panorama general y una ayuda conceptual para visualizar las relaciones entre los componentes del sistema. A este conjunto se le conoce como red, y sus componentes son:

Donde los círculos representan a los elementos y se conocen como nodos y las líneas son larelación entre ellos y se les denomina flechas; estas pueden tener o no una dirección especifica, también se encuentran en forma de arco para determinar ciclos dirigidos o no dirigidos, los números son la distancia entre los distintos elementos o nodos.

* La investigación de operaciones, en optimización de redes nos plantea diferentes tipos de problemas.
1.-El problema de la ruta más corta.
Aquíse plantea una la necesidad de encontrar el camino mas corto dentro de una red.las aplicaciones de este problema por mencionar algunas son.

1.-minimizar la distancia total recorrida.
2.-minimizar el costo total de la secuencia de actividades.
3.-minimizar el tiempo total de la secuencia de actividades.
En ocasiones un solo problema puede plantear una minimización en los tres factores.
Sitomamos una flecha con dos nodos especialmente llamados origen y destino.
Si tomamos en cuenta la ilustración anterior veremos que para llegar del elemento “O” al elemento “B” la ruta mas corta será O-A-b, ya que las distancias serán de “O” a “A” = 2 y “A” a “B”=2 esto nos da un total de 4 a diferencia de el camino “directo” de “O”a”B” =5

2.-Problema del árbol de expansión mínima.
Este caso deproblema es muy similar al anterior de ruta mas corta, pero aquí solo se muestra los nodos y no las ligaduras, el objetivo de este problema es encontrar las ligaduras que satisfagan que cada par de nodos tenga una ligadura y toda la red este ligada, encontrando el numero mínimo de distancias entre las ligaduras (tiempo, costo, distancia) insertadas en la red.
Algoritmo para el problema de árbolen expansión mínima.
Se selecciona de manera arbitraria un nodo y se busca el nodo mas cercano que no este conectado a el, con el siguiente nodo se busca nuevamente el nodo mas cercano que no este conectado a este ultimo, de esta manera se conectan todos los nodos de la red, los nodos pueden estar conectado entre si o a un tercer nodo.

Aquí se selecciona de manera arbitraria un nodo en...