Región factible

En optimización matemática, una región factible, un conjunto factible, un espacio de búsqueda o un espacio de solución es el conjunto de todos los puntos posibles (conjuntos de valores de las variables de elección) de un problema de optimización que satisface las restricciones del problema, incluyendo potencialmente desigualdades, igualdades y restricciones enteras.^[1]​ Este es el conjunto inicial de posibles soluciones al problema, antes de que se haya reducido el conjunto de candidatos.

Un problema con cinco restricciones lineales (en azul, incluidas las restricciones de no negatividad). En ausencia de restricciones enteras, el conjunto factible es la región completa delimitada por azul, pero con restricciones enteras es el conjunto de puntos rojos.

Ejemplo de espacio de búsqueda. Gráfica de una función con múltiples óptimos locales en 2 dimensiones.

Una región factible cerrada de un problema de programación lineal con tres variables es un poliedro convexo.

Por ejemplo, considere el problema

Minimizar ${\displaystyle x^{2}+y^{4}}$

con respecto a las variables ${\displaystyle x}$ y ${\displaystyle y,}$

sujeto a

${\displaystyle 1\leq x\leq 10}$

y

${\displaystyle 5\leq y\leq 12.\,}$

Aquí, el conjunto factible es el conjunto de pares ${\displaystyle (x,y)}$ en el que el valor de ${\displaystyle x}$ es al menos 1 y como máximo 10 y el valor de ${\displaystyle y}$ es al menos 5 y como máximo 12. Tenga en cuenta que el conjunto factible del problema está separado de la función objetivo, que establece el criterio a optimizar y que en el ejemplo anterior es ${\displaystyle x^{2}+y^{4}.}$

En muchos problemas, el conjunto factible refleja una restricción de que una o más variables deben ser no negativas. En problemas de programación de enteros puros, el conjunto factible es el conjunto de enteros (o algún subconjunto del mismo). En los problemas de programación lineal, el conjunto factible es un politopo convexo: una región en el espacio multidimensional cuyos límites están formados por hiperplanos y cuyas esquinas son vértices.

La satisfacción de restricciones es el proceso de encontrar un punto en la región factible.

Conjunto factible convexo

 

En un problema de programación lineal, una serie de restricciones lineales produce una región factible convexa de valores posibles para esas variables. En el caso de dos variables, esta región tiene la forma de un polígono simple convexo.

Un conjunto factible convexo es aquel en el que un segmento de línea que conecta dos puntos factibles cualesquiera pasa solo por otros puntos factibles, y no por puntos fuera del conjunto factible. Los conjuntos factibles convexos surgen en muchos tipos de problemas, incluidos los problemas de programación lineal, y son de particular interés porque, si el problema tiene una función objetivo convexa que debe maximizarse, generalmente será más fácil de resolver en presencia de una función de conjunto factible convexo y cualquier óptimo local también será un óptimo global.

Ningún conjunto factible

Si las restricciones de un problema de optimización son mutuamente contradictorias, no hay puntos que satisfagan todas las restricciones y, por lo tanto, la región factible es el conjunto nulo. En este caso, el problema no tiene solución y se dice que es inviable.

Conjuntos factibles acotados e ilimitados

 

Un conjunto factible acotado (arriba) y un conjunto factible ilimitado (abajo). El conjunto de la parte inferior continúa eternamente hacia la derecha.

Los conjuntos factibles pueden ser delimitados o ilimitados. Por ejemplo, el conjunto factible definido por el conjunto de restricciones ${\displaystyle \{x\geq 0,y\geq 0\}}$  es ilimitado porque en algunas direcciones no hay límite sobre qué tan lejos se puede llegar y aún estar en la región factible. En contraste, el conjunto factible formado por el conjunto de restricciones ${\displaystyle \{x\geq 0,y\geq 0,x+2y\leq 4\}}$  está acotado porque la extensión del movimiento en cualquier dirección está limitada por las restricciones.

En problemas de programación lineal con ${\displaystyle n}$  variables, una condición necesaria, pero insuficiente para que el conjunto factible esté acotado es que el número de restricciones sea al menos ${\displaystyle n+1}$  (como se ilustra en el ejemplo anterior).

Si el conjunto factible no está acotado, puede haber o no un óptimo, dependiendo de las características específicas de la función objetivo. Por ejemplo, si la región factible se define por el conjunto de restricciones ${\displaystyle \{x\geq 0,y\geq 0\}}$ , entonces el problema de la maximización de ${\displaystyle x+y}$  no tiene óptima, ya que cualquier solución candidato puede ser mejorada mediante el aumento de ${\displaystyle x}$  o ${\displaystyle y}$ ; sin embargo, si el problema es minimizar ${\displaystyle x+y}$ , entonces hay un óptimo (específicamente en ${\displaystyle (x,y)=(0,0)}$ ).

Solución candidata

En optimización y otras ramas de las matemáticas, y en algoritmos de búsqueda (un tema en ciencias de la computación), una solución candidata es un miembro del conjunto de posibles soluciones en la región factible de un problema dado. Una solución candidata no tiene que ser una solución probable o razonable al problema — simplemente está en el conjunto que satisface todas las restricciones; es decir, está en el conjunto de soluciones factibles. Los algoritmos para resolver varios tipos de problemas de optimización a menudo reducen el conjunto de soluciones candidatas a un subconjunto de las soluciones factibles, cuyos puntos permanecen como soluciones candidatas, mientras que las otras soluciones factibles se excluyen de ahora en adelante como candidatas.

El espacio de todas las soluciones candidatas, antes de que se hayan excluido los puntos factibles, se denomina región factible, conjunto factible, espacio de búsqueda o espacio de solución. Este es el conjunto de todas las posibles soluciones que satisfacen las limitaciones del problema. La satisfacción de restricciones es el proceso de encontrar un punto en el conjunto factible.

Algoritmo genético

En el caso del algoritmo genético, las soluciones candidatas son los individuos de la población que el algoritmo está desarrollando.^[2]​

Cálculo

En cálculo, se busca una solución óptima utilizando la prueba de la primera derivada: la primera derivada de la función que se está optimizando se equipara a cero, y cualquier valor de la(s) variable(s) de elección que satisfaga esta ecuación se considera como soluciones candidatas (mientras que aquellos que no se descartan como candidatos). Hay varias formas en las que una solución candidata puede no ser una solución real. Primero, podría dar un mínimo cuando se busca un máximo (o viceversa), y segundo, puede que no dé ni un mínimo ni un máximo, sino más bien un punto de silla o un punto de inflexión, en el que se produce una pausa temporal en la subida local o se produce la caída de la función. Tales soluciones candidatas pueden descartarse mediante el uso de la prueba de la segunda derivada, cuya satisfacción es suficiente para que la solución candidata sea al menos localmente óptima. En tercer lugar, una solución candidata puede ser un óptimo local pero no un óptimo global.

Al tomar antiderivadas de monomios de la forma ${\displaystyle x^{n},}$  la solución candidata que usa la fórmula de cuadratura de Cavalieri sería ${\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.}$  Esta solución candidata es de hecho correcta excepto cuando ${\displaystyle n=-1.}$ 

Programación lineal

En el método simplex para resolver problemas de programación lineal, se selecciona un vértice del politopo factible como la solución candidata inicial y se prueba su optimalidad; si se rechaza como el óptimo, un vértice adyacente se considera como la siguiente solución candidata. Este proceso continúa hasta que se encuentra que una solución candidata es la óptima.

 

Una serie de restricciones de programación lineal sobre dos variables produce una región de valores posibles para esas variables. Los problemas de dos variables que se pueden resolver tendrán una región factible en la forma de un polígono convexo simple si está acotado. En un algoritmo que prueba los puntos factibles de forma secuencial, cada punto probado es a su vez una solución candidata.

Véase también

• Optimización combinatoria
• Búsquedas no informadas
• Algoritmo de búsqueda
• Computación evolutiva
• Optimización (matemática)
• Investigación de Operaciones
• Programación con restricciones

Referencias

1. Beavis, Brian; Dobbs, Ian (1990). Optimisation and Stability Theory for Economic Analysis. New York: Cambridge University Press. p. 32. ISBN 0-521-33605-8. 
2. Whitley, Darrell (1994). «A genetic algorithm tutorial». Statistics and Computing 4 (2): 65-85. doi:10.1007/BF00175354. 

•   Datos: Q17013331