Observaciones generales Teoría del método símplex

Aunque las páginas anteriores describen la esencia del método símplex revisado, debe hacerse notar que se puede efectuar modificaciones menores que mejoran la eficiencia de su ejecución en una computadora. Por ejemplo, B^-1 puede obtenerse como el producto de las matrices E anteriores. Esta modificación requiere sólo el almacenamiento de la columna n de E y el número de la columna, en lugar de toda la matriz B^-1 en  cada iteración. Esta forma de producto de la inversa de la base puede ser la más eficaz si se tiene que usar una cinta magnética en lugar de la memoria para almacenar.

También debe observarse que la presentación anterior se limitó al caso de problemas de programación lineal que se ajustan a nuestra forma estándar dada la seccion 3.2, pero las modificaciones para otras formas son relativamente sencillas. El paso inicial se llevará a cabo de manera idéntica que para el méetodo símplex original. Cuando este paso comprende la introducción de variables originales para obtener una solución inicial básica factible (y por lo tanto para obtener la matriz idéntico como matriz base inicial), estas variables deben incluirse en los m elementos de xs.

Ahora se hará un resumen de las ventajas que tiene el método símplex revisado sobre el original. Una de ellas es que puede reducirse el número de cálculos aritméticos. Esto es válido en especial cuando la matriz A contiene un gran número de elementos iguales a cero (lo que por lo general ocurre con los problemas de gran escala que surgen en la práctica). La cantidad de información que se tiene que almacenar es menor, algunas veces mucho menor. El método símplex revisado también permite el control de los errores de redondeo que inevitablemente se generan en una computadora digital. Este control se puede ejercer al obtener en forma periódica la matriz B^-1 directamente de la inversa de B. Aún más, algunos de los problemas del análisis posóptimo que se presentaron en la sección 4.7 se pueden manejar mejor con este método. Por todas estas razones, en general se prefiere el método símplex revisado cuando se corre en una computadora.

Resumen del método símplex revisado (VI) Iteración 2

Con estos coeficientes de las variables no básicas, la siguiente iteración comienza por identificar x1 como la variable básica entrante. Para determinar la variable básica que sale se deben calcular los otros coeficientes de x1:

Como ambos coeficientes (3/2 y 1) son no negativos, la solución actual (x1 = 2, x2 = 6, x3 = 2, x4 = 0, x5 = 0) es óptima y termina el procedimiento.

Resumen del método símplex revisado (V)

Para probar si esta solución es óptima se calculan los coeficientes de las variables no básicas (x1 y x4) en la ecuación (0). Al realizar nada más las partes relevantes de la multiplicación de matrices, se tiene:

de manera que los coeficientes de x1 y x4 son -3 y 5/2 respectivamente. Como x1 tiene coeficiente negativo, esta solución no es óptima.

Resumen del método símplex revisado (IV)

Ejemplo. Para ilustrar el método símplex revisado se aplicará al problema de la Wyndor Glass Co. Las variables básicas iniciales son las variables de holgura.

Resumen del método símplex revisado (III)

Recuérdese que el nuevo conjunto de ecuaciones [se excluye la ecuación (0)] se puede obtener a partir del conjunto precedente si se resta la ecuación (r) multiplicada por aik/ark de la ecuación (i), para toda i = 1,2,.....m excepto i = r y después se divide la ecuación (r) por ark. Por tanto, el elemento de B^-1 que corresponde al renglón i y la columna j es

Resumen del método símplex revisado (II)

En la parte 3 del paso iterativo, B^-1 se puede obtener cada vez usando una rutina estándar de computadora para invertir matrices. Sin embargo, como B (y por lo tanto B^-1) cambia tan poco de una iteración a otra, resulta mucho más eficiente obtener la nueva B^-1 (denotada por B(nueva)^-1 a partir de la B^-1 de la iteración anterior (denotada por B^(antigua)-1. (Si se trata de la solución básica factible inicial, B = I = B^-1.) El método para hacer esta derivación se basa directamente en la interpretación de los elementos de B^-1 (los coeficientes de las variables de holgura en las ecuaciones 1,2,....,m actuales) que se presentará en la siguiente sección, así como en el procedimiento usado por el método símplex original para obtener el nuevo conjunto de ecuaciones a partir del anterior.

Para describir formalmente este método, sea:
xk = variable básica entrante,
aik = coeficiente de xk en la ecuación (i) actual, para i = 1,2,....,m (calculado en la parte 2 del paso iterativo)
r = número de ecuaciones que contienen la variable básica que sale.

Resumen del método símplex revisado (I)

1. Paso inicial: el mismo que para el método símplex original
2. Paso iterativo: Parte 1: determinar la variable básica entrante: igual que para el método símplex original. Parte 2: determinar la variable básica que sale: igual que para el método símplex original, pero se calculan sólo los números que se necesitan para hacerlo [los coeficientes de la variable básica entrante en todas las ecuaciones menos la ecuación (0), y después, para cada coeficiente estrictamente positivo, se calcula el lado derecho de esa ecuación]. Parte 3: determinar la nueva solución básica factible: obtener B^-1 y el conjunto XB = B^-1b. (El cálculo de XB es opcional a menos que la prueba de optimalidad encuentre que es óptima.)
3. Prueba de optimalidad: igual que para el método símplex original, excepto que se calculan sólo los números necesarios para realizar esta pueba, a saber, los coeficientes de las variables no básicas en la ecuación (0).