análisis de sensibilidad Archivos - Página 3 de 4

Análisis de Sensibilidad en Programación Lineal utilizando la Tabla Final del Método Simplex

Un supuesto básico asociado a la Programación Lineal es que los parámetros o constantes son valores conocidos con exactitud al momento de resolver el modelo de optimización. Este supuesto de asumir que no existe incertidumbre claramente implica una simplificación en el modelamiento de problemas de naturaleza real y es conocido como el supuesto de modelo determinista.

La optimización también permite incorporar explícitamente la incertidumbre en los parámetros en el modelamiento, asumiendo que la totalidad o un conjunto de éstos se distribuyen aleatoriamente, lo cual se puede representar a través de una función de probabilidad conocida o una distribución empírica que modela distintos escenarios para los parámetros, asociando una probabilidad de ocurrencia en cada caso. Esta categoría de modelos de optimización (por cierto más complejos en comparación al caso determinista) se llaman modelos estocásticos, los cuales en rara oportunidad se analizan en cursos introductorios de Investigación de Operaciones, de modo que forman parte del programa de estudios en cursos de Magíster y Doctorado asociado al área de optimización matemática.

En relación a lo anterior, si bien un modelo determinista considera valores fijos para los parámetros, aún podemos analizar los cambios en los resultados del modelo (solución óptima y valor óptimo principalmente) en comparación a lo obtenido en una instancia de resolución original o escenario base. Esto se conoce como análisis de sensibilidad o análisis postoptimal.

Recordemos que la estructura de la tabla final del Método Simplex se puede representar de la siguiente forma:

Donde:

I: Matriz Identidad (Diagonal de “1”)
0: Vector de costos reducidos asociados a las variables básicas
B: Matriz de variables básicas
D: Matriz de variables no básicas
b: Vector de “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

A continuación presentamos los Análisis de Sensibilidad más recurrentes asociados a los modelos de Programación Lineal y utilizando como fuente de información la tabla final del Método Simplex. El siguiente es un listado de los artículos que hemos desarrollado para cada uno de estos temas los cuales te recomendamos visitar:

Aprueba tu Examen con el Libro de Apuntes de Programación Lineal

¿Te gustaría disponer de un Apunte con ejercicios resueltos explicados de modo sencillo que te permita aprobar tu Examen de Programación Lineal?

El Libro de Apuntes de Programación Lineal que necesitas esta aquí y ha sido diseñado especialmente para aquellos alumnos que se encuentran cursando una cátedra inicial de Investigación de Operaciones (o Investigación Operativa) que buscan resolver de forma sencilla aquellas preguntas frecuentes relacionadas a los modelos de optimización lineales.

El material contenido en este Apunte es original, es decir, no ha sido tomado de libros o apuntes de terceros. Para ello hemos desarrollado una labor creativa en el diseño de los ejercicios que estamos seguros sabrás apreciar.

El Libro de Apuntes contiene los siguientes capítulos:

UNIDAD 1: FORMULACIÓN Y RESOLUCIÓN GRÁFICA DE MODELOS DE PROGRAMACIÓN LINEAL EN 2 VARIABLES
UNIDAD 2: ANÁLISIS DE SENSIBILIDAD EN PROGRAMACIÓN LINEAL UTILIZANDO EL MÉTODO GRÁFICO
UNIDAD 3: RESOLVER UN MODELO DE PROGRAMACIÓN LINEAL CON SOLVER DE EXCEL
UNIDAD 4: INTERPRETACIÓN DE LOS INFORMES DE SENSIBILIDAD OBTENIDOS CON SOLVER DE EXCEL
UNIDAD 5: MÉTODO SIMPLEX
UNIDAD 6: MÉTODO SIMPLEX DE 2 FASES
UNIDAD 7: CASOS ESPECIALES DE LA PROGRAMACIÓN LINEAL DETECTADOS CON EL MÉTODO SIMPLEX

Beneficios

Eso no es todo!

~~Por la compra del Apunte recibirás GRATIS un archivo Excel con Ejercicios de Programación Lineal resueltos con Solver de Excel~~.

¿Quieres tener el archivo PDF con el Libro de Apuntes de Programación Lineal?

[sociallocker]MUCHAS GRACIAS!. DESCARGA AQUÍ EL APUNTE DE PROGRAMACIÓN LINEAL[/sociallocker]

Nuestros Usuarios nos Respaldan

Desde Febrero de 2012 el Libro de Apuntes de Programación Lineal ha sido descargado por más de ~~57.000~~ 100.000 usuarios de distintos países los cuales se han mostrados muy satisfechos por el material recibido. Esto ha permitido consolidar nuestro sitio web como una de las principales referencias sobre la Gestión de Operaciones e Investigación de Operaciones para estudiantes.

Incorporar Nueva Restricción (Análisis Postoptimal Programación Lineal)

Una vez resuelto un modelo de Programación Lineal puede resultar de interés si la actual solución óptima y valor óptimo se conservaran si se decide incorporar una nueva restricción al problema. Esta restricción generalmente representa una condición que en primera instancia se omite de forma voluntaria para dar una mayor flexibilidad a la resolución del modelo original o alternativamente su no inclusión en el modelo original puede también deberse a una simple omisión (involuntaria).

Consideremos el siguiente modelo de Programación Lineal que hemos resuelto en un artículo previo a través del Método Simplex:

La tabla final óptima que considera las variables s1, s2 y s3 como las respectivas holguras de las restricciones del problema es:

Por ejemplo, consideremos que se desea incorporar una nueva restricción definida por la siguiente expresión: 3X+Y<=600. ¿Cambia la actual solución óptima y valor óptimo?.

Para responder a lo anterior se recomienda evaluar la actual solución óptima en la nueva restricción; si ésta se cumple entonces el modelo conserva su solución óptima y valor óptimo; en caso contrario la solución óptima actual será infactible y se debe incorporar esta situación en el modelo original para encontrar la nueva solución del mismo. Notar que también puede suceder que al agregar una nueva restricción que no satisface la solución actual el problema podría resultar ser infactible al tener un dominio de soluciones factibles vacío.

En nuestro ejemplo al evaluar obtenemos: 3(100)+(350)<=600, es decir, la solución óptima actual es infactible al incorporar esta nueva restricción.

Para incorporar esta modificación en la tabla final del Método Simplex agregamos una nueva fila y una nueva columna asociada a una variable s4>=0 que será la holgura de la nueva restricción. La tabla queda de la siguiente forma:

Las variables básicas del problema original son x, s2 e y, respectivamente. Al incorporar la nueva restricción (fila) tanto x como y pierden la estructura de la identidad característica de las variables básicas. Por ello para formar la base podemos realizar operaciones fila multiplicando por -3 la fila 1 y sumando ésta a la fila 4. Posteriormente multiplicar por -1 la fila 3 y sumar a la fila 4:

Ahora las variables básicas son x, s2, y, s4 (enumeradas en el orden en el cual aparecen en la identidad), sin embargo, la variable s4 toma un valor de -50 lo cual no corresponde a una solución básica factible.

¿Cómo continuar con las iteraciones?. Utilizando el Método Simplex Dual se recomienda corroborar que la nueva solución óptima corresponde a x=250/3 e y=350.

Adicionalmente podemos utilizar un enfoque de Resolución Gráfica para el problema anterior. El siguiente gráfico representa la resolución del escenario inicial donde la solución básica factible óptima se alcanza en el vértice C con x=100 e y=350.

Al incorporar la nueva restricción (recta color rojo) el dominio de soluciones factibles se ve reducido, donde ahora ya no son factibles los puntos en el polígono con área achurada color verde (donde se puede verificar que el vértice C es infactible).

Si se resuelve gráficamente sobre el nuevo dominio (área achurada color naranjo) las curvas de nivel de la función objetivo (recta punteada color azul) pasa por última vez en el vértice F donde x=250/3 e y=350 como solución óptima del nuevo problema.

Incorporar nueva variable en un Modelo (Análisis de Sensibilidad en Programación Lineal)

Una vez resuelto un modelo de Programación Lineal a través del Método Simplex puede resultar de interés analizar si cambia la solución óptima y valor óptimo del problema luego de incluir una nueva variable de decisión.

Por ejemplo, en un Problema de Producción esta nueva variable generalmente representa la evaluación de un nuevo producto no considerado inicialmente donde es útil saber cuál sería su impacto en los resultados del modelo sin la necesidad de reoptimizar.

Este tipo de análisis corresponde al Análisis de Sensibilidad en Programación Lineal y a continuación presentaremos un ejemplo de este escenario.

Consideremos el siguiente modelo de optimización:

Al resolver este modelo de Programación Lineal con el Método Simplex se alcanza la siguiente tabla final, donde s1, s2 y s3 son las variables de holgura de las restricciones 1, 2 y 3, respectivamente:

Consideremos adicionalmente que las variables x e y representan 2 productos y sus respectivos coeficientes en la función objetivo representan el ingreso asociado a su venta. En este contexto, en el plan actual se producen 100 unidades de x y 350 unidades de y, con un ingreso total de $3.100 (valor óptimo).

Asumamos que nos interesa analizar si conviene la fabricación de un tercer producto (llamado z) que tiene un ingreso unitario por venta de $5 y que para su fabricación requiere de 3, 1 y 1 unidad de los recursos asociados a las restricciones R1, R2 y R3, respectivamente.

Más aún, nos interesa dar respuesta a esta interrogante sin tener que resolver desde cero este nuevo problema. Si este es nuestro objetivo podemos utilizar el Análisis Postoptimal donde en particular calcularemos el costo reducido de esta nueva variable dado sus parámetros.

Si dicho costo reducido resulta ser negativo implica que la solución óptima actual deja de serlo al considerar este cambio y por tanto se puede buscar el nuevo óptimo utilizando la solución actual como punto de partida.

La fórmula del costo reducido para la nueva variable está dada por:

Donde la notación corresponde a:

Aplicando las definiciones anteriores a nuestro ejemplo se obtiene lo siguiente:

Notar que el costo reducido para esta nueva variable es 3/2>=0 lo que significa que la solución óptima actual se mantiene si se incluye esta nueva variable al modelo (donde la variable z sería una variable no básica con valor cero).

¿Cuánto debería ser como mínimo el ingreso asociado a la nueva variable z de modo que si sea conveniente su producción y por tanto cambie la solución óptima actual?.

Responder esta interrogante consiste en determinar cuál debiera ser el valor de Cj para que Rj<0 y entonces la variable z al tener costo reducido negativo entra a la base y se continua con las iteraciones.

Por simple inspección y evaluando en la fórmula anterior se puede corroborar que el ingreso mínimo para dicha variable debería ser un valor mayor a 13/2. Por ejemplo, asumamos ahora que el ingreso unitario de la variable z es $7. El nuevo costo reducido sería -1/2 y se actualiza la tabla final del Método Simplex quedando de la siguiente forma:

Se pueden continuar con las iteraciones del Método Simplex incorporando la variable z a la base y luego calculando el mínimo cuociente entre {400/2; 350/1}=200 ==> s1 deja la base. Al actualizar la tabla se obtiene la nueva solución básica factible óptima y valor óptimo:

Ahora x=200, y=150, z=200, con valor óptimo V(P)=3.200. Puedes corroborar los resultados revisando nuestro tutorial Cómo resolver un modelo de Programación Lineal con el Método Simplex.

Cambio en el Lado Derecho de las Restricciones (Programación Lineal)

El vector del lado derecho asociado a las restricciones de un modelo de Programación Lineal puede tener distintas interpretaciones prácticas como, por ejemplo, la disponibilidad de insumos para la fabricación de determinados productos, limitantes de capacidad, requisitos de demanda, entre otros.

En consecuencia resulta de interés analizar el impacto del cambio de uno o varios coeficientes del vector de lado derecho sobre los resultados originales del modelo sin la necesidad de reoptimizar, es decir, sin que tener que resolver nuevamente un modelo que incorpore los cambios propuestos.

En este contexto, si en particular se verifica que:

Se puede afirmar que se conserva la actual base óptima. Lo anterior implica que las variables básicas del modelo lo seguirán siendo bajo este nuevo escenario y por tanto la nueva solución óptima del problema se podrá encontrar a través de la resolución del mismo sistema de ecuaciones original (se conservan las restricciones activas originales).

Ahora bien, si alguno de los coeficientes en el cálculo del vector de variables básicas adopta un valor negativo, estamos frente a una solución básica infactible, lo que nos obliga a realizar una actualización de los resultados del modelo para encontrar la nueva solución, base óptima y valor óptimo, pero que no pase por la reoptimización del mismo.

Consideremos el siguiente modelo de optimización:

Las variables básicas son x=100, s2=400, y=350, donde todas satisfacen las condiciones de no negatividad (es decir es una solución básica factible) y además el costo reducido de las variables no básicas (s1 y s3) son mayores o iguales a cero, condición necesaria y suficiente junto a lo anterior para garantizar que nos encontramos frente a la solución óptima del problema (solución básica factible óptima).

Adicionalmente y en relación a la proposición anterior se pueden corroborar los resultados obtenidos:

Consideremos ahora que el lado derecho de la restricción 1 cambia de su valor original 1600 a 1650. ¿Cambia la actual base óptima?. Para ello recalculamos el vector de las variables básicas:

Se puede apreciar que todos los coeficientes del vector de variables básicas (Xb) son mayores o iguales a cero, es decir, se conserva la base óptima (idénticas variables básicas) pero la solución óptima cambia a x=125, s2=250, y=350.

Adicionalmente el valor óptimo ahora es V(P)=3.175. Sin embargo, no es necesario seguir realizando iteraciones del Método Simplex (dado que estamos frente a una solución básica factible óptima) y nos ahorramos el trabajo de la reoptimización.

La pregunta natural es ¿Qué sucede si al actualizar el vector de las variables básicas al menos una de las variables toma un valor negativo?. Modifiquemos ahora en forma simultanea los lados derechos de las restricciones 1 y 2 a 2.000 y 1.500, respectivamente. El nuevo vector de variables básicas queda definido de la siguiente forma:

Notar que ahora la variables básica s2=-1.000 adopta un valor que no satisface la condición de no negatividad para las variables de decisión. Al definir lo anterior una situación de infactibilidad es necesario actualizar la tabla final del Método Simplex con el valor de las variables básicas y el valor de la función objetivo:

Para encontrar la solución óptima de este problema a partir de la tabla anterior se puede aplicar el Método Simplex Dual. La variable básica que deja la base es s2 (variable básica asociada a la fila 2 donde encontramos el “lado derecho” negativo).

Para determinar la variable que entra a la base calculamos el mínimo cuociente: Min{-3/2/-3}=1/2 ==> s1 entra a la base. Actualizamos la tabla del Método Simplex obteniendo lo siguiente:

Se puede apreciar que sólo fue necesario realizar una iteración adicional para poder obtener la solución óptima del nuevo escenario (x=400/3, s1=1.000/3, y=350) con un valor óptimo de V(P)=3.200.

El siguiente gráfico realizado con el software Geogebra permite visualizar la nueva solución óptima y estructura del problema, donde ahora la solución óptima se encuentra con las restricciones 2 y 3 activas (el problema original en su solución óptima consideraba la restricción 1 y 3 como activas):