Resolución de problemas de Optimización Combinatoria mediante técnicas de Programación Lineal Entera
Paula Zabala
Departamento de Computación, FCEyN-UBA

Los problemas de Optimización Combinatoria aparecen en diversas situaciones de la vida real en una gran variedad de disciplinas, desde genética, física, química hasta finanzas, en la industria y en el sector de servicios. Generalmente, son problemas fáciles de describir, pero computacionalmente difíciles de resolver. La gran cantidad de aplicaciones hacen que estos problemas no sólo tengan interés teórico, sino también, una gran importancia práctica, donde se requiere solucionar problemas reales de gran importancia económica y de actualidad. Muchos de estos problemas pueden ser modelados mediante formulaciones de programación lineal entera o entera mixta, como por ejemplo la asignación de la tripulación a la flota de aviones de una aerolínea, el diseño de líneas de producción, la alocación de recursos, la asignación de frecuencias radiales y control de inventario, donde personas, máquinas, actividades, recursos, aviones, son indivisibles. En estos modelos el objetivo es buscar el óptimo de una función lineal donde algunas o todas las variables están restringidas a ser enteras y deben verificar un sistema de desigualdades lineales. El objetivo de esta charla es brindar una introducción a los problemas de Optimización Combinatoria, a los modelos de Programación Lineal Entera y a las técnicas algorítmicas utilizadas para su resolución.