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.