Teoría de la dualidad y análisis de sensibilidad

El análisis de sensibilidad es una parte esencial de casi todos los estudios de programación 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.

En realidad, los valores de los parámetros que se usan en el
modelo casi siempre son sólo estimaciones basadas en una predicción de las condiciones futuras. Con frecuencia, los datos que se obtienen para desarrollar estas estimaciones son bastante burdos o no existen, así que los parámetros de la formulación original pueden representar tan sólo la opinión
proporcionada por el personal de línea.

Para investigar el efecto que tendría sobre la solución óptima que proporciona el método símplex el hecho de que
los parámetros tomen otros valores posibles.

Identificar los parámetros sensibles (es decir, los parámetros cuyos valores no pueden cambiar sin que cambie la solución
óptima).

Caso 1: cambios en las bi

Caso 2a: cambios en los coeficientes de una variable no básica

Caso 2b: introducción de una nueva variable

Caso 3: cambios en los coeficientes de una variable básica

Caso 4: introducción de una nueva restricción

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

2. 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

3. 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

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

5. 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.

6. 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.

La teoría de la dualidad se basa de manera directa en la idea fundamental (en particular con respecto al renglón 0)

Propiedad de dualidad débil: Si x es una solución factible para el problema primal y y es una solución factible para el problema dual, entonces
cx <= yb.

Propiedad de dualidad fuerte: Si x* es una solución óptima para el problema primal y y* es una solución óptima para el problema dual, entonces
cx* = y*b.

Propiedad de soluciones complementarias: En cada iteración, el método símplex identifica de manera simultánea una solución FEV, x, para el problema primal y una solución
complementaria, y, para el problema dual (que se encuentra en el renglón 0, como loscoefi cientes de las variables de holgura), donde
cx = yb.

Propiedad de soluciones complementarias óptimas: Al final de cada iteración, el método símplex identifica de manera simultánea una solución óptima x* para el problema primal y una solución óptima complementaria y* para el problema dual (que se encuentra en el renglón 0 como los coeficientes de las variables de holgura), donde
cx* = y*b.

Propiedad de simetría: En el caso de cualquier problema primal y su problema dual, las relaciones entre ellos deben ser simétricas debido a que el dual de este problema dual es este problema primal.

1. 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.
2. 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.
3. Si un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones factibles o bien la función objetivo es no acotada.

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

Una de las aplicaciones más importantes de esta teoría es la interpretación y realización del análisis de sensibilidad.

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 coeficientes de 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.