Principios de optimización y métodos combinatorios

Abstract

En el presente trabajo discutiremos algunos principios de optimización que dan lugar a Métodos combinatorios para la determinación de máximos o mínimos de funciones definidas sobre un conjunto numerable de puntos. La aplicación de estos métodos la haremos a través de varios problemas de interés, a los cuales podemos reducir muchos problemas que se presentan en la vida diaria, como es el famoso problema del agente viajero que debe encontrar el itinerario de mínimo costo que le permita recorrer un conjunto de ciudades en donde conoce las tarifas de transporte entre cada par de ellas. Evidentemente el número de itinerarios posibles correspondería al número de permutaciones del conjunto de ciudades, el cual es un conjunto numerable que puede ser muy grande. Es claro ver que cualquier método enumerativo para un número suficientemente grande de ciudades es casi imposible de aplicar, sin embargo este problema puede resolverse fácilmente mediante la aplicación de métodos combinatorios.