Modelos de optimizacion.

Título:
Modelos de optimización de redes.

Introducción:
Los modelos de optimización de redes se utilizan ampliamente en aéreas tan diversas como la producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera.
Una representación de redes proporciona un panorama general poderoso y una ayuda conceptual para visualizar lasrelaciones entre las componentes de los sistemas. La aparición de algunos algoritmos ha tenido un impacto importante, al igual que las ideas de ciencias de la computación acerca de las estructuras de datos y manipulación eficiente del mismo.
Las situaciones en las que se pueden aplicar estos algoritmos también se pueden formular y resolver en forma de programas lineales explícitos, sin embargo,los algoritmos basados en redes, son más eficientes.
Una red consiste en una serie de nodos con arcos o ramas. La notación para describir una red es (N,A), donde N es el conjunto de nodos y A es el conjunto de arcos.

Contenido:

Terminologia:

Red: Una red consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos. Los puntos se llaman 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.

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ínea querepresenta 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[pic]B.

Arcos No Dirigidos: Si el flujo a través de un arco se permite en ambas direcciones (como una tubería que se puede usarpara bombear fluido en ambas direcciones), se dice que es un arco no dirigido.

También se les llama ligadura. Aunque se permita que el flujo a través de un arco no dirigido ocurra en cualquier dirección, se supone que ese flujo será en una dirección, en la seleccionada, y no se tendrá flujos simultáneos en direcciones opuestas.

Trayectoria: Una trayectoria entre dos nodos es una sucesión dearcos distintos que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan los nodos O y T en la figura 1 es la sucesión de arcos OB-BD-DT (O[pic]B[pic]D[pic]T), y viceversa.

Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas y trayectorias no dirigidas.

Trayectoria Dirigida: Una trayectoria dirigida del nodo ial nodo j, es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a través de esta trayectoria es factible.

Trayectoria No Dirigida: Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) pueden ser hacia o desde el nodo j. Con frecuencia alguna trayectoria no dirigida tendráalgunos arcos dirigidos hacia el nodo j y otros desde él (es decir, hacia el nodo i).

Ciclo: Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En la red no dirigida que se muestra en la figura 5 existen muchos ciclos, OA-AB-BC-CO.

Red Conexa: Una red conexa es una red en la que cada par de nodos está conectado. Se dice que dos nodos están conectados si la red contiene al menosuna trayectoria no dirigida entre ellos. Se debe resaltar que no es necesario que la trayectoria sea dirigida aun cuando la red sea dirigida. La figura 1 representa una red conexa.

Árbol de Expansión: es una red conexa para los n nodos, que contiene ciclos no dirigidos. Todo árbol de expansión tiene justo n-1 arcos, ya que este es el número mínimo de arcos necesarios para tener una red conexa...