Cálculo del Intervalo de Variación del Lado Derecho que conserva la Base Óptima

Una vez concluidas las iteraciones del Método Simplex y en el caso de alcanzar una solución básica factible óptima, puede resultar de interés determinar un intervalo de variación para un parámetro del vector de los lados derechos de las restricciones que permita conservar la geometría del problema. Esto implica que se conservan las restricciones activas originales en el nuevo escenario (es decir, se mantiene la base óptima) que se genera a partir de la modificación (individual) de un parámetro o coeficiente del lado derecho. Para ilustrar el resultado anterior consideremos el siguiente modelo de Programación Lineal.

Luego de llevar a la forma estándar el modelo anterior agregando , y como las variables de holgura de las restricciones 1, 2 y 3, respectivamente, y aplicar las iteraciones necesarias del Método Simplex, se alcanza la siguiente tabla final (óptima):

La solución óptima es y  con valor óptimo . El valor de las variables de holgura en el óptimo , y es 0, 0 y 20, respectivamente. Luego se puede concluir que la solución óptima del problema se alcanza con las restricciones 1 y 2 activas (notar que sus respectivas holguras con variables no básicas en el óptimo) y la base actual esta conformada por las variables , y .

Sabemos adicionalmente que, por ejemplo, el costo reducido de la variable de holgura  representa el precio sombra asociado a la primera restricción (). No obstante desconocemos en qué intervalo puede variar el parámetro del lado derecho de la restricción 1 (actualmente ) de modo que se conserve la base óptima y por tanto nos permita hacer un correcto uso de la información del precio sombra.

Para ello se propone la siguiente fórmula que permite encontrar el intervalo de variación para un lado derecho que conserva la base óptima:

Max {-bj/yij con yij>0} <= D <= Min {-bj/yij con yij<0}

Por ejemplo determinemos el intervalo para el parámetro :

En consecuencia  puede disminuir en 30 unidades y aumentar en 15 unidades y se conserva la base óptima. Es decir, si se mantiene la base óptima.

El resultado anterior se puede corroborar gráficamente. La solución óptima se encuentra en el vértice C donde las restricciones 1 y 2 son activas (notar la curva de nivel que pasa por el vértice óptimo es la línea punteada de color azul). Si para el lado derecho de la restricción 1 consideramos  se obtiene la línea de color verde y para  la línea de color rojo. En estos casos si bien se modifica el dominio de soluciones factibles, la solución óptima conserva las actuales restricciones activas (y por ende cuando  adopta un valor fuera de este intervalo cambia la geometría del problema o base óptima).

Esto es consistente con el Informe de Confidencialidad de Solver. En particular el reporte de restricciones donde se aprecia el aumento y reducción permisible que conserva la actual base óptima:

Por ejemplo, ¿cuál es el nuevo valor óptimo si el lado derecho de la restricción 1 ahora es ?. Como , entonces . ¿Cuál es la nueva solución óptima?. Como sabemos que se conservan las restricciones activas en el óptimo para la variación propuesta, la solución óptima del nuevo escenario se obtiene simplemente resolviendo el siguiente sistema de ecuaciones (notar que la restricción 1 y 2 se conservan activas):

De donde  y , que al evaluar en la función objetivo se obtiene: corroborando el resultado anterior. Dejamos al lector el desafío de aplicar los conceptos presentados en este articulo para encontrar un intervalo para  y  que conserve la base óptima.