METODO SIMPLEX ANALISIS DE SENSIBILIDAD Y DUALIDAD Análisis de sensibilidad con la tabla simplex El análisis de sensibilidad para programas lineales implica el cálculo de intervalos para los coeficientes de la función objetivo y para los valores de los lados derechos, así como también de los precios sombra y/o duales. Coeficientes de la función objetivo El análisis de sensibilidad para un coeficiente de la función objetivo implica determinar un margen para los valores del coeficiente. A tal gama se le denomina intervalo de optimidad. Mientras el valor del coeficiente de la función objetivo se mantenga dentro del citado margen de optimidad la solución básica factible seguirá siendo óptima. Por ello, para una variable no básica, el intervalo de optimidad define los posibles valores del coeficiente de la función objetivo para los cuales esa variable sigue siendo no básica. Por otro lado, el citado intervalo para una variable básica define los valores de los coeficientes de la función objetivo para los cuales esa variable sigue siendo básica. Al evaluar el intervalo de optimidad para un coeficiente de la función objetivo, se supone que todos los demás coeficientes del problema conservan sus valores originales; en otras palabras, solo se

permite que cambie un coeficiente a la vez. Para ilustrar el proceso de cálculo de los márgenes para los coeficientes de la función objetivo, se plantea el problema de la empresa High Tech: Max Z= 50X1 + 40X2 Sujeto a 3x1 + 5x2 ≤ 150 tiempo de ensamble 1x2 ≤ 20 monitor para portable 8x1 + 5x2 ≤ 300 espacio de almacén X1, x2 ≥ 0 En seguida se reproduce la tabla simplex final del problema de High Tech:

Recuérdese que cuando se utiliza el método simplex para resolver un programa lineal, se reconoce una solución óptima cuando todos los elementos del renglón de evaluación (Cj – Zj) son ≤ 0. Como la tabla simplex anterior satisface este criterio, es óptima la solución que se muestra ahí. Sin embargo, si un cambio en los coeficientes del a función objetivo ocasionara que uno o más valores de Cj – Zj se volviera positivo, entonces la solución ya no sería óptima. Por ello se concluye que el

intervalo de optimidad para un coeficiente de la función objetivo se determina mediante los valores de los coeficientes que conservan Cj – Zj ≤ 0 para todos los valores de j. Para ilustrar la forma en que se determina el intervalo de optimidad, se calcula el intervalo de optimidad para C1, la utilidad por unidad del modelo deskpro. Utilizando C1 (en lugar de 50) como coeficiente de X1 en la función objetivo, la tabla simplex final modificada es la siguiente:

Como los elementos de Cj – Zj correspondientes a las variables básicas siguen siendo 0, la solución actual seguirá siendo optima mientras el valor de C1 dé como resultado Cj – Zj ≤ 0 para las dos variables no básicas S1 y S3. Por ello, se debe tener

y

Utilizando la primera desigualdad: C1 – 64 ≤ 0

De manera similar, se tiene de la segunda desigualdad: 24 - C1 ≤ 0

C1 ≤ 64

24 ≤ C1

Por lo tanto, el intervalo de optimidad está dado por:

24 ≤ C1 ≤ 64

Para ver como la High Tech puede utilizar la información anterior sobre análisis de sensibilidad, supóngase que un aumento en los costos de los materiales reduce a $30 la contribución a las utilidades de la deskpro. El intervalo de optimidad indica que la solución actual (x 1 = 30, x2=12, s2=8) sigue siendo óptima. Para verificar esto, se vuelve a calcular la tabla simplex final después de reducir a 30 el valor de C1.

Como Cj – Zj ≤ 0 para todas las variables, la solución original sigue siendo óptima. Nótese sin embargo, que se presenta una reducción en las utilidades totales. ¿Qué sucedería si se redijera aún más la contribución unitaria a las utilidades, por ejemplo a $20?, con referencia al intervalo de optimidad mencionado para C1, se observa que “20” esta fuera del intervalo; por ello se sabe que un cambio de esa magnitud ocasiona que la óptima sea otra base. Para verificar esto, considérese la modificación de la tabla simplex final anterior, reemplazando C 1 por 20 (en vez de 30).

Como era de esperar, la solución actual (X1=30, X2=12, S2=8) ya no es óptima por que el elemento de la columna S3 del renglón de evaluación neta es mayor que cero. Esto implica que se debe realizar cuando menos una iteración simplex adicional para llegar a la solución óptima. El procedimiento para calcular el intervalo de optimidad para las variables no básicas es aún más sencillo, puesto que un cambio en el coeficiente de la función objetivo de una variable no básica ocasiona que cambie solamente el elemento Cj – Zj de la tabla simplex final.

Para ilustrar este procedimiento se muestra en seguida el cuadro simplex final para el problema original de High Tech después de reemplazar 0, el coeficiente de S1 en la función objetivo, con el coeficiente Cs1

Obsérvese que los únicos cambios que se dan en la tabla están en la columna S1. Al aplicar la desigualdad para calcular en intervalo de optimidad, se tiene: Cs1 – 14/5 ≤ 0

y así:

Cs1 ≤ 14/5

Por lo tanto, mientras el coeficiente de S1 en la función objetivo sea menor o igual a 14/5, la solución seguirá siendo óptima.

Pasos para determinar el intervalo de optimidad Paso1:

Reemplazar el valor numérico del coeficiente de la función objetivo para Xk, con Ck en todos los casos en los que aparezca en la tabla simplex final.

Paso 2:

Si la variable Xk es una variable básica, volver a calcular Cj – Zj para cada variable no básica; si Xk es una variable no básica, solo es necesario volver a calcular Ck – Zk

Paso 3:

Haciendo que Cj – Zj ≤ 0, resolver cada desigualdad a fin de obtener los limites inferior y superior de Ck. Si existen dos o más limites superiores para Ck, el menor de ellos es el límite superior del intervalo de optimidad. Si existen dos o más limites inferiores, el mayor de ellos será el límite inferior del intervalo de optimidad.

Paso 4:

Si el problema original es uno de minimización que se convirtió a uno de maximización para aplicar el método simplex, multiplicar por -1 las desigualdades que se obtienen en el paso 3, y cambiar el sentido de las desigualdades para obtener los intervalos de optimidad para el problema original de minimización.

VALORES DE LOS LADOS DERECHOS En muchos problemas de programación lineal pueden interpretarse los valores de los lados derechos (las bi) como los recursos disponibles. Los precios sombra ofrecen información sobre el valor de los recursos adicionales; los intervalos correspondientes a los valores de los lados derechos determinan los márgenes dentro de los cuales esos precios sombra son válidos. Precios sombra: A los cambios en el valor de la función objetivo por los aumentos unitarios en los valores del lado derecho de las restricciones se les denomina precios sombra. Cuando se utiliza el método simplex para resolver un problema de programación lineal, es fácil obtener los valores de los precios sombra o de sombra. Se encuentran en el renglón Zj de la tabla simplex final. Para ilustrar este punto se tiene la tabla simplex final del problema de High Tech:

Los valores Zj para las tres variables de holgura son 14/5, 0, y 26/5 respectivamente. Por ello, el precio sombra para la restricción de tiempo de ensamble es 14/5 = 2.80, para la restricción de los monitores para la portable es 0.00, y para la restricción de espacio de almacén es 26/5 = 5.20. Para ver por qué son precios sombra los valores de Zj para las variables de holgura de la tabla simplex final, considérese primero el caso de las variables de holgura que son parte de la solución básica factible óptima. Cada una de estas variables de holgura tiene un valor de Zj igual a cero, lo que indica un precio sombra nulo para la restricción correspondiente. Considérense ahora las variables de holgura no básicas, por ejemplo S1. Se determinó que el valor de Zj para la variable S1 es de 14/5 = 2.80 Se puede concluir que $2.80 es el valor que tiene para High Tech una hora de tiempo de ensamble que se utiliza en la producción de computadoras desktop y portable. Por ello, si se puede obtener tiempo adicional, esa empresa debe estar dispuesta a pagar hasta $2.80 por cada hora. Se puede dar una interpretación similar al valor de Zj para cada una de las variables de holgura no básicas. Es decir, Zj es el valor de una unidad adicional del recurso en el renglón correspondiente a esa variable de holgura.

INTERVALO DE FACTIBILIDAD Como se acaba de ver, puede utilizarse el renglón Zj de la tabla simplex final para determinar el precio sombra y, como resultado, pronosticar el cambio que se da en el valor de la función objetivo y que corresponde a un cambio unitario en un valor de bi. Sin embargo, lo que interesa es calcular un intervalo de valores sobre los que pueda variar una b i específica, sin que ninguna de las variables básicas del momento se convierta en no factible. A tal gama de valores se le denomina intervalo de factibilidad. Para ilustrar el efecto de los cambios en bi considérese un aumento en la cantidad disponible de tiempo de ensamble en el problema de la High Tech, de 150 a 160 hrs. ¿la base actual sigue ofreciendo una solución factible? Si la respuesta es sí, dado un precio sombra de $2.80 para la restricción de tiempo de ensamble, puede esperarse un aumento de 10(2.80)= 28, en el valor de la función objetivo. En seguida se muestra la tabla simplex final que corresponde a un aumento de 10 horas en el tiempo de ensamble.

La misma base, que consiste en las variables básicas X2, S2 y X1, es factible porque todas las variables básicas son no negativas. No tese también que, el valor de la solución óptima ha aumentado en 28 (de 1980 a 2008). Los únicos cambios en la tabla simplex final (en comparación con el cuadro simplex final cuando b1=150) son las diferencias en los valores de las variables básicas y el valor de la función objetivo. Es decir, sol ha cambiado la última columna de la tabla simplex. Los elementos de esta nueva columna se obtuvieron simplemente sumando los primeros 4 elementos de la columna S 1, multiplicados por 10, a la última columna de la tabla anterior:

Recuérdese que cada coeficiente de la columna S1 indica la magnitud de la disminución que ocurrirá en la correspondiente variable básica al aumentar S1 en una unidad. El cambio en el valor de la función objetivo que corresponde a un aumento de una unidad en b 1 está dado por el valor de Zj en esa columna (el precio sombra). En el caso anterior, se aumentó en 10 unidades la disponibilidad del tiempo de ensamble; por ello, se multiplicaron por 10 los primeros 4 elementos de la columna S1 con el objeto de obtener el cambio en el valor de la solución. ¿Cómo se sabe cuándo un cambio en b1 es tan grande que la base en cuestión se vuelve no factible?, se responde a esta pregunta específicamente para el problema de High Tech: Se comenzara mostrando como se calculan los límites superior e inferior para la cantidad máxima en que puede cambiar b1 antes de que la base óptima se vuelva no factible. Ya se ha visto el modo de encontrar los nuevos valores básicos factibles de la solución, para un aumento de 10 unidades en b 1. En general, dado un cambio de ∆b1 en b1, los nuevos valores de las variables básicas del problema de la High Tech están dados por

Mientras el nuevo valor de las variables básicas siga siendo no negativo, la base sigue siendo factible, y por lo tanto, optima. Se puede hacer que las variables básicas sigan siendo no negativas limitando el cambio en b1 (es decir ∆b1), de manera que se satisfaga cada una de las siguientes condiciones:

Obsérvese que los lados izquierdos de las desigualdades anteriores representan los nuevos valores de las variables básicas después de que ha variado b1 ∆b1 Despejando ∆b1 en las desigualdades anteriores, se obtiene:

Como deben satisfacerse las tres desigualdades, se deben satisfacer también los límites más estrictos que tenga b1, para que todas las variables básicas sigan siendo no negativas. Por ello, ∆b1 debe satisfacer -37.5 ≤ ∆b1 ≤ 25 El tiempo inicial disponible de ensamble era 150 horas. Por ello, b1 = 150 + ∆b 1 , en donde b1 es la cantidad disponible de tiempo de ensamble. Se suma 150 a cada uno de los tres términos de la expresión anterior para obtener: 112.5 ≤ 150 + ∆b1 ≤ 175 Reemplazando 150 + ∆b1 por b1 se obtiene el intervalo de factibilidad para b1: 112.5 ≤ b1 ≤ 175 Este intervalo indica que mientras el tiempo disponible de ensamble se mantenga entre 112.5 y 175 horas, la base óptima en cuestión sigue siendo factible. Es por esto que se denomina a esta gama el intervalo de factibilidad.