Asociado a todo problema de programación lineal, existe otro problema lineal llamado dual.

Még több ilyen

EL ARTE EN LA EDUCACIÓN INICIAL

Szerző: Didier Parra

Estado del arte en la investigación ¿Análisis de los conocimientos acumulados o indagación por nuevos sentidos?

Szerző: Liliana Gualpa

Teoria de la dualidad y analisis de sensibilidad

Szerző: Angel Ramon Cespedes Then

Sensibilidad y dualidad

Szerző: Frank Evangelista Vásquez

Teorema de la dualidad: Las siguientes son las únicas relaciones posibles entre los problemas primal y dual.

Si un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones factibles o bien la función objetivo es no acotada

Si uno de los problemas tiene soluciones factibles y una función objetivo no acotada (es decir, no tiene solución óptima), entonces el otro problema no tiene soluciones factibles.

Si un problema tiene soluciones factibles y una función objetivo acotada (y, por ende, una solución óptima), entonces ocurre lo mismo con el otro problema, de manera que se aplican tanto la propiedad de dualidad débil como la fuerte.

Asociado a todo problema de programación lineal, existe otro problema lineal llamado dual.

Propiedades de la Dualidad

Se tienen las siguientes relaciones generales entre los problemas primal y dual.

Los coeficientes de la función objetivo en un problema son los valores del lado derecho en el otro.

Los parámetros de una restricción (funcional) en cualquier problema son los coeficientes de una variable en el otro.

Dado un pronlema Primal en forma estandar, su problema dual usa exactamente los mismos parámetros que el problema primal, pero en diferentes lugares:

Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restricción funcional del problema dual.

Los coeficientes de la función objetivo del problema primal son los lados derechos de las estricciones funcionales del problema dual.

Los lados derechos de las restricciones funcionales del problema primal son los coeficientes de la función objetivo del problema dual.

Al cambiar los valores de los parámetros en el problema primal se cambian también los valores correspondientes en el problema dual. Por tanto, se puede elegir qué problema se va a usar para investigar cada cambio.

Introducción de una nueva variable

Cambios en los coeficientes de una variable no básica

Como la variable en cuestión es no básica (su valor es cero), el cambio en sus coeficientes no puede afectar la factibilidad de la solución, por lo cual, la pregunta que queda abierta en este caso es si todavía es óptima.

Resumen del procedimiento para análisis de sensibilidad

Reoptimización: Si esta solución no pasa una de las pruebas, se puede obtener (si se desea) la nueva solución óptima a partir de la tabla actual como tabla símplex inicial (con las conversiones necesarias) por el método símplex o el símplex dual.

Prueba de optimalidad: Se verifica si esta solución es óptima (factible), mediante la comprobación de que todos los coeficientes de las variables no básicas del renglón 0 continúen no negativos.

Prueba de factibilidad: Se prueba la factibilidad de esta solución mediante la verifi cación de que todas las variables básicas de la columna del lado derecho aún tengan valores no negativos.

Conversión a la forma apropiada de eliminación de Gauss: Se convierte esta tabla en la forma apropiada para identificar y evaluar la solución básica actual, para lo cual se aplica (según sea necesario) eliminación de Gauss.

Revisión de la tabla símplex final: Se emplea la idea fundamental para determinar los cambios que resultan en la tabla símplex final.

Revisión del modelo: se hacen los cambios deseados en el modelo que se va a investigar.

Una de las aplicaciones más importantes de esta teoría es la interpretación y realización del análisis de sensibilidad lineal. Debido a que la mayoría de los valores de los parámetros que se emplean en el modelo original son sólo estimaciones de las condiciones futuras, es necesario investigar el efecto que tendrían sobre la solución óptima en caso de que prevalecieran otras condiciones.