Región factible

En optimización matemática y ciencias de la computación, una región factible, conjunto factible o espacio de soluciones es el conjunto de todos los puntos posibles (conjuntos de valores de las variables de elección) de un problema de optimización que satisfacen las restricciones del problema, que pueden incluir desigualdades, igualdades y restricciones de números enteros. Este es el conjunto inicial de soluciones candidatas al problema, antes de que se haya reducido el conjunto de soluciones candidatas.

Por ejemplo, considere el problema de minimizar la función ${\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 (x, Sí.) en el cual el valor de x es al menos 1 y al menos 10 y el valor Sí. al menos 5 y al menos 12. El conjunto factible del problema está separado de la función objetiva, que establece el criterio para ser optimizado y que en el ejemplo anterior es ${\displaystyle x^{2}+y^{4}$

En muchos problemas, el conjunto factible refleja una restricción según la cual una o más variables deben ser no negativas. En problemas de programación entera pura, el conjunto factible es el conjunto de números enteros (o algún subconjunto de ellos). En 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.

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

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

Los conjuntos factibles pueden ser acotados o no acotados. Por ejemplo, el conjunto factible definido por el conjunto de restricciones {x ≥ 0, y ≥ 0} no es acotado porque en algunas direcciones no hay límite a la distancia que se puede recorrer y aún así estar en la región factible. Por el contrario, el conjunto factible formado por el conjunto de restricciones {x ≥ 0, y ≥ 0, x + 2y ≤ 4} es acotado porque la extensión del movimiento en cualquier dirección está limitada por las restricciones.

En problemas de programación lineal con n variables, una condición necesaria pero no suficiente para que el conjunto factible esté acotado es que el número de restricciones sea al menos n + 1 (como lo ilustra el ejemplo anterior).

Si el conjunto factible no tiene límites, puede haber o no un óptimo, dependiendo de las particularidades de la función objetivo. Por ejemplo, si la región factible está definida por el conjunto de restricciones {x ≥ 0, y ≥ 0}, entonces el problema de maximizar x + y no tiene un óptimo, ya que cualquier solución candidata puede mejorarse incrementando x o y; sin embargo, si el problema es minimizar x + y, entonces hay un óptimo (específicamente en (x, y) = (0, 0)).

En optimización y otras ramas de las matemáticas, y en algoritmos de búsqueda (un tema de la informática), una solución candidata es un miembro del conjunto de soluciones posibles en la región factible de un problema dado. Una solución candidata no tiene por qué ser una solución probable o razonable para el 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 quedan excluidas de ahí 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 soluciones posibles que satisfacen las restricciones del problema. La satisfacción de las restricciones es el proceso de encontrar un punto en el conjunto factible.

En el caso del algoritmo genético, las soluciones candidatas son los individuos de la población que evoluciona mediante el algoritmo.

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 iguala a cero, y todos los valores de la variable de elección que satisfacen esta ecuación se consideran soluciones candidatas (mientras que los que no la satisfacen se descartan como candidatos). Hay varias formas en las que una solución candidata podría no ser una solución real. En primer lugar, podría dar un mínimo cuando se busca un máximo (o viceversa), y en segundo lugar, podría no dar 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 el ascenso o descenso local 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 óptima localmente. En tercer lugar, una solución candidata puede ser un óptimo local pero no un óptimo global.

Al tomar antiderivados de monomiales de la forma ${\displaystyle x^{n}$ la solución candidata usando la fórmula de cuadratura de Cavalieri sería ${\fnMicroc} {1}{n+1}x^{n+1}+C}$ Esta solución candidata es en realidad correcta excepto cuando ${\displaystyle n=-1.$

En el método símplex 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 la óptima, se considera un vértice adyacente como la siguiente solución candidata. Este proceso continúa hasta que se encuentra una solución candidata que es la óptima.