¿Un valor no nulo de las variables artificiales, tras aplicar el método simplex, muestra una solución no factible?

Question

En la programación lineal a veces utilizamos variables artificiales para el método simplex cuando las restricciones se expresan como igualdades. Después de un cierto número de iteraciones del método simplex llegamos a un punto en el que todos los coeficientes son no negativos. ¿Qué indica un valor no nulo de la variable artificial en ese punto? ¿Solución inviable? ¿Error en el cálculo? ¿Podrías ilustrarlo con un ejemplo?

Edición: Este es un ejemplo. Tabla inicial simplex a la derecha. Comienzo el método simplex eligiendo la variable de entrada-salida y me detengo si no hay coeficientes negativos en la última fila. ¿Qué significa un valor no nulo para la variable artificial en este punto?

Answer 1

Tengo entendido que se hace una primera pasada de optimización con un función objetivo que maximiza el negativo de las variables artificiales . Si estas variables artificiales se ponen a cero a partir de esa pasada, entonces el problema es factible, y se puede entonces eliminarlas y continuar con una segunda pasada utilizando la función objetivo real. Si las variables artificiales no son cero (después de esa primera pasada) entonces el problema original no era factible. (Creo que algunos textos describen esto como Fase I y Fase II).

(Nótese que en CLRS (el libro de texto), en lugar de variables artificiales, prescribe sustituir una restricción de igualdad $ax=b$ con dos restricciones de desigualdad que se contraponen $ax\le b$ y $-ax \le -b$ )