MODELOS DE OPTIMIZACI N DE REDES


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 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 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 lametodologí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 muygrandes que no se habrían podido manejar hace dos o tres décadas.
Muchos modelos de optimización de redes son en realidad tipos especiales de problemas de programación lineal. Por ejemplo, tanto el problema de transponer como el de asignación pertenecen a esta categoría debido a su representación mediante una red.
Cuatro tipos importantes de problemas de redes y algunas ideas básicas sobre cómoresolverlos (sin profundizar en los aspectos de estructuras de bases de datos, tan vitales para la aplicación exitosa en los problemas de gran escala). Los tres primeros tipos de problemas: el problema de la ruta más corta, el problema del árbol de mínima expansión y el problema del flujo máximo, tienen una estructura específica que surge con frecuencia en la práctica.
El cuarto tipo el problema delflujo de costo mínimo proporciona un enfoque unificador de muchas otras aplicaciones por su estructura mucho más general. De hecho, esta estructura es tan general que incluye como casos especiales el problema de la ruta más corta y el de flujo máximo, al igual que los problemas de transporte y de asignación.
TERMINOLOGÍA DE REDES
Se ha desarrollado una terminología relativamente extensa paradescribir 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 conforme se usen los términos en las secciones subsecuentes.Como ayuda, se resalta el nombre de cada término en negritas en el punto en que se define.

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 tiene siete nodos representados por siete círculos. Las líneas se llaman arcos (o ligaduras, aristas o ramas); por ejemplo, la red tiene 12 arcos.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.
Los arcos de una red pueden tener un flujo de algún tipo que pasa por ellos. La tabla proporciona varios ejemplos de flujo en redes. 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 un arcodirigido. 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.

Si el flujo a través de un arco...