1. Encontrando el Dual de un PPL.

Asociado con cualquier problema de programación lineal existe otro llamado DUAL.
Conocer la relación entre un PPL y su dual es vital para entender tópicos avanzados en programación lineal y no-lineal.

Cuando se habla del dual de un PPL se denomina éste último como Primal. Si el primal es un problema de maximización su dual será un problema de minimización y vice-versa. Por conveniencia las variables del primal serán z (función objetivo) y sus variables x_i y las variables para el problema de minimización serán w (función objetivo) y sus variables y_j. Veremos como encontrar el dual de un problema primal  de maximización, con todas sus variables no-negativas y cuyas restricciones son todas del tipo menor o igual (Problema standard de maximización).

Un problema standard de maximización se puede escribir como:

máx  z = S_i c_ix_i

sujeto a

       S_k a_1kx_k £  b₁

                   S_k a_2kx_k £  b₂

                                .
                                .

                   S_k a_mkx_k £  b_m

                                 x_k     ³ 0    (k=1,2,....n)

El dual de un problema de maximización se define como:

min  w = S_i b_iy_i

sujeto a

          S_i a_i1y_i ³  c₁

                    S_i a_i2y_i ³  c₂

                                .
                                .

                     S_i a_iny_i ³  c_n

                                 y_i     ³ 0    (i=1,2,....m)
 
 

Encuentre el dual de:

máx z = 60 x₁ + 30 x₂ + 20 x₃

s.a.        8 x₁ + 6 x₂ +  x₃ £ 48
              4 x₁ + 2 x₂ + 1.5 x₃ £ 20
              2 x₁ + 1.5 x₂ + 0.5 x₃ £ 8

                          x_k     ³ 0    (k=1,2,3)

2. Encontrando el dual de un problema no-standard.

Lamentablemente no todos los problemas en programación lineal tienen la forma del problema de maximización standard.

Pasos:

i. Identifique las variables corespondientes en el dual a su problema primal
ii. Lea el problema dual hacia abajo en forma análoga al PPL standard
iii. Si la i-ésima restricción del primal es:

1. ³  la correspondiente variable del dual y_i debe satisfacer que y_i £ 0
2. =  la correspondiente variable del dual y_i no tiene restricción de signo (srs)
3. srs la i-ésima restricción del dual será una restricción de igualdad.

máx z = 2 x₁ + x₂ 

s.a.        x₁   +  x₂   = 2
              2 x₁ -  x₂  ³ 3
              x₁   - x₂  £ 1

                          x₁     ³ 0,  x₂ srs
 

TEOREMA DEL DUAL: El valor óptimo z del problema primal es igual al valor óptimo w en el dual

3. ¿Cómo leer la solución óptima del Dual desde el tableau óptimo del primal de un problema de maximización?

Valor en el óptimo de la variable y_j del Dual es: