¿Por qué la solución factible en programación lineal es una solución factible básica, pero la solución factible básica no es necesariamente una solución factible?
Una solución factible es una solución que satisface las condiciones de restricción; la solución básica corresponde al vector base en el que las variables no básicas son cero, y la solución básica no es necesariamente la solución básica factible; la solución básica factible no es necesariamente la solución básica, es básicamente factible. La solución que es la solución básica es la solución básica factible, y la solución óptima es la solución que optimiza la función objetivo en la solución básica factible.
En problemas de programación lineal, la solución básica que satisface restricciones no negativas se denomina solución básica factible o solución básica factible. Si existe una solución factible para un problema de programación lineal, entonces debe haber una solución básica factible. Las condiciones suficientes para que una solución factible se convierta en una solución factible básica son las siguientes:
Los vectores columna correspondientes a los componentes distintos de cero en la matriz de coeficientes son linealmente independientes. Las soluciones factibles básicas corresponden a polos en la región factible y son finitas. Si existe una solución óptima acotada, entonces al menos una solución básica factible es la solución óptima.
Extensión:
.p>Una solución básica factible es una solución que satisface tanto la ecuación de restricción como las restricciones variables no negativas.
Según las diferentes características de los problemas de programación lineal, la adquisición de soluciones factibles básicas iniciales se puede dividir en las dos situaciones siguientes:
1. restricciones sobre la restricción de desigualdad variable ≤ Todas las restricciones y todos los elementos en el vector constante correspondiente son positivos, entonces, siempre que se introduzcan y utilicen variables de holgura como variables básicas, la solución obtenida naturalmente es la solución básica factible.
2. Si se agregan variables distintas de las restricciones no negativas a las restricciones de la ecuación, que son similares a las variables de holgura y se denominan variables artificiales, puede introducir cada restricción de la ecuación y luego crear un problema de programación auxiliar. Al resolver el problema de programación auxiliar, se puede obtener una solución básica factible.
El método de eliminación se utiliza para convertir entre soluciones básicas factibles. Preste atención a los siguientes problemas durante la conversión:
1. El valor de la función objetivo de la solución obtenida después de la conversión debe disminuir. Si la disminución es mayor, esta condición se denomina condición de optimización.
2. La solución transformada sigue siendo básicamente factible, es decir, el valor del término constante es mayor o igual a cero. Esta condición se denomina condición no negativa.
3. Juicio de solución óptima.
La transformación que satisface las condiciones anteriores consiste fundamentalmente en encontrar una primitiva de transformación adecuada en el elemento de la matriz correspondiente a la variable no básica.