En la teoría de la programación lineal , una solución básica factible ( BFS ) es una solución con un conjunto mínimo de variables distintas de cero. Geométricamente, cada BFS corresponde a una esquina del poliedro de soluciones factibles. Si existe una solución óptima, entonces existe un BFS óptimo. Por lo tanto, para encontrar una solución óptima, es suficiente considerar los BFS-s. Este hecho es utilizado por el algoritmo simplex , que esencialmente viaja de un BFS a otro hasta que se encuentra uno óptimo. [1]
Definición
Para definir un BFS, primero presentamos el programa lineal en la denominada forma de ecuación :
- maximizar
- sujeto a y
dónde:
- y son vectores de tamaño n (el número de variables);
- es un vector de tamaño m (el número de restricciones);
- es una matriz m por n ;
- significa que todas las variables son no negativas.
Cualquier programa lineal se puede convertir en una forma de ecuación agregando variables de holgura .
Como paso de limpieza preliminar, verificamos que:
- El sistema tiene al menos una solución (de lo contrario, todo el LP no tiene solución y no hay nada más que hacer);
- Todas las m filas de la matrizson linealmente independientes, es decir, su rango es m (de lo contrario, podemos eliminar filas redundantes sin cambiar el LP).
Normalmente m < n , por lo que el sistematiene muchas soluciones; cada una de estas soluciones se denomina solución factible del LP.
Sea B un subconjunto de m índices de {1, ..., n }. Denotamos porla matriz cuadrada m -por- m hecha de las m columnas deindexado por B . Sino es singular , las columnas indexadas por B son una base del espacio de columna de. En este caso, llamamos B una base del LP. Dado que el rango dees m , tiene al menos una base; desdetiene n columnas, tiene como máximo bases.
Dada una base B , decimos que una solución factiblees una solución básica factible con base B si todas sus variables distintas de cero están indexadas por B , es decir, para todas.
Propiedades
1. Un BFS está determinado solo por las restricciones del LP (la matriz y el vector ); no depende del objetivo de optimización.
2. Por definición, un BFS tiene como máximo m variables distintas de cero y al menos n - m variables cero. Un BFS puede tener menos de m variables distintas de cero; en ese caso, puede tener muchas bases diferentes, todas las cuales contienen los índices de sus variables distintas de cero.
3. Una solución viable es básico si-y-solo-si las columnas de la matriz son linealmente independientes, donde K es el conjunto de índices de los elementos distintos de cero de. [1] : 45
4. Una BFS está determinada de forma única por la base B : para cada base B de m índices, hay como máximo una BFScon base B . Esto es porque debe satisfacer la restricción , y por definición de base la matriz no es singular, por lo que la restricción tiene una solución única. Lo contrario no es cierto: cada BFS puede provenir de muchas bases diferentes.
Si la solución única de satisface las restricciones de no negatividad, entonces la base se denomina base factible .
5. Si un programa lineal tiene una solución óptima (es decir, tiene una solución factible y el conjunto de soluciones factibles está acotado), entonces tiene una BFS óptima. Esto es una consecuencia del principio máximo de Bauer : el objetivo de un programa lineal es convexo; el conjunto de soluciones factibles es convexo (es una intersección de hiperespacios); por tanto, el objetivo alcanza su máximo en un punto extremo del conjunto de soluciones factibles.
Dado que el número de BFS-s es finito y está limitado por , se puede encontrar una solución óptima para cualquier LP en un tiempo finito simplemente evaluando la función objetivo en todos BFS-s. Ésta no es la forma más eficaz de resolver un LP; el algoritmo simplex examina los BFS-s de una manera mucho más eficiente.
Ejemplos de
Considere un programa lineal con las siguientes restricciones:
La matriz A es:
Aquí, m = 2 y hay 10 subconjuntos de 2 índices, sin embargo, no todos son bases: el conjunto {3,5} no es una base ya que las columnas 3 y 5 son linealmente dependientes.
El conjunto B = {2,4} es una base, ya que la matriz no es singular.
El BFS único correspondiente a esta base es .
Interpretación geométrica
El conjunto de todas las soluciones factibles es una intersección de hiperespacios . Por tanto, es un poliedro convexo . Si está acotado, entonces es un politopo convexo .
Cada BFS corresponde a un vértice de este politopo. [1] : 53–56
Aplicación en el algoritmo Simplex
El algoritmo simplex mantiene, en cada punto de su ejecución, una "base actual" B (un subconjunto de m de n variables), un "BFS actual" y un "cuadro actual". El cuadro es una representación del programa lineal donde las variables básicas se expresan en términos de las no básicas: [1] : 65
Si todos los coeficientes en son negativos, entonces es una solución óptima, ya que todas las variables (incluidas todas las variables no básicas) deben ser al menos 0, por lo que la segunda línea implica .
Si algunos coeficientes en son positivos, entonces es posible aumentar el objetivo de maximización. Por ejemplo, si no es básico y su coeficiente en es positivo, luego aumentarlo por encima de 0 puede hacer más grande. Si es posible hacerlo sin violar otras restricciones, entonces la variable aumentada se vuelve básica ("ingresa a la base"), mientras que otra variable no básica se reduce a 0 para mantener las restricciones de igualdad y, por lo tanto, se vuelve no básica ( "sale de la base").
Si este proceso se realiza con cuidado, entonces es posible garantizar que aumenta hasta que alcanza la BFS óptima.