Modelos Optimizacion

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 del sistema, 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.

Se darán a conocer en este trabajo cinco tipos importantes de problemas de redes y algunas ideas básicas sobre cómo resolverlos (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 del flujo de costo mínimo- proporciona un enfoque unificador de muchas otras aplicaciones por su estructura mucho más general. Y por último el método del CPM.

Terminología de Redes

Red: conjunto de puntos y líneas que unen ciertos pares de puntos.

Nodos: Puntos (o vértices).

Arcos: Líneas, ligaduras, aristas o ramas. Se etiquetan para dar nombre a los nodos en sus puntos terminales.

Arco dirigido: Si el flujo a través de un arco se permite sólo en una dirección. La dirección se indica agragando una cabeza de flecha al final de la línea que representa el arco.

Arco no dirigido: Si el flujo a través de un arco se permite en ambas direcciones.

Red dirigida: Red que tiene sólo arcos dirigidos.

Red no dirigida: Todos sus arcos son no dirigidos.

Trayectoria: Sucesión de arcos distintos que conectan nodos.

Ciclo: Trayectoria que comienza y termina en el mismo nodo.

Red conexa: Red en la que cada par de nodos esta conectado.

Árbol: Red conexa (para algún subconjunto de n nodos) que no contiene ciclos no dirigidos.

...