metrologia y normalizacion

9

C A P Í T U L O

Modelos de optimización de redes

L

os 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
de manera amplia en áreas tan diversas como producción, distribución, planeación de proyectos,
localización de instalaciones, administraciónde recursos y planeación financiera, por mencionar
sólo algunos ejemplos. En realidad, una representación de redes proporciona un poderoso apoyo
visual y conceptual para mostrar las relaciones entre las componentes de los sistemas, de tal modo
que se usa casi en todos los ámbitos científicos, sociales y económicos.
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 efecto importante, al igual que las ideas de
ciencias de la computación acerca de estructuras de datos y la manipulación eficiente de éstos. En
la actualidad se dispone de algoritmos y paquetes de computadora que se usan en formarutinaria
para resolver problemas muy grandes 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 transporte como el de asignación, que se
presentaron en el capítulo anterior, pertenecen a esta categoría debido a su representación mediante
una red quese mostró en las figuras 8.3 y 8.5.
Uno de los ejemplos de programación lineal que se presentó en la sección 3.4 también es un
problema de optimización de redes. Éste es el ejemplo de la Distribution Unlimited Co., que desea
saber cómo repartir sus bienes en la red de distribución que se muestra en la figura 3.13. Este tipo
especial de problema de programación lineal, llamado de flujo de costomínimo se presenta en la
sección 9.6. Se volverá a analizar este ejemplo en particular en esa sección y después se resolverá
con la metodología de redes en la sección siguiente.
En este capítulo sólo serán planteadas las bases de la metodología de redes actual. Sin embargo, se presentará una introducción a cinco 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 a gran escala). Los tres primeros tipos de
problemas —el de la ruta más corta, el del árbol de mínima expansión y el del flujo máximo— tienen una estructura específica que surge con frecuencia en la práctica.
El cuarto tipo —problema del flujo de costo mínimo—proporciona un enfoque unificado de
muchas otras aplicaciones debido a su estructura mucho más general. 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 del capítulo 8. En razón de que el problema del
flujo de costo mínimo es un tipo especial de problema de programaciónlineal, se puede resolver
en forma eficiente mediante una versión simplificada del método símplex llamada método símplex
de redes. (No se presentarán problemas de redes aún más generales cuya solución es más complicada.)
El quinto tipo de problemas de redes que se considera aquí implica la determinación del modo
más económico de realizar un proyecto de forma que éste pueda terminarse en su fechalímite.
Se utiliza una técnica llamada método CPM de trueques entre tiempo y costo para formular un

332

CAPÍTULO 9

MODELOS DE OPTIMIZACIÓN DE REDES

modelo de red del proyecto y los trueques entre tiempo y costo para sus actividades. Después se
utiliza el análisis de costo marginal o la programación lineal para resolver el plan de proyecto
óptimo.
En la primera sección se...