forma estándar programación linealEl Análisis de Sensibilidad o Análisis Postoptimal en el Método Simplex permite flexibilizar un supuesto básico de la Programación Lineal, el cual es asumir que el valor de los parámetros o constantes de un modelo son conocidos, es decir, que no existe incertidumbre (modelo determinista). En este contexto luego de resolver un problema de Programación Lineal con el Método Simplex resulta de interés analizar el impacto en los resultados (solución óptima, valor óptimo, variables básicas óptimas, etc) ante variaciones en la estimación preliminar de dichos parámetros.

A continuación presentamos a través de un ejemplo algunos casos típicos que se abordan sobre el Análisis Postoptimal (Análisis de Sensibilidad) en cursos introductorios de Investigación de Operaciones. Para ello consideremos el siguiente problema de Programación Lineal:

modelo-programacion-lineal

El cual luego de llevar a la forma estándar y resolver por el Método Simplex permite alcanzar la siguiente tabla final:

tableau-final-metodo-simple

Donde [latex]X_{4}[/latex] y [latex]X_{5}[/latex] son las variables de holgura para las restricciones 1 y 2 respectivamente. Se solicita realizar un Análisis Postoptimal (o Análisis de Sensibilidad) que de respuesta a los siguientes escenarios de forma independiente.

Análisis de Sensibilidad o Postoptimal con la Tabla Final del Método Simplex

Interpretación de Resultados Tabla Final del Método Simplex

¿Cuál es la solución óptima y valor óptimo de P)? Indique cuales son las variables básicas y cuales las variables no básicas. ¿La solución óptima es única? ¿Cuáles son las restricciones que se encuentran activas en el óptimo?.

La solución óptima en términos de las variables originales del modelo es: [latex]X_{1}=0,X_{2}=0,X_{3}=9[/latex]. En cuanto a las variables de holgura, [latex]X_{4}=2[/latex] y [latex]X_{5}=0[/latex] (variable básica y no básica, respectivamente). El valor óptimo es [latex]V(P)=126[/latex]. Las variables básicas son [latex]X_{4}[/latex] y [latex]X_{3}[/latex] y las variables no básicas son [latex]X_{1},X_{2}[/latex] y [latex]X_{5}[/latex]. Las restricciones activas en el óptimo, es decir, aquellas que se cumplen en igualdad, es la restricción 2 (dado que su variable de holgura representada por [latex]X_{5}[/latex] es no básica en el óptimo, por tanto adopta un valor igual a cero), además de las restricciones de no negatividad para las variables [latex]X_{1}[/latex] y [latex]X_{2}[/latex].

Intervalo de Variación Coeficiente de una Variable No Básica en la Función Objetivo en el Método Simplex

Encuentre un intervalo de variación para [latex]C_{2}[/latex] (coeficiente asociado a la variable [latex]X_{2}[/latex] en la función objetivo) que mantenga la actual solución óptima.

Este es un caso sencillo de abordar en el Análisis de Sensibilidad. Por simple inspección se observa que el costo reducido de la variable no básica [latex]X_{2}[/latex] es 3/5. Notar adicionalmente que el coeficiente de la variable [latex]X_{2}[/latex] en la función objetivo de maximización es igual a 5. Luego se concluye que para que la variable [latex]X_{2}[/latex] pueda ingresar a la base (y de esta forma cambiar la solución óptima y la base óptima) el parametro correspondiente en la función objetivo ([latex]C_{2}[/latex]) debería ser al menos 5+3/5=28/5. Es decir, se conserva la solución óptima si y solo sí [latex]C_{2}[/latex] varía en el intervalo [latex]]-\infty ,28/5][/latex] en la función objetivo de maximización. Notar que en particular si [latex]C_{2}=28/5[/latex] se da lugar al escenario de infinitas soluciones óptimas (variable no básica con costo reducido igual a cero en la actual solución básica factible óptima).

Intervalo de Variación Coeficiente de una Variable Básica en la Función Objetivo en el Método Simplex

Si el coeficiente para [latex]X_{3}[/latex] en la función objetivo cambia de 14 a 12. ¿Cambia la actual solución óptima?. ¿Cambia la actual base óptima?.

Sea [latex]r_{j}[/latex] el costo reducido correspondiente a una variable no básica en la actual solución óptima e [latex]y_{ij}[/latex] denotan las entradas en la tabla final del Método Simplex correspondiente a la variable básica [latex]x_{i}[/latex] (cuyo coeficiente cambia) y la respectiva variable no básica [latex]x_{j}[/latex]. Dado lo anterior se conserva la solución óptima si la variación propuesta para el parámetro que pondera a una variable básica en la función objetivo se encuentra en el intervalo que provee la fórmula a continuación:

intervalo-funcion-objetivointervalo-variacion-c3

En el ejemplo propuesto esto da origen un aumento permisible de más infinito y una reducción permisible de 3/2 (la interpretación se ha realizado sobre el parámetro [latex]C_{3}[/latex] en la función objetivo de maximización). No obstante la resolución del problema mediante el Método Simplex y el correspondiente análisis de sensibilidad se ha realizado sobre el modelo en su forma estándar, es decir, considerando una función objetivo de minimización. Se concluye a través del Análisis de Sensibilidad que [latex]C_{3}[/latex] puede variar entre 12,5 e infinito y se conserva la actual solución óptima (y base óptima).

Agregar Nueva Restricción en el Método Simplex

Considere que se incorpora la siguiente restricción al problema: [latex]2X_{1}+3X_{2}+5X_{3}\leq 50[/latex]. ¿Cambia la solución óptima y valor óptimo?. En caso de ser afirmativo encuentre la nueva solución óptima y valor óptimo.

En primer lugar corresponde evaluar si la actual solución óptima resulta ser factible al considerar la nueva restricción, es decir,: [latex]2(0)+3(0)+5(9)\leq 50[/latex], lo que claramente se cumple. En consecuencia se conserva tanto la solución óptima como el valor óptimo.

Agregar Nueva Variable de Decisión en el Método Simplex

Asuma ahora que se incorpora una nueva variable de decisión [latex]X_{6}[/latex] con coeficiente en la función objetivo (de maximización) igual a 10 y con parámetros 3 y 5 en la primera y segunda restricción, respectivamente. ¿Cambia la actual solución óptima?.

costo-reducido-nueva-variab

Este análisis requiere evaluar el costo reducido de la nueva variable propuesta y verificar si éste es mayor o igual a cero. En dicho caso se conserva tanto la solución óptima como el valor óptimo (un caso particular sería obtener un costo reducido igual a cero donde se genera el caso de infinitas soluciones óptimas). Por el contrario si el costo reducido para la nueva variable de decisión resulta ser negativo, entonces cambia la solución óptima y esta nueva variable deberá ingresar a la base y obliga a continuar con las iteraciones del Método Simplex. En el ejemplo el costo reducido de la variable [latex]X_{6}[/latex] es -3, por tanto ingresa a la base, agregándose una columna adicional a la tabla con coeficientes [latex]B^{-1}A_{j}[/latex] en las restricciones tal como se muestra a continuación:

agregar-variable-metodo-sim

Indicación: La variable [latex]X_{6}[/latex] ingresa a la base y sale la variable [latex]X_{4}[/latex] considerando el criterio del mínimo cuociente. Se propone al lector continuar las iteraciones a contar de este punto.

Cambio Vector del Lado Derecho en el Método Simplex

Considere que cambia el vector del lado derecho de las restricciones a [latex]b=(10,100)^{T}[/latex]. Indique si las actuales variables básicas óptimas lo son también del nuevo problema.

Se actualiza el vector de las variables básicas considerando la modificación propuesta según se detalla a continuación:

cambio-lado-derecho

La variable básica asociada a la fila 1 ([latex]X_{4}[/latex]) adopta un valor negativo (-10) por tanto cambia la actual base óptima. Para encontrar la nueva solución óptima y valor óptimo se debe continuar las iteraciones utilizando el Método Simplex Dual previa actualización del valor de la función objetivo en la nueva solución básica (de momento infactible).

Cambio Coeficientes Función Objetivo en el Método Simplex

Si cambia la función objetivo de maximización a [latex]-4X_{1}+6X_{2}+13X_{3}[/latex]. ¿Cambia la actual base óptima?. ¿Cuál es la solución óptima y valor óptimo de este nuevo escenario?.
vector-costos-reducidos-no-

En este caso se debe recalcular el vector de los costos reducidos de las variables no básicas del problema que denotamos por [latex]r_{D}[/latex] según se muestra en la imagen. Notar que el costo reducido de la variable [latex]X_{2}[/latex] es negativo (-4/5) lo cual implica que cambia la actual solución óptima (y se deberá actualizar el valor de la función objetivo dado los nuevos coeficientes de la función objetivo). Para encontrar la nueva solución óptima se deberá ingresar la variable [latex]X_{2}[/latex] a la base y seguir con las iteraciones del Método Simplex.

Recomendación: La mayor parte de los resultados presentados en este artículo sobre el Análisis de Sensibilidad pueden ser verificados a través de herramientas de resolución online para modelos de Programación Lineal haciendo uso del Método Simplex. En este sentido se recomienda acceder a la aplicación disponible en Programación Lineal – Método Simplex.

Leave a comment

Su dirección de correo no se hará público. Los campos requeridos están marcados *