Teoria De Dualidad

1. TEORÍA DE DUALIDAD

En este capítulo presentamos los aspectos más relevantes de la teoría de dualidad para el problema de optimización lineal. En la sección 5.1 definimos el dual de un problema de minimización en forma canónica el cual es el punto de partida para deducir reglas para formar el dual de un problema lineal general. En la sección 5.2 presentamos los teoremas de dualidad débil y fuerte. Finalmente, en la sección 5.3 presentamos la relación entre los costos reducidos y las variables óptimas duales.

1.1 EL DUAL DE UN PROBLEMA DE OPTIMIZACIÓN LINEAL

Para cada problema de programación lineal es posible asociar un problema lineal compañero llamado problema dual en el cual los roles de las variables y restricciones son reversos, i.e., para cada variable en el problema lineal original o primal hay una restricción en el dual, y para cada restricción en el primal hay una variable en el dual.

Aunque veremos que es posible asociar un dual a cada problema lineal, la simetría de los dos problemas es más obvia cuando el problema lineal está en forma canónica:

este problema será llamado el problema lineal primal o simplemente, problema primal. El correspondiente problema lineal dual o simplemente problema dual es, por definición:

Es decir:

Problema primal

Problema dual

Nótese que:

1) Todo problema lineal puede ser llevado a la forma canónica de un modo simple:

a) Una restricción del tipo es simplemente multiplicada por .

b) Una restricción de igualdad puede ser escrita como dos desigualdades:

c) El requerimiento de que todas las variables sean no negativas se trata de la misma forma ya vista para transformar un problema lineal a la forma standard.

d) Un problema de maximización es convertido en un problema de minimización multiplicado la función objetivo por -1.

2) Si el problema primal tiene n variables y m restricciones entonces el problema dual tiene m variables (una variable para cada restricción del primal) y n restricciones (una restricción en el dual por cada variable en el primal) esto es así porque, por definición, si A es la matriz de restricción del primal, es la matriz de restricciones del dual.

3) También por definición, el vector de costos c del primal actúa como vector del lado derecho en el dual y viceversa.

4) El problema dual es un problema lineal de maximización, donde todas las restricciones son del tipo , y todas las variables son no negativas. Esta es la forma canónica para un problema de maximización.

Es decir, las formas canónicas son:

Forma canónica para un problema de minimización

Forma canónica para un problema de maximización

Ejemplo: Considere el problema primal en forma canónica.

Entonces su dual es:

El siguiente lema prueba que el rol del primal y dual puede ser intercambiado, en el sentido de que el problema dual, del problema dual es el problema primal, de manera que calcular el dual dos veces es equivalente a no hacer modificaciones en el problema primal.

Lema:

El dual del problema lineal dual es el problema primal.

Prueba:

Consideremos

...