Ir al contenido

Problema de optimización

De Wikipedia, la enciclopedia libre

En matemáticas, ciencias de la computación y economía, un problema de optimización es el problema de encontrar la mejor solución a partir de todas las soluciones factibles.

Los problemas de optimización se pueden dividir en dos categorías, dependiendo de si las variables son continuas o discretas:

Problema de optimización continua

[editar]

La forma estándar de un problema de optimización continua es[1]

donde

  • f : n es la función objetivo a minimizar sobre el vector x de n-variables,
  • gi(x) ≤ 0 se denominan restricciones de desigualdad
  • hj(x) = 0 se denominan restricciones de igualdad, y
  • m ≥ 0 y p ≥ 0.

Si m = p = 0, el problema es un problema de optimización sin restricciones. Por convención, la forma estándar define un problema de minimización. Un problema de maximización puede tratarse negando la función objetivo.

Problema de optimización combinatoria

[editar]

Formalmente, un problema de optimización combinatoria A es un cuádruple (I, f, m, g), donde

  • I es un conjunto de instancias;
  • dada una instancia xI, f(x) es el conjunto de soluciones factibles;
  • dada una instancia x una solución factible y de x, m(x, y) denota la medida de y, que generalmente es un real positivo.
  • g es la función objetivo, y es min o max.

El objetivo es entonces encontrar para algún caso x una solución óptima, es decir, una solución factible y con

Para cada problema de optimización combinatoria, hay un problema de decisión correspondiente que pregunta si existe una solución factible para alguna medida particular m0. Por ejemplo, si hay un gráfico G que contiene los vértices u y v, un problema de optimización podría ser "encontrar una ruta de u a v que use la menor cantidad de aristas". Este problema podría tener una respuesta de, digamos, 4. Un problema de decisión correspondiente sería "¿hay una ruta de u a v que use 10 aristas o menos?" Este problema se puede responder con un simple 'sí' o 'no'.

En el campo de los algoritmos de aproximación, los algoritmos están diseñados para encontrar soluciones casi óptimas a problemas difíciles. La versión de decisión habitual es entonces una definición inadecuada del problema, ya que solo especifica soluciones aceptables. Aunque podríamos introducir problemas de decisión adecuados, el problema se caracteriza más naturalmente como un problema de optimización.[2]

Véase también

[editar]

Referencias

[editar]
  1. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. p. 129. ISBN 978-0-521-83378-3. 
  2. Ausiello, Giorgio (2003), Complexity and Approximation (Corrected edición), Springer, ISBN 978-3-540-65431-5 .

Enlaces externos

[editar]