Teoremas De Dualidad

La dualidad en programación lineal provee de resultados teóricos interesantes que justifican su uso como herramienta alternativa y complementaria de resolución.

TEOREMA DE DUALIDAD DÉBIL: En general, el valor de cualquier solución factible del problema de minimización, provee una cota superior del valor óptimo del problema de maximización. Análogamente, el valor de la función objetivo de cualquier solución factible del problema de maximización es una cota inferior del valor óptimo del problema de minimización.

TEOREMA DE DUALIDAD FUERTE: En el óptimo el valor de la función objetivo del problema primal será igual al valor de la función objetivo del problema dual evaluada en la solución dual óptima. Si el problema primal es no acotado, entonces el dual es infactible. Alternativamente si el problema primal es infactible, entonces el dual es no acotado.

TEOREMA DE HOLGURAS COMPLEMENTARIAS:Una variable en el primal esta asociada a una restricción en el dual (y viceversa). En este sentido si en el primal existe una variable no básica (valor igual a cero), en el dual la restricción asociado no está activa, es decir, no se cumple en igualdad. Análogamente, si la variable es básica en el primal, la restricción asociada en el dual se cumple en igualdad. Este resultado teórico es útil toda vez que simplifica la forma de obtener la solución óptima dado que como en un problema lineal la solución óptima (en caso de existir) esta en un vértice, esto implica resolver un sistema de ecuaciones (con restricciones de igualdad).

...