SENCIBILIDAD Y DUALIDAD

3._SENCIBILIDAD Y DUALIDAD

TEORÍA

Siguiendo la notación utilizada en la sección dedicada al Método Simplex en nuestro sitio, éste opera para modelos de Programación Lineal en un formato estándar.

Min cTx

s.a Ax = b

x >= 0

Donde la tabla final del Método mantiene la siguiente estructura:

• Donde:

• I: Matriz Identidad

• 0: Costos reducidos asociados a las variables básicas

• B: Matriz de variables básicas

• D: Matriz de variables no básicas

• b: Lado derecho

• Cb: Coeficientes en la función objetivo asociados a las variables básicas

• Cd: Coeficientes en la función objetivo asociados a las variables no básicas

1. Cambio en el "lado derecho" de las restricciones: Lo que se busca identificar si las actuales variables básicas se mantienen luego de la modificación de uno o más parámetros asociados al "lado derecho" del modelo. Si calculamos:

y se cumple , Las mismas variables básicas lo son también de la nueva solución óptima, calculada con el nuevo . Si lo anterior no se cumple, se puede aplicar el Método Simplex Dual.

EJEMPLO: Sin resolver nuevamente el problema, se desea saber si las actuales variables básicas óptimas del problema también lo son del mismo problema, donde los lados derechos corresponde al vector b=(20,30). (Observación: X4 y X5 son variables de holgura de la restricción 1 y 2 respectivamente)

Max 2x1 + 7x2 - 3x3

sa: x1 + 3x2 + 4x3 <= 30

x1 + 4x2 - x3 <= 10

x1,x2,x3 >= 0

X1 X2 X3 X4 X5

0 -1 5 1 -1 20

1 4 -1 0 1 10

0 1 1 0 2 20

Para analizar este escenario debemos calcular el vector de variables básicas y verificar si todos sus componentes son positivos definidos. Nótese que para esto necesitamosla matriz B inversa, la cual fácilmente podemos rescatar identificando los parametros asociados a X4 y X5 (variables de holgura de la restricción 1 y 2 respectivamente) en la tabla final del Método Simplex:

Luego, dado que al menos uno de los coeficientes del nuevo lado derecho tiene un valor negativo, cambia la actual base óptima. Cabe destacar que ante esta situación no es necesario resolver el nuevo escenario partiendo de cero, sino lo que se debe hacer es utilizar la tabla final del simplex del escenario base, actualizando el lado derecho y valor de la función objetivo.

X1 X2 X3 X4 X5

0 -1 5 1 -1 -10

1 4 -1 0 1 30

0 1 1 0 2 60

Posteriormente, se continua iterando haciendo uso del Método Simplex Dual. (Ver referencia a la derecha).

2. Inclusión de una nueva variable: Debemos evaluar si la nueva variable es un aporte significativo a los resultados del modelo original. Luego, para decir si la actual solución básica es óptima para el nuevo problema, calculamos el costo reducido de la nueva variable como:

donde k es el índice de la nueva variable y Ak su respectiva columna en la matriz de coeficientes. Si se cumple que rk>=0 se conserva la actual solución óptima. En caso contrario, se puede seguir con el Simplex agregando a la tabla una nueva columna con entradas B-1Ak y rk y tomando como variable entrante a la nueva base la que acabamos de introducir

...