Problema Dual

 Problema Dual.

Definicion del Problema Dual.

Para poder elaborar el problema dual a partir del primal, este se debe presentar en su forma canónica de la siguiente forma:

El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera:

1. Cada restricción de un problema corresponde a una variable en el otro.

2. Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la función objetivo en el otro.

3. Un problema busca maximizar y el otro minimizar.

4. El problema de maximización tiene restricciones que y el problema de minimización tiene restricciones que.

5. Las variables en ambos casos son no negativas. 

¿Cómo convertir un problema primal a dual?

Un problema dual se formula de un problema primal de la siguiente forma: 

1. Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.

2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.

3. Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.

4. Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.

5. Los signos de desigualdad del  problema dual son contrarios a los del primal.

6. Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables Xn del primal se convierte en nuevas variables Ym en el dual.
7. 
   

   PROBLEMA PRIMAL EN FORMA CANONICA: MAX  Z= CX Sujeto a: AX £ b X ³ 0

   PROBLEMA DUAL EN FORMA CANONICA: MIN  Z= BY Sujeto a: AY ³ C Y ³ 0

   
   
   Ejemplo.
   Si el problema primal es: MAX  Z= 45X1 + 17X2 + 55X3
                                 Sujeto a:
                                           X1   +    X2  +     X3   £ 200
                                          9X1  +  8X2  +  10X3  £ 5000
                                          10X1+  7X2  + 21 X3  £ 4000
                                          Xj ³ 0
    El problema dual será:
             MIN  Z= 200Y1 + 5000Y2 + 4000Y3
             Sujeto a:
                         Y1 +   9Y2 + 10Y3  ³ 45
                         Y1 +   8Y2 +   7Y3  ³ 17
                         Y1 + 10Y2 + 21Y3 ³ 55
               Yj ³ 0 
   
   
   Forma de representar el problema dual.
   MIN  =  2X1 -  3X2                                                            
   Sujeto a:                                                                                    
             1X1 +  2X2  £  12                                                                       
             4X1 -   2X2  ³   3
             6X1 -   1X2  = 10                                                                          
   X1,2  ³ 0
     1.  Llevar el problema a su equivalente de maximización, multiplicando la función objetivo por –1: 
   MAX  -2X1 + 3X2
   2. Convertir las restricciones ³ en una restricción equivalente £ multiplicando por –1 ambos lados:
   -4x1 + 2x2  £ -3  
   3. Para las restricciones de igualdad, obtener 2 restricciones de desigualdad, una de forma £ y la otra de forma ³; después regresar al punto anterior y cambiar la restricción ³ a la forma £:
   6X1 – 1X2 £ 10 
   6X1 – 1X2 ³ 10
   6X1 –  1X2  £   10
   -6X1 + 1X2  £  -10
   
   
   
   
   Así el problema primal se ha replanteado en la forma equivalente: 
   MAX  Z= -2X1 + 3X2
   Sujeto a:
   1X1 + 2X2  £  12
   -4X1 + 2X2  £  - 3
   6X1 – 1X2   £  10
   -6X1 + 1X2  £ -10
          X1,2 ³ 0   
   4. Teniendo el problema primal convertido a la forma canónica de un problema de maximización, es fácil llevarlo al problema dual:
   MIN    12Y1 – 3Y2 + 10Y3
   Sujeto a:
   Y1–4Y2 + 6Y3’–6Y3’’ ³-2          Y’3  y  Y’’3 ambas se refieren a la tercera restricción
   2Y1 + 2Y2 – 1Y3’ + 1Y3’’  ³   3                  del problema  primal.
   Y1, 2, 3’, 3’’ ³ 0