MODELOS DE OPTIMIZACION POR REDES

                  MODELOS DE OPTIMIZACION POR REDES.

Modelos de Optimización de Redes. 

Terminología de Redes. 

Problema de la Ruta Más Corta. 

Problema del Árbol de Expansión Mínima. 

Problema de Flujo Máximo. 

Problema del Flujo de Costo Mínimo.

PROGRAMACION LINEAL EN TEORIAS DE REDES.

USO DE SOFTWERE.

MODELOS DE OPTIMIZACIÓN DE REDES

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. La representación de redes se utilizaampliamente en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administraciónde 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 las relaciones 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 impacto importante, 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.

TERMINOLOGÍA.

Se ha desarrollado una terminología relativamente extensa para describir los tipos de redes y sus componentes. Aunque se ha evitado en lo posible el uso del vocabulario específico, es necesario introducir un número considerable de términos que se usarán en este capítulo. Se sugiere al lector que lea la sección completa una vez para entender las definiciones y planee después regresar a refrescar la memoria confórmese usen los términos en las secciones subsecuentes. Como ayuda, seres alta el nombre de cada término en

Negritas en el punto en que redefine.

[pic 1]

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); por ejemplo, la red de la figura 9.1 tiene siete nodos representados por siete círculos. Las líneas se llaman

Arcos

(Oligaduras, aristas o ramas); por ejemplo, la red de la figura 9.1 tiene 12arcos. Los arcos se etiquetan para dar nombre a los nodos en sus puntos terminales; por ejemplo, AB es el arco entre los nodos A y B en la figura 9.1.Los arcos de una red pueden tener un flujo de algún tipo que pasa por ellos. La tabla 9.1 proporciona varios ejemplos de flujo enredes. Si el flujo a través de un arco se permite sólo en una dirección (como en una calle de un sentido), se dice que el arco es unArcodirigido. La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco. Al etiquetar un arco dirigido con

El nombre de los nodos que une, siempre se pone primero el 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 de etiquetado es A→B.

[pic 2]

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 el arco es un

Arco no dirigido. Para ayudar a distinguir entre los dos tipos de arcos, con frecuencia se hará referencia a los arcos no dirigidos con el sugestivo nombre de Ligadura. Aunque se permita que el flujo a través de un arco no dirigidoocurra en cualquier dirección, se supone que ese flujo será en una dirección, en la seleccionada, y no se tendrán flujos simultáneos en direcciones opuestas. (Este último caso requiere usar un Par de Arcos dirigidos.

En direcciones opuestas). Sin embargo, en el proceso detona decisiones sobre el flujo en un arco no dirigido, se permite hacer una secuencia de asignaciones de flujos en direcciones opuestas, pero en el entendimiento de que el flujo real será

Flujo neto. (La diferencia delos flujos asignados en las dos direcciones). Por ejemplo, si se asignan flujo de 10 en una dirección y después un flujo de 4 en la dirección opuesta, el efecto real es la cancelación de 4 unidades de la asignación original, lo que reduce el flujo en la dirección original de 10a 6. Aun para un arco dirigido, en ocasiones se usa la misma técnica como una manera conveniente de reducir un flujo previamente asignado. En particular, se puede hacer una asignación ficticia de flujo en la dirección "equivocada" a través de un arco dirigido para registrar una reducción en esa cantidad en el flujo que va en la dirección “correcta."

PROBLEMA DELA RUTA MÁS CORTA

Aunque al final de la sección se mencionan otras versiones del problema de la ruta más corta (incluyendo algunas para redes dirigidas),la atención se centrará en la siguiente versión sencilla. Considere una red conexa y no dirigida con dos nodos especiales llamado origen y destino.

 A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.

EJEMPLO PROTOTIPO: Se ha decidido construir un colector de “Aguas residuales” desde la ciudad “O” hasta la planta de tratamiento “T”.

...