Esencia de la teoría de dualidad (I)

Al usar nuestra forma estándar para el problema primal, que se muestra a la izquierda (tal vez después de hacer la conversión de una a otra forma), su problema dual tiene la forma que se muestra a la derecha.

Teoría de dualidad y análisis de sensibilidad

Uno de los descubrimientos más importantes durante el desarrollo inicial de la programación lineal fue el concepto de dualidad y sus muchas e importantes ramificaciones. Este descubrimiento reveló que, asociado a todo problema de programación línea, existe otro problema lineal llamado dual. Las relaciones entre el problema dual y el original (llamado primal) son extremadamente útiles en una gran variedad de situaciones. Por ejemplo,se verá que de hecho la solución óptima del problema dual es la que proporciona los precios sombra que se describieron en la seccion 4.7. En este capítulo se presentarán muchas otras aplicaciones valiosas.

Uno de los papeles clave que juega la teoría de dualidad es la interpretación y realización del análisis de sensibilidad. Como ya se mencionó en las secciones 2.3, 3.3 y 4.7, el análisis de sensibilidad consitituye una parte muy importante en casi todos los estudios de programación lineal. Dado que algunos o todos los valores de los parámetros que se emplean en el modelo original son sólo estimaciones de condiciones futuras, es necesario investigar el efecto que se tendría sobre la solución óptima en caso de que prevalecieran otras condiciones. Aún más, ciertos valores de estos parámetros (como la cantidad de recursos) pueden representar decisiones de la gerencia, en cuyo caso su elección debe ser el punto más importante de la investigación y, por supuesto, se estudia a través del análisis de sensibilidad.

Para mayor claridad de exposición, las tres primeras secciones presentan la teoría de dualidad bajo la suposición de que el problema primal de programación líneal está en nuestra forma estándar (pero sin restricción de que las bi deben ser positivas). Más adelante, en la sección 6.4 se analizan otras formas. El capítulo comienza con una introducción de la esencia de la teoría de dualidad y sus aplicaciones. Después se describe la interpretación económica del problema dual (Sec. 6.2) y se profundiza en las relaciones entre el problema primal y el dual (Sec. 6.3). La sección 6.5 hace hincapié en la importancia de la teoría de dualidad para el análisis de sensibilidad. El procedimiento básico para el análisis de sensibilidad (que se basa en la idea fundamental de la sección 5.3) se resume en la sección 6.6 y se ejemplifica en la sección 6.7.

Conclusiones de la Teoría del método símplex

Aunque el método símplex es un procedimiento algebraico, está basado en algunos conceptos geométricos bastante sencillos. Estos conceptos permiten al algoritmo examinar un número relativamente pequeño de soluciones básicas factibles antes de alcanzar e identificar la solución óptima.

El método símplex revisado, proporciona una manera efectiva de adaptar el método símplex para programarlo en una computadora.

La tabla símplex final incluye la información completa para poderla reconstruir algebraicamente a partir de la tabla símplex inicial. Esta idea fundamental tiene aplicaciones muy importantes, en especial en el análisis de posoptimalidad.

Aplicaciones de la idea fundamental (III)

(Si cualquiera de estos nuevos valores fuera negativo y, por lo tanto no factible, entonces se aplicaría la técnica de reoptimización descrita en la sección 4.7, comenzando con esta tabla final revisada.) Al aplicar el análisis incremental a la ecuación anterior de Z* también se obtiene.

La idea fundamental también se puede aplicar a la investigación de otro tipo de cambios en el modelo original de una manera muy parecida; ésta es la parte medular del procedimiento para el análisis de sensibilidad que se describirá en el capítulo 6.

También se podrá observar en el siguiente capítulo que la idea fundamental juega un papel clave en la útil teoría de dualidad par aun problema de programación lineal.

Aplicaciones de la idea fundamental (III)

Pro ejemplo, considérese el cambio de b2=12 a b2=13, tal y como se ilustra en la figura 4.3 para el problema de la Wyndor Glass Co. No es necesario resolver todo el problema para obtener la nueva solución óptima (x1, x2) = (5/3, 13/2) porque la idea fundamental proporciona en seguida los valores de las variables básicas (b*) en la tabla símplex final.

Aplicaciones de la idea fundamental (II)

Otro grupo de aplicaciones en extremo importantes incluye varios de las tareas de posoptimalidad (la técnica de reoptimización, el análisis de sensibilidad y la programación lineal parámetria, descritas en la sección 4.7) que investigan el efecto que causan uno o más cambios en el modelo original. En particular, supóngase que ya se aplicó el método símplex para obtener una solución óptima (inclusive y* y S*)para el modelo original y que estos cambios se hacen después. Cuáles serián los cambios resultantes en la tabla final si se aplicara exactamente la misma secuencia de operaciones algebraicas a la tabla inicial revisada? Como y* y S* no cambian, la idea fundamental revela de inmediato la respuesta.

Aplicaciones de la idea fundamental (I)

La idea fundamental tiene una gran variedad de aplicaciones en programación lineal. Una de ellas influye el método símplex revisado. Según se describió en la sección anterior (véase la tabla 5.7), este método utiliza S* = B^-1 y la tabla símplex inicial para calcular todos los números relevantes de la tabla símplex actual en cada iteración. Va aun más lejos que la idea fundamental al utilizar B^-1 para calcular el mismo y* como y* = cBB^-1

Otra aplicación incluye la interpretación de los precios sombra (y1*, y2*,....,y*m) descritos en la sección 4.7. La idea fundamental revela que Z* (el valor de Z para la solución óptima) es

en el problema de la Wyndor Glass Co. Esta ecuación conduce inmediato a la interpretación de las yi* dada en la sección 4.7.

Resumen matemático de la Teoría del método símplex (VI)

Hasta ahora, la idea fundamental se ha descrito bajo la suposición de que el modelo original se encuentra en nuestra forma estandar dada en la seccion 3.2. No obstante, la lógica matemática anterior revela con exactitud qué ajustes se necesitan para otras formas del modelo original. La clave es la matriz idéntica I en la tabla símplex inicial, misma que se convierte en S* en la tabla símplex final. Si han de introducirse algunas variables artificiales en la tabla símplex inicial para que sirvan de variables básicas iniciales, entonces I en esta tabla símplex está formada por el conjunto de columnas (ordenadas apropiadamente) de todas las variables básicas iniciales (tanto de holgura como artificiales). Las mismas columnas en la tabla símplex final proporcionan S* para la ecuación T* = S*T y y* para la ecuación t* = t + y*T. Si se usara el método de la M con M's en el renglón 0 preliminar como coeficientes de las variables artificiales, entonces la t para la ecuación t* = t + y*T es el renglón 0 de la tabla símplex inicial después de eliminar algebraicamente estos coeficientes distintos de cero de las variables básicas. (De otra manera, el renglón 0 preliminar se puede usar como t pero deben restarse estas M's en el renglón 0 final para obtener y*.)

Resumen matemático de la Teoría del método símplex (V)

Como la componente del centro (o cualquier otra) de estas matrices iguales debe ser la misma, se deduce que M = S* y así la ecuación 2 es válida.

La ecuación 1 se obtiene de manera similar al observar que la serie completa de operaciones algebraicas que incluyen el renglón 0 se reduce a sumar una combinación líneal de los renglones de T a t, lo que es equivalente a sumar a t algún vector multiplicado por T. Si este vector se denota por v, se tiene

t* = t + vT

pero todavía es necesario identificar v. Escribiendo las componentes de t y t* se llega a

Al igualar las componentes centrales de estos dos vectores iguales se tiene v = y*, lo que comprueba la ecuación 1.

Resumen matemático de la Teoría del método símplex (IV)

Estas dos ecuaciones se usaron cuando se describió la iteración 2 para el problema de la Wyndor Glass Co. en la subsección anterior. En particular, el lado derecho de la expresión para el renglón 0 final en la iteración 2 es justo t* + y*T y la segunda línea de la expresión para los renglones finales 1-3 es exacamente S*T.

Se dará ahora un resumen de la lógica matemática que respalda las dos ecuaciones de la idea fundamental. Para derivar la ecuación 2, recuérdese que la serie complete de operaciones algebraicas realizadas por el método símplex (excepto las que involucran el renglón 0) es equivalente a premultiplicar T por alguna matriz, sea ésta M. Por tanto,

T* = MT,

pero ahora es necesario identificar M. Escribiendo las componentes de T y T* esta ecuación T* = MT se convierte en

Resumen matemático de la Teoría del método símplex (III)

Ahora supóngase que se tiene la tabla símplex inicial, t y T, y de la tabla símplex final sólo conocen y* y S*. Existe alguna manera de utilizar esta información para calcular el resto de la tabla final? La tabla 5.7 proporciona la respuesta. Esta tabla incluye una parte de la información que no es directamente valiosa es este planteamiento, a saber como y* y S* se puede calcular (y* = cBB^-1 y S* = B^-1) si se conoce el conjunto actual de variables básicas y, por lo tanto, la matriz base actual B. La parte inferior de esta tabla (que bien puede representar una tabla símplex final o intermedia) también muestra con claridad cómo se puede obtener el resto de la tabla símplex a partir de los coeficientes de las variables de holgura. Esto se resume como sigue:

Idea fundamental

Resumen matemático de la Teoría del método símplex (II)

En cuanto a los coeficientes de las variables de holgura (parte central) en la tabla símplex inicial de la tabla 5.9, obsérvese  el vector nulo 0 en el renglón 0 y la matriz idéntica I abajo, lo que proporciona la clave de la idea fundamental. El vector y la matriz en la misma posición de la tabla símplex final, y* y S*, se juegan entonces un papel importante en las ecuaciones, para la idea fundamental. [Esta matriz se denotó por B^-1 para cualquier tabla símplex en la sección 5.2, ahora S* denota esta matriz en particular sólo para la tabla símplex final, donde la S es la primera letra de la palabra holgura en el idioma inglés  (*slack*).] A y b en la tabla símplex inicial se convierten en A* y b* en la tabla símplex final. Para el renglón 0, los coeficientes de las variables originales son z* - c ( de manera que el vector z* es lo que se ha agregado al vector de coeficientes iniciales, -c) y el lado derecho Z* denota el valor óptimo de Z.

Resumen matemático de la Teoría del método símplex (I)

Como su aplicación más importante incluye una tabla símplex final, se dará ahora una expresión matemática general para la idea fundamental justo en términos de esta tabla, usando la notación matricial. Si no se ha leído la sección 5.2, es necesario saber que los parámetros del modelo están dados por la matriz A = ||aij|| y los vectores b = ||bi|| y c = ||cj||, según es estableció al principio de esa sección.

La notación necesaria que falta se resume e ilustra en la tabla 5.9. Nótese que el vector t (que representa el renglón 0) y la matriz T (que representa los otros renglones) corresponden a los renglones de la tabla símplex inicial en la tabla 5.8 mientras que el vector t* y la matriz T* corresponden a los nuevos renglones de la tabla símplex final. Esta tabla también muestra una partición de estos vectores y matrices en tres partes: los coeficientes de las variables originales, los coeficientes de las variables de holgura (el centro de nuestra atención) y el lado derecho. Una vez más, la notación hace distinción entre las partes de la tabla símplex inicial y la tabla símplex final usando un asterisco en est último caso.

Ejemplo de la idea fundamental- Iteración 2 (V)

Observese de nuevo cómo el vector que premultiplica los renglones 1-3 de la tabla símplex inicial se reproduce exactamente como los coeficientes de las variables de holgura en el renglón 0 final. Estas cantidades deben ser idénticas debido a los coeficientes de las variables de holgura en la tabla símplex inicial (una matriz idéntica abajo de un vector nulo). Esta conclusión es la que corresponde al renglón 0 en la idea fundamental.

Ejemplo de la idea fundamental- Iteración 2 (IV)

Para completar esta historia para el renglón 0, la idea fundamental dice que todo el renglón 0 final se puede calcular a partir de la tabla símplex inicial usando sólo los coeficientes de las variables de holgura en el renglón 0, final, [0, 3/2, 1]. Este cálculo se muestra en seguida, el primer vector es el renglón 0 de la tabla símplex inicial y la matriz la forman los renglones 1-3 de la tabla símplex inicial.

Ejemplo de la idea fundamental- Iteración 2 (III)

Para entender la razón por la que estos multiplicadores de los renglones iniciales son correctos tendrían que revisarse todas las operaciones algebraicas de las dos iteraciones. Por ejemplo, por el renglón 1 final incluye (1/3) del renglón inicial 2, aun cuando nunca se agregó un multiplo de ese renglón 2 al renglón 1? La razón es que el renglón inicial 2 se restó del renglón 3 inicial en la iteración 1 y después (1/3) del renglón 3 antiguo se restó del renglón 1 antiguo en la iteración 2.

Sin embargo, no hay necesidad de averiguar todo esto. Aunque el método símplex haya realizado cientos o miles de iteraciones, los coeficientes de las variables de holgura en la tabla símplex final revelerá en qué forma se obtuvo esta tabla a partir de la tabla símplex inicial. Lo que es más, las mismas operaciones algebraicas darían estos mismos coeficientes aun cuando se cambiaran algunos de los parámetros en el modelo original (tabla símplex inicial), de manera que estos coeficientes también pueden revelar en que forma cambia el resto de la tabla símplex final si se hacen cambios en la tabla inicial.

Ejemplo de la idea fundamental- Iteración 2 (II)

Las primeras dos matrices que se muestran en la primera línea de estos cálculos resumen las operaciones algebraicas de la segunda y primera iteraciones, respectivamente. Su producto se muestra como la primera matriz de la segunda línea y combina las operaciones algebraicas de las dos iteraciones. Obsérvese que esta matriz se reproduce igual como los coeficientes de las variables de holgura en los renglones 1-3 de la nueva tabla símplex (final) que se muestra en la tercera línea. Lo que esta parte de la tabla revela es la forma en que se obtuvo toda la tabla símplex final (excepto el renglón 0) a partir de la tabla símplex inicial, a saber,

renglón 0 final = (1) renglón 1 inicial + (1/3)renglón 2 inicial + (-1/3)renglón3 inicial,
renglón 2 final = (0) renglón 1 inicial + (1/2)renglón 2 inicial + (0)renglón 3 inicial,
renglón 3 final = (0) renglón 1 inicial + (-1/3)renglón 2 inicial + (1/3)renglón 3 inicial,

Ejemplo de la idea fundamental- Iteración 2 (I)

Las operaciones algebraicas realizadas en la segunda tabla símplex de la tabla 5.8 para la iteración 2 son:

renglón 0 nuevo = renglón 0 antiguo + (1) renglón 3 antiguo,
renglón 1 nuevo = renglón 1 antiguo + (-1/3) renglón 3 antiguo,
renglón 2 nuevo = renglón 2 antiguo + (0) renglón 3 antiguo,
renglón 3 nuevo = (1/3) renglón 3 antiguo,

Si por el momento se ignora el renglón tabla símplex como el producto de matrices que se dio en la iteración 1 se obtiene:

Ejemplo de la idea fundamental- Iteración 1 (III)

Nótese que este vector se reproduce exactamente como los coeficientes de las variables de holgura en el renglón 0 de la nueva tabla símplex, tal como se aseguró en la ideal fundamental (Una vez más, la razón es la matriz idéntica para los coeficientes de las variables de holgura en los renglones 1-3 de la tabla inicial, junto con los ceros para esos coeficientes en el renglón de esta tabla.)

Ejemplo de la idea fundamental- Iteración 1 (II)

Obsérvese que esta primera matriz se reproduce exactamente como los coeficientes de las variables de holgura en los renglones 1-3 de la nueva tabla, proque estos coeficientes en la tabla inicial formaban una matriz idéntica. Así, tal como se estableció en la descripción verbal de la idea fundamental, los coeficientes e las variables de holgura en la nueva tabla símplex proporcionan sin duda las operaciones algebraicas realizadas.

Esta idea no es motivo de gran emoción después de sólo una iteración ya que se puede ver directo en la tabla inicial cuáles deben ser estas operaciones, pero se vuelve invaluable una vez que se han realizado todas las operaciones.

Para el renglón 0, la operación algebraica realizada se reduce al siguiente cálculo de matrices, en donde ahora se prestará atención al vector [0,5/2,0] que premultiplica los renglones 1-2 de la tabla símplex inicial

Ejemplo de la idea fundamental- Iteración 1 (I)

Para mostrar la idea fundamental se dirigirá la atención a las operaciones realizadas por el método símplex usando la eliminación gaussiana para obtener la nueva solución básica factible. Si se divide el renglón pivote por el número  pivote al último en lugar de al principio las operaciones algebraicas que se detallaron en el capítulo 4 para la iteración 1 son

renglón 0 nuevo =  renglón 0 antiguo + (5/2) renglón 2 antiguo
renglón 1 nuevo = renglón 1 antiguo + (0) renglón 2 antiguo
renglón 2 nuevo =                            + (1/2) renglón 2 antiguo
renglón 3 nuevo = renglón 3 antiguo + (-1) renglón 2 antiguo

Si por el momento se ignora el renglón 0, estas operaciones algebraicas son lo mismo que premultiplicar los renglones 1-3 de la tabla símplex inicial por la primera matriz que se muestra en seguida

Ejemplo de la idea fundamental

La tabla 5.8 muestra la parte relevante de la tabla símplex para ilustrar esta idea fundamental. Se dibujaron líneas más oscuras alrededor de los coeficientes de las variables de holgura en la segunda y tercerca tablas porque éstos son los coeficientes cruciales para la aplicación de esta idea. Para evitar que se encimen el renglón pivote y la columna pivote se identifican sólo por un cuadro sencillo.

Una idea fundamental Teoría del método símplex (II)

Como ya se describió en la sección anterior, una sucesión de operaciones algebraicas de este tipo es equivalente a permultiplicar la tabla símplex inicial por alguna matriz. La consecuencia se puede resumir como sigue.

Descripción verba, de la idea fundamental. Después de cualquier iteración, los coeficientes de las variables de holgura en cada ecuación revelan de inmediato cómo se obtuvo la ecuación a partir de las ecuaciones iniciales.

Como ejemplo de la importancia de esta idea, recuérdese en la tabla 5.7, que la fórmula matricial que el método símplex obtuvo para la solución óptima es

xB = B^-1b

en donde xB es el vector de variables básicas, B^-1 es la matriz de coeficientes de las variables de hogura para los renglones 1-m de la tabla símplex final y b es el vector original del lado derecho (disponibilidad de recursos). (Más adelante se denotará esta matriz particular B^-1 por S*.) En análisis posóptimo por lo general incluye una investigación de los posibles cambios en b. Si se usa esta fórmula, se puede observar justo cómo cambia la solución básica factible óptima ( o si se convierte en no factible debido a valores negativos de las variables) como una función de b. No es necesario volver a aplicar el método símplex una y otra vez para cada nuevo vector b ya que los coeficientes de las variables de holgura !lo dicen todo! De manera similar, esta idea fundamental proporciona un ahorro computacional enorme para el resto del análisis de sensibilidad.

Para dejar bien claro el por qué y el cómo de esta idea, se observará de nuevo el ejemplo de la Wyndor Glass Co.

Una idea fundamental Teoría del método símplex (I)

En esta sección se hará hincapié en una propiedad del método símplex (en cualquiera de sus formas) que el método símplex revisado puso de manifiesto en la sección anterior. Esta idea fundamental proporciona la clave tanto para la teoría de  dualidad como para el análisis de sensibilidad, dos partes muy importantes de la programación líneal.

La propiedad involucra los coeficientes de las variables de holgura  y la información contienen. Es un resultado directo del paso inicial, en donde se asigna un coeficiente de +1 a la i-esima variable de holgura en la ecuación (i) y cero en todas las demás ecuaciones [incluyendo la ecuación (0)] para i=1,2,......m, como lo muestran el vector nulo 0 y la matriz identica I en la columna de Variables de holgura de la tabla 5.7. El otro factor clave es que las iteraciones subsecuentes  producen cambios en las ecuaciones inciales sólo mediante:

1. la multiplicación de una ecuación completa por una constante distinta de cero, o 
2. la suma de un múltiplo de una ecuación completa a otra ecuación completa

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).