Hispanopedia Wiki
Articulo de referencia

Región factible

Un problema con cinco restricciones lineales (en azul, incluyendo las restricciones de no negatividad). En ausencia de restricciones enteras, el conjunto factible es toda la reg...

Hispanopedia WikiContenido en espanolLectura gratuita
Un problema con cinco restricciones lineales (en azul, incluyendo las restricciones de no negatividad). En ausencia de restricciones enteras, el conjunto factible es toda la región delimitada por el color azul, pero con restricciones enteras es el conjunto de puntos rojos.
Una región factible cerrada de un problema de programación lineal con tres variables es un poliedro convexo .

En optimización matemática e informática , una región factible, un conjunto factible o un 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 enteras . [ 1 ] Este es el conjunto inicial de soluciones candidatas al problema, antes de que se haya reducido el conjunto de candidatas.

Por ejemplo, consideremos el problema de minimizar la funciónincógnita2+y4{\displaystyle x^{2}+y^{4}}con respecto a las variablesincógnita{\displaystyle x}yy,{\displaystyle y,}sujeto a1≤incógnita≤10{\displaystyle 1\leq x\leq 10}y5≤y≤12.{\displaystyle 5\leq y\leq 12.\,}Aquí, el conjunto factible es el conjunto de pares ( x , y ) en los que el valor de x es al menos 1 y como máximo 10 y el valor de y es al menos 5 y como máximo 12. El conjunto factible del problema es independiente de la función objetivo , que establece el criterio a optimizar y que en el ejemplo anterior esincógnita2+y4.{\displaystyle x^{2}+y^{4}.}

En muchos problemas, el conjunto factible refleja una restricción que establece que una o más variables deben ser no negativas. En problemas de programación entera pura, el conjunto factible es el conjunto de los números enteros (o algún subconjunto del mismo). 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 cuyos vértices son esquinas .

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

Conjunto factible convexo

Un conjunto factible convexo es aquel en el que un segmento de recta 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 debe minimizarse, 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 .

No hay un conjunto factible

Si las restricciones de un problema de optimización son mutuamente contradictorias, no existen 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 .

Conjuntos factibles acotados y no acotados

Un conjunto factible acotado (arriba) y un conjunto factible no acotado (abajo). El conjunto de abajo se extiende infinitamente hacia la derecha.

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 está acotado porque en algunas direcciones no hay límite en la distancia que se puede recorrer sin salirse de la región factible. En cambio, el conjunto factible formado por el conjunto de restricciones { x ≥ 0, y ≥ 0, x + 2y ≤ 4} está acotado porque la amplitud del movimiento en cualquier dirección está limitada por las restricciones.

En los problemas de programación lineal con 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 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 está definida por el conjunto de restricciones { x ≥ 0, y ≥ 0}, entonces el problema de maximizar x + y no tiene óptimo, ya que cualquier solución candidata puede mejorarse aumentando x o y ; sin embargo, si el problema es minimizar x + y , entonces existe un óptimo (específicamente en ( 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 de la informática ), una solución candidata es un miembro del conjunto de posibles soluciones en la región factible de un problema dado. [ 2 ] Una solución candidata no tiene por qué 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 diversos 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 demás soluciones factibles se excluyen como candidatas.

El espacio de todas las soluciones candidatas, antes de excluir cualquier punto factible, se denomina región factible, conjunto factible, espacio de búsqueda o espacio de soluciones. [ 2 ] 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.

Algoritmo genético

En el caso del algoritmo genético , las soluciones candidatas son los individuos de la población que está evolucionando mediante el algoritmo. [ 3 ]

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 iguala a cero, y cualquier valor de la(s) variable(s) de elección que satisfaga(n) esta ecuación se considera una solución candidata (mientras que los que no la satisfacen se descartan como candidatas). Hay varias maneras en que una solución candidata puede no ser una solución real. Primero, puede dar un mínimo cuando se busca un máximo (o viceversa), y segundo, puede 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. Dichas soluciones candidatas pueden descartarse utilizando la prueba de la segunda derivada , cuya satisfacción es suficiente para que la solución candidata sea al menos localmente óptima. Tercero, una solución candidata puede ser un óptimo local pero no un óptimo global .

Al tomar antiderivados de monomios de la formaincógnitanorte,{\displaystyle x^{n},}La solución candidata utilizando la fórmula de cuadratura de Cavalieri sería:1norte+1incógnitanorte+1+do.{\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.}Esta solución candidata es de hecho correcta excepto cuandonorte=−1.{\displaystyle n=-1.}

Programación lineal

Una serie de restricciones de programación lineal sobre dos variables generan una región de valores posibles para dichas variables. Los problemas resolubles de dos variables tendrán una región factible con forma de polígono simple convexo si esta es acotada. En un algoritmo que prueba puntos factibles secuencialmente, cada punto probado es, a su vez, una solución candidata.

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

Referencias

  1. ↑ Beavis, Brian; Dobbs, Ian (1990). Optimisation and Stability Theory for Economic Analysis . Nueva York: Cambridge University Press. pág.  32. ISBN 0-521-33605-8.
  2. 1 2 Boyd, Stephen; Vandenberghe, Lieven (2004-03-08). Optimización convexa . Cambridge University Press. doi : 10.1017/cbo9780511804441 . ISBN 978-0-521-83378-3.
  3. ↑ Whitley, Darrell (1994). "Un tutorial sobre algoritmos genéticos" (PDF) . Statistics and Computing . 4 (2): 65– 85. doi : 10.1007/BF00175354 . S2CID 3447126 .