Soluciones basicas

Consideremos el modelo estándar de PL con m ecuaciones y n incógnitas. Una solución básica asociada se determina haciendo n-m variables iguales a cero y luego, resolviendo las ni ecuaciones con las restantes ro variables, siempre que la solución resultante exista y sea única. Para ilustrar esto, consideremos el siguiente sistema de ecuaciones: /

2x + x2 + 4x, + x4 = 2
x1 + 2x, + 1V3 + x4 = 3

En este ejemplo tenemos ni = 2 y n = 4. Entonces, una solución básica está asociada con n — ni 4 — 2 2 variables nulas, Esto significa que el conjunto de ecuaciones dado tiene n!/Íni! (o — ni) = 4!/2!21 = 6 posibles soluciones básicas, Decimos soluciones básicas “posibles” porque algunas combinaciones pueden no conducir en absoluto a soluciones básicas. Por ejemplo, considérese la combinación donde x y x4 se hacen igual a cero. En este caso el sistema se reduce a

2x, + 4x, = 2
x1 + 2x, = 3

Las dos ecuaciones son inconsistentes y, por consiguiente, no existe una solución. 1_a conclusión es que x, y x, no pueden constituir una solución básica y por ello, no corresponden a un punto extremo.
En forma alternativa, consideremos el caso donde x3 y x4 se hacen igual a cero. Esto da las ecuaciones
2x + x, = 2
x1 + 2x, = 3


La solución única correspondiente (x 1/3, x2 4/3), junto con .r, O y x4 = O, define una solución básica y, por lo tanto, un punto extremo del espacio de soluciones de la PL.

En la PL, nos referimos a las n — m variables que se hacen iguales a cero como variables no básicas y, a las no variables restantes como variables básicas (por supuesto, siempre que exista una solución única). Se dice que una solución básica es factible si todos los valores de su solución son no negativos. Un ejemplo de este caso es la solución factible básica (x1 = 1/3, y5 = 4/3, x, O, a4 = O). Para ilustrar el caso de una solución básica infactible, consideremos la combinación donde las variables no básicas son x1 O y x3 = O. Las ecuaciones anteriores dan

4x, + x4 = 2
2x, + .v4 = 3

La solución básica correspondiente es (.r, — /2, a4 4), que es infactible porque x, es negativa.

En la resolución del problema de PL, nos interesarán las soluciones básicas, tanto factibles como infactibles. Específicamente veremos que todas las iteraciones del método símplex primal siempre están asociadas sólo con soluciones básicas factibles. Por otra parte,. el método símplex dual trata con soluciones básicas infactibles hasta la última iteración, donde la solución básica asociada debe ser factible. En esencia, el método símplex primal sólo trata con puntos extremos, en tanto que en el método símplex dual todas las iteraciones, excepto la última, están asociadas con puntos extremos infactibles. Al final, ambos métodos dan soluciones básicas factibles como lo estipula la condición de no negatividad del modelo de PL.