Esta es la primera parte de un curso de Optimización Combinatoria. El cálculo numérico de problemas de optimización tuvo su origen a fines de los años cuarenta con el descubrimiento de un algoritmo para resolver el problema de programación lineal. El primer capítulo está dedicado a este problema, sus propiedades y los algoritmos que lo resuelven.
Buena parte de los problemas de optimización se plantean utilizando grafos. El capítulo 2 está dedicado a la noción de grafo y a describir algoritmos que resuelven algunos de estos problemas. En particular se describen varios algoritmos para hallar un camino óptimo en un grafo.
De especial importancia son los problemas combinatorios para los cuales hay algoritmos eficientes que proporcionan soluciones enteras. En general, los algoritmos para resolver problemas de programacion lineal no dan soluciones enteras pero hay problemas lineales de cierta estructura particular para los cuales se conocen algoritmos que proporcionan soluciones enteras. Los capítulos 3 y 4 están dedicados a algunos de estos problemas: máximo flujo y flujo de mínimo costo.
Finalmente consideraramos el caso general de resolver un problema de programacion lineal al cual le imponemos la condición de que la solución deba ser entera (capítulo 5). Veremos muchos ejemplos de problemas que se plantean de esta manera para mostrar la importancia de la condición entera. Desgraciadamente no se conocen algoritmos eficientes que los resuelvan. Explicaremos un método para obtener la solución, conocido como “Branch & Bound”.
La segunda parte de Optimización Combinatoria se dicta bajo el nombre de “Optimización” y tiene por objeto enseñar métodos alternativos para atacar los problemas que no tienen algoritmos eficientes que los resuelvan (algoritmos aproximados, métodos heurísticos). En ambos cursos se dan ejemplos de cómo se utilizaron algunas de las técnicas enseñadas en ellos para resolver problemas reales en la industria.
