Politica

MODELOS DE OPTIMIZACIÓN DE RE D E S

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.

Pág. 1 2 5 13 17 26

Nota : Los fundamentos teóricos fueron tomados del texto INVESTIGACION DE OPERACIONES HILLIER LIEBERMAN. Séptima edición
OPTIMIZACION DE REDESING. José Luis Albornoz Salazar

-6-

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 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 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 transpone como el de asignación pertenecen a esta categoría debido a su representación mediante una red. Uno de los ejemplos de programación linealpresentado 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 distribuir sus bienes en la red de distribución mostrada en la figura 3.13 (página 3 de esta guía). Este tipo especial de problema de programación lineal, llamado problema de flujo de costo mínimo, se presenta mas adelante. El tercer caso estudiado en lasección 3.5 también se refiere a una aplicación del problema del flujo de costo mínimo. Este caso incluyó

la planeación del abastecimiento, la distribución y la comercialización de bienes de Citgo Petroleum Corp. El equipo de IO de Citgo desarrolló un sistema para apoyar las decisiones basado en la optimización, utilizando la metodología del modelo del flujo de costo mínimo para cada productoy lo unió a la base de datos corporativa. Cada modelo de producto tiene alrededor de 3000 ecuaciones (nodos) y 15000 variables (arcos), que es un tamaño modesto para los estándares actuales en la aplicación de modelos de redes de optimización. El modelo toma en cuenta todos los aspectos del negocio, ayuda a la administración en todas las decisiones, desde el nivel de producción en las distintasrefinerías, hasta los precios que debe pagar o cobrar. La representación de redes es esencial debido al flujo de bienes a través de las distintas etapas: la compra de petróleo crudo de los proveedores, el envío a las refinerías, el refinamiento de los diferentes productos y el embarque de estos productos a los centros de distribución y terminales de almacenamiento para su venta posterior. Como sedijo en la sección 3.5, el sistema de modelado ha permitido a la compañía reducir su inventario en más de $116 millones de dólares sin disminuir los niveles de servicio. Esto ha significado un ahorro en los intereses anuales de $14 millones de dólares y mejoras en las decisiones de coordinación, costeo y compra, equivalentes a otros $2.5 millones de dólares anuales, junto con muchos beneficios...