Método Simplex: Post-Optimalidad y Sensibilidad / Dualidad

Più simili a questo

teoria RPECV

da Josué David Fritz

IDENTIFICACION DE MICROORGANISMOS

da SEBASTIAN JAVIER MONSERRAT ARDILAA

SERES HUMANOS UNITARIOS Martha E. Rogers

da 05-EF-HU-JOSHELIN THALIA PORRAS RONDON

Estructura de un Proyecto

da Maria Elena Pimentel Hernandez

Método Simplex: Post-Optimalidad y Sensibilidad / Dualidad

Dualidad

Con los diferentes avances en investigación operativa se han descubierto cosas como que para cada problema modelado de programación lineal (Primal), existe una forma Dual que nos brinda información valiosa y de fácil acceso. Por ejemplo, sabemos que los precios sombre están dados en la solución del problema dual, la dualidad es una interpretación de los análisis de sensibilidad, Con cada iteración del simplex Dual obtenemos un límite superior del valor de Z* mientras que con cada iteración del Simplex Primal obtenemos un límite inferior del valor de Z*.

Programación Lineal Paramétrica

Una vez tenemos dominados los conceptos antes mencionados, ahora nos paramos a pensar que seria adecuado hacer con la información con la que disponemos o l oque es lo mismo ¿Qué cambios vale la pena implementar en nuestro modelo? Usando la programación lineal paramétrica para bosquejar los escenarios planteados con la información modelada y ofreciendo los cambios que vale la pena hacer.

Precios Sombra

Los precios sombra (denotados como yi) miden el valor marginal de un recurso; el ritmo al que pudiera aumentarse Z si aumentamos la disponibilidad del recurso bi. El método simplex identifica el precio sombra como el coeficiente de la variable de holgura en la fila 0 de la tabla simplex final. Gráficamente, sería el equivalente a evaluar el cambio en la función objetivo por trasladar las restricciones activas en las direcciones posibles hasta encontrarse con un vértice distinto.

Teoria de la dualidad

Uno de los descubrimientos más importantes durante el desarrollo inicial de la programación lineal fue el concepto de dualidad y sus importantes ramificaciones. Este descubrimiento reveló que, asociado a todo problema de programación lineal, existe otro problema lineal llamado dual. Desde distintos puntos de vista las relaciones entre el problema dual y el original (llamado primal) son muy útiles. Practicamente esta teoria nos dice que el problema primal de programación lineal se presenta en nuestra forma estándar (pero sin la restricción de que los valores de bi deban ser positivos). Se demuestra en la forma de que el problema dual usa exactamente los mismos parámetros que el problema primal, sin embargo, en diferentes lugares como: 1. Los coeficientes de la función objetivo del problema primal son los lados derechos de las restricciones funcionales del problema dual. 2. Los lados derechos de las restricciones funcionales del problema primal son los coeficientesde la función objetivo del problema dual. 3. Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restricción funcional del problema dual.

Análisis de sensibilidad

A la hora de hacer un análisis de un problema mediante la investigación operativa nos damos cuenta de que al plantear los problemas no se toman en cuenta todas las situaciones por las que puede pasar el problema y por ello es muy recomendable efectuar un análisis de sensibilidad. Esto nos sirve para identificar los costos reducidos a los que la solución óptima es más sensible, para tener presenta que deben ser calculadas con precaución.

Re-optimización

En muchos casos prácticos, los modelos desarrollados son sumamente grande. Para poder evaluar todo esto, a veces se desea crear variantes del modelo básico para considerar los diferentes escenarios. Es por esto que al obtener una solución óptima para una versión del modelo, frecuentemente es necesario resolver el problema varias veces mas. Un método para aplicar esto es resolver desde 0 cada nueva versión del modelo, pero esto requeriría cientos o miles de iteraciones en muchos casos. Una forma mas eficiente de lograrlo es re-optimizar . La re-optimización envuelve deducir como los cambios en el modelo se transfieren a la tabla final y posteriormente utilizar esta tabla como solución básica inicial para resolver el nuevo modelo. Si esta solución es factible para el nuevo modelo, aplicamos el método Simplex como siempre lo hemos hecho, en caso contrario, podemos aplicar el método Simplex Dual.

Análisis de Post-Optimalidad

El análisis de post-optimalidad es una parte importante de la mayoría de estudios de Investigación de Operaciones y especialmente para aplicaciones de Programación Lineal. Este es el que nos permite dar respuestas mas completas que una simple solución óptima, con este podemos ir mas allá y tomar verdaderas decisiones estratégicas. En general, el análisis de Post-Optimalidad busca evaluar nuestros parámetros (constantes y coeficientes) para revelarnos la robustez y posibles puntos de mejora de nuestro sistema.