Bienvenido a ProgramaciónLineal.net un sitio enfocado exclusivamente a los contenidos de esta importante área de la Investigación de Operaciones. Se busca presentar los contenidos de una forma simple y didáctica, que permita al estudiante complementar su estudio formal de esta disciplina. Invitamos a los usuarios a plantear sus consultas y comentarios escribiendo a info@programacionlineal.net
SEP
2018
Análisis de Sensibilidad o Postoptimal
El análisis de sensibilidad o postoptimal para los modelos de Programación Lineal, tiene por objetivo identificar el impacto que resulta en los resultados del problema original luego de determinadas variaciones en los parámetros, variables o restricciones del modelo, sin que esto pase por resolver el problema nuevamente.
Es decir, ya sea si resolvemos nuestro modelo gráficamente o utilizando el Método Simplex, lo que se busca es que estas variaciones o sensibilidad hagan uso de la solución y valor óptimo actual, sin tener la necesidad de resolver para cada variación un nuevo problema. En especial nos concentraremos en el análisis de sensibilidad o postoptimal que hace uso de la tabla final del Método Simplex.
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 al problema.
EJEMPLO: Se desea estudiar la posibilidad de elaborar un nuevo producto con beneficio neto igual a 8 y que requiere 4, 2 y 5 unidades de los recursos asociados a cada restricción. Sin resolver nuevamente el problema, ¿Conviene elaborar el producto?
Max 9x1 + 12x2
sa: 4x1 + 3x2 <= 180
2x1 + 3x2 <= 150
4x1 + 2x2 <= 160
x1,x2 >= 0
X1 |
X2 |
X3 |
X4 |
X5 |
|
1 |
0 |
1/2 |
-1/2 |
0 |
15 |
0 |
1 |
-1/3 |
2/3 |
0 |
40 |
0 |
0 |
-4/3 |
2/3 |
1 |
20 |
0 |
0 |
1/2 |
7/2 |
0 |
615 |
Se debe evaluar rk y determinar si este es >=0.
En este ejemplo rk=1>=0, por lo cual no conviene la incorporación de esta nueva variable al modelo, es decir, aun cuándo sea incorporada no obtendremos un valor óptimo que supere el actual V(P)=615. De todas formas mostraremos como se incluye en la tabla final del Simplex esta modificación de modo que el lector pueda entender su incorporación cuando es necesario:
X1 |
X2 |
X3 |
X4 |
X5 |
XNew |
|
1 |
0 |
1/2 |
-1/2 |
0 |
1 |
15 |
0 |
1 |
-1/3 |
2/3 |
0 |
0 |
40 |
0 |
0 |
-4/3 |
2/3 |
1 |
1 |
20 |
0 |
0 |
1/2 |
7/2 |
0 |
1 |
615 |
Si el costo reducido de esta nueva variable hubiese sido cero, entonces el nuevo escenario tendría infinitas soluciones.
3. Cambio en los Coeficientes Función Objetivo: Se busca identificar qué ocurre con la actual solución óptima del escenario base si se cambian uno o varios de los coeficientes que definen la función objetivo. La solución óptima actual también lo será para el nuevo escenario siempre que los nuevos costos reducidos sean mayores o iguales a cero (notar que también cambia el valor de la función objetivo en la actual solución óptima). Es decir se debe cumplir que:
En caso contrario, se aplica el Simplex a partir de la tabla final del modelo original, con los nuevos costos reducidos y nuevo valor de la actual solución básica.
EJEMPLO: Sin resolver nuevamente el problema, se desea saber que sucede si se modifica los parámetros de la función objetivo, quedando éstos de la siguiente forma: Z = x1 + 5x2 - 2x3. (X4 y X5 son las 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 |
Debido a que los cambios en los parámetros de la función objetivo se producen en más de una variable consideraremos la siguiente fórmula:
Debido a que al menos uno de los costos reducidos de las variables no básicas se ha vuelto negativo, entonces cambia la actual solución y valor óptimo del problema. Para incorporar esta modificación en la tabla final del Método Simplex se actualiza los costos reducidos asociados a las variables no básicas, además del valor óptimo, quedando como sigue:
X1 |
X2 |
X3 |
X4 |
X5 |
|
0 |
-1 |
5 |
1 |
-1 |
20 |
1 |
4 |
-1 |
0 |
1 |
10 |
0 |
-1 |
1 |
0 |
1 |
10 |
4. Inclusión de una nueva restricción: Para saber si la actual solución y valor óptimo se mantendrá luego de incorporar una nueva restricción al problema se debe evaluar la solución actual y verificar si satisface la nueva restricción. En caso afirmativo, la actual solución también lo será del problema con la nueva restricción, en caso contrario se incorpora la nueva restricción a la tabla final del Simplex del escenario base.
EJEMPLO: Sin resolver nuevamente el problema, se desea saber que sucede si se considera una nueva restricción de la forma: 3x1 + 2x2 + 3x3 <= 25. (Observación: Considerar mismo modelo y tabla final del ejemplo anterior)
Se evalua la solución actual en la restricción: 3*(10) + 2*(0) + 3*(0) <= 25. No cumple. Por tanto se incorpora esta nueva restricción como fila a la tabla final del Simplex. Adicionalmente, se agrega X6 como variable de holgura asociada a esta nueva restricción:
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
0 |
-1 |
5 |
1 |
-1 |
0 |
20 |
1 |
4 |
-1 |
0 |
1 |
0 |
10 |
3 |
2 |
3 |
0 |
0 |
1 |
25 |
0 |
1 |
1 |
0 |
2 |
0 |
20 |
Una alternativa para encontrar el óptimo a través de esta tabla es formar la identidad (debemos hacer cero el parámetro asociado a X1 en la tercera fila) multiplicando la fila 2 por -3 y sumando dicho resultado a la fila 3. De esta forma se obtiene:
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
0 |
-1 |
5 |
1 |
-1 |
0 |
20 |
1 |
4 |
-1 |
0 |
1 |
0 |
10 |
0 |
-10 |
6 |
0 |
-3 |
1 |
-5 |
0 |
1 |
1 |
0 |
2 |
0 |
20 |
Finalmente obtenemos X4, X1 y X6 como variables básicas. Producto de la transformación un lado derecho queda negativo y en este caso podemos continuar adelante utilizando el Método Simplex Dual.
NUESTROS REFERIDOS
A continuación se presenta un compendio de Links de Interés para el usuario.
Análisis de Sensibilidad en Programación Lineal
ENLACES PATROCINADOS
Links patrocinados que pueden resultar de interés para el usuario.
MÉTODO SIMPLEX DUAL
El Método Simplex Dual es una estrategia algorítmica que nos puede resultar ser útil en diversos escenarios. El más evidente es cuando para llevar el modelo a su forma estándar debemos agregar varias variables de exceso (para restricciones del tipo >=) y otras tanto artificiales, de modo de tener una solución básica factible inicial en estas últimas. Esto nos define un modelo para ser resuelto por Simplex de 2 Fases que para un importante número de variables puede resultar engorroso.
También podemos aplicar el Método Simplex Dual como apoyo al análisis de sensibilidad o postoptimal. Especialmente para cambios en el vector del "lado derecho" o la inclusión de una nueva restricción al problema. Mayores referencias en Método Simplex Dual.
Consideremos el siguiente ejemplo:
- MIN 8X + 6Y
- S.A. 2X + Y >= 10
- ...... .2X + 2Y >= 16
- ..... ..X>= 0, Y>= 0
Llevamos el modelo a su forma estándar, agregando S1 y S2 como variables de exceso a la restricción 1 y 2, respectivamente. (Lo que claramente NO define una solución básica factible inicial).
X |
Y |
S1 |
S2 |
|
2 |
1 |
-1 |
0 |
10 |
2 |
2 |
0 |
-1 |
16 |
8 |
6 |
0 |
0 |
0 |
La tabla anterior no es óptima, debido a que S1=-10, S2=-16 que no cumplen con las restricciones de no negatividad y criterio básico para la aplicación del Método Simplex. Primero, multiplicaremos por -1 la fila 1 y 2 para que la negatividad quede asociado al lado derecho:
X |
Y |
S1 |
S2 |
|
-2 |
-1 |
1 |
0 |
-10 |
-2 |
-2 |
0 |
1 |
-16 |
8 |
6 |
0 |
0 |
0 |
Consideramos como variable básica que deja la base aquella asociada a la fila del lado derecho más negativo. En nuestro caso S2 asociado a fila 2. La variable que entra a la base será la del mínimo cuociente entre el negativo de los costos reducidos de las variables no básicas y los coeficientes de éstas asociados a la fila 2. En consecuencia: Min {-8/-2; -6/-2}=3. Por tanto, Y entra a la base. (Se ha marcado con azul el pivote).
Posteriormente se actualiza la tabla siguiendo la forma normal del Método Simplex:
X |
Y |
S1 |
S2 |
|
-1 |
0 |
1 |
-1/2 |
-2 |
1 |
1 |
0 |
-1/2 |
8 |
2 |
0 |
0 |
3 |
-48 |
Aun queda un lado derecho negativo asociado a la fila 1. Luego la actual variable básica asociada a la fila 1 (S1) deja la base. En seguida se calcula Min {-2/-1; -3/-1/2}=2. En consecuencia, X entra a la base.
X |
Y |
S1 |
S2 |
|
1 |
0 |
-1 |
1/2 |
2 |
0 |
1 |
1 |
-1 |
6 |
0 |
0 |
2 |
2 |
-52 |
Finalmente se obtiene la solución óptima donde X=2, Y=6 con V(P)=-52 (Nótese que el valor óptimo se obtiene con signo cambiado). Un resultado interesante a considerar es que el costo reducido asociado a las variables de exceso de la restricción 1 y 2 representan el valor de las variables duales óptimas al modelo que hemos resuelto. (Ver ejemplo Sillas y Mesas AQUI)
INTERVALO DE VARIACIÓN LADO DERECHO
Frecuentemente es útil conocer un intervalo de variación para cada parámetro del lado derecho por separado de modo que se conserve la actual base óptima. Por ejemplo si consideramos la tabla final del ejemplo de "1. Cambio en el "lado derecho" de las restricciones"
X1 |
X2 |
X3 |
X4 |
X5 |
|
0 |
-1 |
5 |
1 |
-1 |
20 |
1 |
4 |
-1 |
0 |
1 |
10 |
0 |
1 |
1 |
0 |
2 |
20 |
¿Cuál es el intervalo de variación para b2 (actualmente b2=10) que mantiene la actual base óptima?
Consideramos la columna asociada a X5 que corresponde a la variable de holgura asociada a la restricción 2. Luego, para encontrar el intervalo de variación calculamos:
Max {-10/1} <= D <= Min {-20/-1}
-10 <= D <= 20
Por tanto b2 puede variar entre: {10-10; 10+20} = {0,30} y se mantiene la actual base óptima.
INTERVALO DE VARIACIÓN COEFICIENTE FUNCIÓN OBJETIVO
Un caso de interés resulta identificar el intervalo de variación de los coeficientes de la función objetivo para las variables básicas, que garantiza que la actual solución óptima se mantenga.
EJEMPLO: Encontrar un intervalo de variación para C1 y C2 que conserven la actual solución óptima (X3 y X4 corresponden a las variables de holgura de la restricción 1 y 2 respectivamente).
Max 20x1 + 15x2
sa: 2x1 + 2x2 <= 8
2x1 + x2 <= 6
x1,x2 >= 0
X1 |
X2 |
X3 |
X4 |
|
0 |
1 |
1 |
-1 |
2 |
1 |
0 |
-1/2 |
1 |
2 |
0 |
0 |
5 |
5 |
70 |
Para C1:
Max {5/-1/2} <= D <= Min {5/1}
-10 <= D <= 5
C1 puede variar entre: {-20-10, -20+5}={-30,-15} para el problema de minimización. (Entre {15,30} para Max)
Para C2:
Max {5/-1} <= D <= Min {5/1}
-5 <= D <= 5
C2 puede variar entre: {-15-5, -15+5}={-20,-10} para el problema de minimización. (Entre {10,20} para Max)
Comparte tus consultas y sugerencias.
Ingresa a nuestro Formulario de Contacto