Problema de optimización

Representación gráfica de un problema de optimización típico.

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:

• Un problema de optimización con variables discretas se conoce como optimización discreta, en la que un objeto como un número entero, una permutación o un gráfico se debe encontrar en un conjunto contable.
• Un problema con variables continuas se conoce como optimización continua, en la que se debe encontrar un valor óptimo de una función continua. Pueden incluir problemas restringidos y problemas multimodales.

Problema de optimización continua

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

$\begin{array}{cccc}& \underset{x}{\mathrm{minimizar}}& & f(x)\\ & \mathrm{s}\mathrm{u}\mathrm{j}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{a}& & g_i(x)\le 0,i=1,\dots ,m\\ & & & h_j(x)=0,j=1,\dots ,p\end{array}$

donde

• Plantilla:Math es la función objetivo a minimizar sobre el vector Plantilla:Mvar de Plantilla:Mvar-variables,
• Plantilla:Math se denominan restricciones de desigualdad
• Plantilla:Math se denominan restricciones de igualdad, y
• Plantilla:Math y Plantilla:Math.

Si Plantilla:Math, 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

Formalmente, un problema de optimización combinatoria Plantilla:Mvar es un cuádruple Plantilla:Math, donde

• Plantilla:Math es un conjunto de instancias;
• dada una instancia Plantilla:Math, Plantilla:Math es el conjunto de soluciones factibles;
• dada una instancia Plantilla:Mvar una solución factible Plantilla:Mvar de Plantilla:Mvar, Plantilla:Math denota la medida de Plantilla:Mvar, que generalmente es un real positivo.
• Plantilla:Mvar es la función objetivo, y es [[Extremos de una función|Plantilla:Math]] o [[Extremos de una función|Plantilla:Math]].

El objetivo es entonces encontrar para algún caso Plantilla:Mvar una solución óptima, es decir, una solución factible Plantilla:Mvar con

$m(x,y)=g\{m(x,y^{\prime })\mid y^{\prime }\in f(x)\}.$

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 Plantilla:Math. Por ejemplo, si hay un gráfico Plantilla:Mvar que contiene los vértices Plantilla:Mvar y Plantilla:Mvar, un problema de optimización podría ser "encontrar una ruta de Plantilla:Mvar a Plantilla:Mvar 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 Plantilla:Mvar a Plantilla:Mvar 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.

Véase también

• Problema de conteo (complejidad)
• Optimización del diseño
• Problema de funcionamiento
• Investigación de operaciones
• Satisfactorio: no es necesario encontrar el óptimo, solo una solución "suficientemente buena".
• Problema de búsqueda
• Programación semi-infinita

Enlaces externos

• Plantilla:Cita web