Procesos de decisión.

INVESTIGACIÓN OPERATIVA 2

Capítulo 1: Redes

• Introducción

Dondequiera que miremos en nuestra vida cotidiana, las redes son evidentes. Redes eléctricas y de poder traen iluminación y el entretenimiento a nuestros hogares. Redes telefónicas nos permiten comunicarse entre sí casi sin esfuerzo dentro de nuestras comunidades locales ya través de las fronteras regionales e internacionales. Los sistemas nacionales de carreteras, redes ferroviarias, aéreas y redes de servicios que nos proporcionan los medios para cruzar grandes distancias geográficas para cumplir con nuestro trabajo, para ver a nuestros seres queridos, y visitar nuevos lugares y vivir nuevas experiencias. Redes de fabricación y distribución que nos dan acceso a esencial de los productos de consumo. Y las redes informáticas, como los sistemas de reservas aéreas, han cambiado la manera de compartir información y llevar a cabo nuestros negocios y vidas personales.

En todos estos dominios de problemas, y en muchos más, deseamos mover alguna entidad (electricidad, un producto de consumo, una persona o un vehículo, un mensaje) a partir de un punto a otro en una red subyacente, y para hacerlo tan eficientemente como sea posible, tanto para proporcionar un buen servicio a los usuarios de la red y utilizar instalaciones de transmisión efectiva (típicamente caro).

Objetivo: “aprender a modelar como objetos matemáticos, conocidos problemas de flujo de red y el estudio de diversas maneras (algoritmos) para resolver los modelos resultantes”.

• Definición

Los Flujos de redes son un dominio de problemas que se encuentra en la cúspide entre varios campos de investigación, incluidas las matemáticas aplicadas, informática, ingeniería, administración e investigación de operaciones. El campo tiene una tradición rica y larga, y remonta sus raíces a la obra de Gustav Kirchhof y otros pioneros de la ingeniería eléctrica y mecánica que sistemáticamente por primera vez analizados los circuitos eléctricos. Este primer trabajo sentó las bases de muchas de las ideas fundamentales de la teoría de flujo de redes, y las redes establecidas (gráficos) como objetos matemáticos útiles para la representación de muchos sistemas físicos.

Gran parte de este trabajo inicial fue de carácter descriptivo, respondiendo a preguntas tales como: si se aplica un conjunto de tensiones a una red dada, ¿cuál será el flujo de corriente resultante? Posteriormente surgen nuevas inquietudes como ¿Si tenemos alternativas para conectar a una red (es decir, enviar el flujo), la alternativa será más rentable? Nuestra herencia intelectual para responder a tales preguntas es mucho más reciente y se remonta a la década de 1940 y principios de 1950, cuando las comunidades de investigación y optimización han desarrollado poderosos instrumentos que conocemos hoy en día para realizar cálculos científicos y de gestión.

En su mayor parte, se aborda las siguientes cuestiones fundamentales:

1. Problema del camino más corto: ¿Cuál es la mejor forma de recorrer la red para ir de un punto a otro lo más barato posible?
2. Problema de flujo máximo. Si una red tiene la capacidad del flujo en los arcos, ¿cómo podemos enviar el flujo máximo posible entre dos puntos de la red al tiempo que respeta las capacidades de flujo de arco?
3. Coste mínimo problema de flujo. Si incurrimos en un costo por unidad de flujo en una red con capacidades de arco y necesitamos enviar unidades de un bien que residan en uno o varios puntos de la red a uno o más puntos de otro modo, ¿cómo podemos enviar el material a un costo mínimo posible?

En el sentido tradicional de las matemáticas aplicadas y puras, cada uno de estos problemas es trivial de resolver. No es muy difícil (pero no del todo evidente para los dos problemas más adelante) para ver que sólo tenemos que considerar un número finito de alternativas para cada problema. Así que un matemático tradicional podría decir que los problemas están bien resueltos, porque basta con enumerar el conjunto de soluciones posibles y elegir la que es mejor. Desafortunadamente, este enfoque está lejos de lo pragmático, ya que el número de posibles alternativas pueden ser muy grandes, más que el número de átomos en el universo para muchos problemas prácticos. Así que mejor nos gustaría diseñar algoritmos que son, en cierto sentido "bueno", es decir, cuyo tiempo de cálculo es pequeño, o por lo menos razonable, por problemas encontrados en la práctica. Una forma de asegurar este objetivo es diseñar algoritmos cuyo tiempo de funcionamiento se garantiza que no crecen muy rápido como la red se hace más grande.

En el campo de los flujos de redes, los investigadores idearon los primeros aportes en la década de 1950 antes de que el campo de la teoría de la complejidad computacional aún existiera como una disciplina separada tal como la conocemos hoy en día. Y a lo largo de las tres últimas décadas, los investigadores han hecho un flujo constante de innovaciones que han dado lugar a nuevos métodos de solución y en la mejora de los métodos conocidos. En los últimos años, sin embargo, los investigadores han hecho contribuciones al diseño y análisis de algoritmos de flujo de red con mejores garantías de ejecución de peor caso a un ritmo explosivo, casi vertiginoso, por otra parte, estas contribuciones fueron muy sorprendentes: A lo largo de los años 1950, 1960, y 1970, los flujos de la red se había convertido en un campo bastante maduro, tanto es así que la mayoría de las comunidades de investigación y practicante cree que los modelos básicos que se estudian en este libro fueron tan bien entendido de que las innovaciones adicionales serían difíciles de conseguir y serían pocos y distantes entre sí.

...