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.

modelo-lineal-cambio-lado-d

Luego de llevar a la forma estándar el modelo anterior agregando x_{3}, x_{4} y x_{5} 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):

tabla-optima-simplex-lado-d

La solución óptima es x_{1}=15x_{2}=40 con valor óptimo V(P)=615. El valor de las variables de holgura en el óptimo x_{3}, x_{4} y x_{5} 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 x_{1}, x_{2} y x_{5}.

Sabemos adicionalmente que, por ejemplo, el costo reducido de la variable de holgura x_{3} representa el precio sombra asociado a la primera restricción (\pi_{1}=1/2). No obstante desconocemos en qué intervalo puede variar el parámetro del lado derecho de la restricción 1 (actualmente b_{1}=180) 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 b_{1}:

intervalo-variacion-lado-de

En consecuencia b_{1} puede disminuir en 30 unidades y aumentar en 15 unidades y se conserva la base óptima. Es decir, si b_{1}\epsilon [150,195] se mantiene la base óptima.

intervalo-parametro-b1

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 b_{1}=150 se obtiene la línea de color verde y para b_{1}=195 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 b_{1} adopta un valor fuera de este intervalo cambia la geometría del problema o base óptima).

intervalo-grafico-lado-dere

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:

informe-lado-derecho-solver

Por ejemplo, ¿cuál es el nuevo valor óptimo si el lado derecho de la restricción 1 ahora es b_{1}=190?. Como b_{1}=190\epsilon[150,195], entonces V(P)=615+\Delta b_{1}\pi _{1}=615+(190-180)*(1/2)=620. ¿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):

sistema-ecuaciones-restricc

De donde x_{1}=20x_{2}=110/3, que al evaluar en la función objetivo se obtiene: V(P)=9*(20)+12*(110/3)=620 corroborando el resultado anterior. Dejamos al lector el desafío de aplicar los conceptos presentados en este articulo para encontrar un intervalo para b_{2}b_{3} que conserve la base óptima.

Rating: 5.0. From 2 votes.
Please wait...

, , , , , , , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Deja un comentario