Región factible
Región factible (también conjunto de soluciones factibles o conjunto factible, en inglés Feasible region, feasible set) — en investigación de operaciones, optimización y modelado matemático, es el conjunto de todas las posibles soluciones (conjuntos de valores de las variables) que satisfacen todas las restricciones impuestas al problema.
La región factible representa el subespacio en el que se busca la solución óptima. Cualquier solución que se encuentre fuera de esta región se considera no factible.
Definición y formación
La región factible se forma como la intersección de los conjuntos definidos por cada una de las restricciones del problema. Las restricciones pueden presentarse en forma de:
- Desigualdades: Establecen límites superiores o inferiores para los valores de las variables o sus combinaciones (por ejemplo, "el consumo del recurso A no debe exceder las 100 unidades", "la cantidad de producto fabricado debe ser de al menos 50 unidades").
- Igualdades: Requieren el cumplimiento exacto de una condición (por ejemplo, "el volumen total de transporte debe ser igual a 1000 toneladas", "el balance de flujos de entrada y salida es igual a cero").
- Condiciones sobre el signo de las variables: A menudo, las variables deben ser no negativas, enteras o pertenecer a un conjunto discreto específico.
Un punto (o un vector de valores de las variables) pertenece a la región factible si y solo si satisface simultáneamente todas estas restricciones.
Interpretación geométrica
La región factible a menudo tiene una interpretación geométrica clara, especialmente en problemas con un número reducido de variables:
- En el espacio bidimensional (2 variables): Cada restricción lineal de tipo desigualdad define un semiplano. La región factible es la intersección de estos semiplanos, formando un polígono convexo (posiblemente no acotado o vacío).
- En el espacio tridimensional (3 variables): Cada restricción lineal de tipo desigualdad define un semiespacio. La región factible es la intersección de estos semiespacios, formando un poliedro convexo.
- En el espacio multidimensional: La región factible definida por restricciones lineales es un politopo convexo.
En el caso de restricciones no lineales, la región factible puede tener una forma más compleja y no ser convexa.
Papel en la optimización
La región factible desempeña un papel fundamental en la optimización:
- Definición del espacio de búsqueda: La solución óptima del problema (si existe) se encuentra siempre dentro de la región factible o en su frontera. Los algoritmos de optimización buscan el extremo de la función objetivo precisamente en esta región.
- Verificación de la existencia de soluciones: Si la región factible es un conjunto vacío (es decir, las restricciones son contradictorias), el problema no tiene soluciones factibles y, por lo tanto, tampoco una solución óptima.
- Influencia en la solución óptima: La forma y el tamaño de la región factible influyen directamente en la posibilidad de alcanzar un extremo de la función objetivo y en el valor de dicho extremo.
Propiedades de la región factible (en problemas de programación lineal)
En problemas de programación lineal (PL), donde todas las restricciones y la función objetivo son lineales, la región factible posee propiedades importantes:
- Convexidad: Si dos puntos pertenecen a la región factible, todo el segmento de línea que los une también pertenece a la región. Esta propiedad garantiza que la solución óptima (si existe y es única) se encontrará en uno de los vértices del poliedro que define la región factible.
- Cierre: La región factible incluye sus fronteras (debido a las desigualdades no estrictas ≤, ≥ y a las igualdades).
La región factible puede ser:
- Acotada: Tiene dimensiones finitas.
- No acotada: Se extiende infinitamente en una o más direcciones.
- Vacía: No contiene ningún punto.
Bibliografía
- Ventsel E. S. Investigación de operaciones: problemas, principios, metodología. — Moscú: Nauka, 1988.
- Ackoff R., Sasieni M. Fundamentos de la investigación de operaciones. — Moscú: Mir, 1971.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)
Véase también
- Investigación de operaciones
- Optimización
- Modelo matemático
- Restricciones
- Solución factible
- Solución óptima
- Función objetivo
- Programación lineal
- Conjunto convexo