Optimización de funciones

Optimización
En matemáticas la optimización o programación matemática intenta dar respuesta a un tipo general de problemas donde se desea elegir el mejor entre un conjunto de elementos. En su forma más simple, el problema equivale a resolver una ecuación de este tipo:
[pic]
Donde x = (x1,...,xn) es un vector y representa variables de decisión, f(x) es llamada función objetivo yrepresenta o mide la calidad de las decisiones (usualmente números enteros o reales) y Ω es el conjunto de puntos o decisiones factibles o restricciones del problema.
Algunas veces es posible expresar el conjunto de restricciones Ω como solución de un sistema de igualdades o desigualdades.
[pic]
Un problema de optimización trata entonces de tomar una decisión óptima para maximizar(ganancias, velocidad, eficiencia, etc.) o minimizar un criterio determinado (costos, tiempo, riesgo, error, etc). Las restricciones significan que no cualquier decisión es posible.
Optimización combinatoria
La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada a la investigación de operaciones, teoría de algoritmos yteoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo eltamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.
Los algoritmos de optimización combinatoria a menudo son implementados en lenguajes imperativos como C y C++,en lenguajes de programación lógicos tales como Prolog, o incluso en lenguajes multi-paradigma tales como Oz.
Mediante el estudio de la teoría de la complejidad computacional es posible comprenderla importancia de la optimización combinatoria. Los algoritmos de optimización combinatoria se relacionan comúnmente con problemas NP-hard. Dichos problemas en general no son resueltos eficientemente, sin embargo, varias aproximaciones de la teoría de la complejidad sugieren que ciertas instancias (ej. "pequeñas" instancias) de estos problemas pueden ser resueltas eficientemente. Dichas instanciasa menudo tienen ramificaciones prácticas muy importantes.

Definición formal

Una instancia de un problema de optimización combinatoria puede ser descrito formalmente como una tupla (X,P,Y,f,extr) donde
• X es el espacio de soluciones (en el cual f y P están definidos)
• P es la factibilidad predicado.
• Y es el conjunto de soluciones factibles.
• f es la funciónobjetivo.
• extr es el extremo (normalmente min o max).

Problema

El problema del viajante es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.
La respuesta al problema es conocida, es decir se conoce la forma deresolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado (Para una mayor profundidad en el tema ver el artículo NP-completos).
El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejorestudiado) en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, el TSP es uno de los más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos desde hace siglos.

Enunciado

Sean N ciudades de un territorio....